Description

Modding Acquaintance

Compute each of the following using Euclid’s 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 Bézout’s 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.