Modding Acquaintance

Compute each of the following using Euclids Algorithm. Show your intermediate results, both as a sequence of recursive calls and in tableau form (showing just the divisions performed, as shown in lecture).

• gcd(44,180)
• gcd(340,178)
• gcd(2³² 1,2⁰ 1).

2. Mod Squad

• Compute the multiplicative inverse of 15 modulo 103 using the Extended Euclidean Algorithm. Your answer should be a number between 0 and 102. Show your work in tableau form (the divisions performed, the equations for the remainders, and the sequence of substitutions).
• Find all integer solutions x Z to the equation

15x 11 (mod 103)

It is not sufficient just to state the answer. You need to prove that your answer is correct.

• Prove that there are no integer solutions to the equation

10x 3 (mod 15)

Note: this does not follow from (just) the fact that 10 does not have a multiplicative inverse modulo 15. That argument, if true, would apply to the equation 10x 10 (mod 15), which actually does have solutions (e.g., x = 1)! Hence, a different argument is required to show that this equation has no integer solutions.

Hint: By De Morgan, there does not exist a solution if and only if every x Z is not a solution. Hence, one way to prove this is to assume that x satisfies the above equation and establish that this is a contradiction. That would show that the assumption (that x was a solution) is false.

• Prove that all solutions to the equation in part (b) are also solutions to

34x + 3 4x + 25 (mod 103).

3. Two Peas In a Mod

• Compute 3³³⁸ mod 100 using the efficient modular exponentiation algorithm. Show all intermediate results.
• How many multiplications does the algorithm use for this computation?
• For the multiplications performed by the algorithm, what is the maximum number of decimal digits in the result?
• Suppose that we instead computed the integer 3³³⁸. How many decimal digits does it have?

4. Weekend At Cape Mod

Let m and n be positive integers.

• Prove that, if a b (mod m) and a c (mod n), then b c (mod d), where d = gcd(m,n).
• Prove that, if b c (mod d), with d = gcd(m,n), then there exists some a Z such that a b (mod m) and a c (mod n).

Hint: Start by applying Bzouts theorem to m and n. Then, use the assumption to find a number of the form c + ()n that is also of the form b + ()m.

• Explain why the pair of congruences, a b (mod m) and a c (mod n), has a solution if and only if b c (mod d), where d = gcd(m,n).

5. Master of Induction

Prove, by induction, that n³ + 2n is divisible by 3 for any positive integer n.

6. Super Colliding Super Inductor

Prove that, for all n N and all x R with x > 2, the inequality (2 + x)ⁿ 2ⁿ + n2ⁿ¹x holds.

7. RSA [Extra credit]

We know that we can reduce the base of an exponent modulo m : a^k (a mod m)^k (mod m). But the same is not true of the exponent itself! That is, we cannot write a^k a^{k mod m} (mod m). This is easily seen to be false in general. Consider, for instance, that 2¹⁰ mod 3 = 1 but 2^{10 mod 3} mod 3 = 2¹ mod 3 = 2.

The correct law for the exponent is more subtle. We will prove it in steps.

• Let R = {n Z : 1 n m 1 gcd(n,m) = 1}. Define the set aR = {ax mod m : x R}. Prove that aR = R for every integer a > 0 with gcd(a,m) = 1.
• Consider the product of all the elements in R modulo m and the elements in aR modulo m. By comparing those two expressions, conclude that, for all a R, we have a^(m) 1 (mod m), where (m) = |R|.
• Use the last result to show that, for any b 0 and a R, we have a^b a^{b mod (m)} (mod m).
• Finally, prove the following two facts about the function First, if p is prime, then (p) = p 1. Second, for any primes a and b with a 6= b, we have (ab) = (a)(b). (Or slightly more challenging: show this second claim for all positive integers a and b with gcd(a,b) = 1.)

The second fact of part (d) implies that, if p and q are primes, then (pq) = (p 1)(q 1). That along with part (c) prove of the final claim from lecture about RSA, completing the proof of correctness of the algorithm.