Number theory problem set 3

1. Suppose that plaintext message units are digraphs in the ordinary 26-letteralphabet, where (as usual) A-Z corresponds to 0-25. We represent each digraph ij as an integer in the following way:

(26 · i) + j.

For example, the digraph “IN” is represented as 26 · 8 + 13 = 221.

You receive the sequence of ciphertext message units,

5997,5520,3280,824,4595,7366,5967,2026,5764,2849,4743

which were encrypted using a Merkle-Hellman knapsack system. (Each unit is the encryption of a digraph, and hence represents two plaintext letters.) The private key for the system is

(M = 2629,W = 1036,{`{3,5,10,19,41,79,161,320,641,1311}`}).

Your job is to decipher the message.

2. Use the repeated squaring method (Algorithm 3.3 in the number theory notes) to calculate 652⁸⁴⁸ mod 4847.

In proving the following facts, you may use without proof any result stated in sections 1-3 of the Number Theory notes (except, of course, if the given result itself is what you’re being asked to prove. In that case, you may use without proof any result stated in sections 1-3 of the Number Theory notes up to the result I’m asking you to prove.) If you use some number theoretic result not stated in sections 1-3 of the notes, you should prove that result first (using, of course, the results in sections 1-3 of the notes).

3. Complete the proof of the gcd recursion theorem (Theorem 1.6 in the number theory notes).
4. Complete the proof of Theorem 1.13 in the notes: If there are integers x,y such that ax + by = 1, then gcd(a,b) = 1.
5. Prove that if a ⊥ m and b ⊥ m, then ab ⊥ m.

(This is part of Theorem 1.15 in the notes.)

6. Prove that if a ≡ a b (mod m) and gcd(m,a) = 1, then b ≡ 1 (mod m).

(Note: This is a special case of the cancellation property described (but not proved) on p.10 of the Number Theory notes. The idea here is to prove this special case directly. In particular, you shouldn’t use the cancellation property, and you shouldn’t assume (without proof) the existence of an inverse for a)

7. Consider the statement, “if a ≡ b (mod m) and a ≡ b (mod n), then a ≡ b (mod mn)”.
8. Show by example that this statement is not true in general.
9. Prove that the statement is true if m ⊥ n.
10. Prove that if x ≡ y (mod m), then gcd(x,m) = gcd(y,m).