Description
Directions: Write up carefully argued solutions to the following problems. Your solution should be clear
enough that it should explain to someone who does not already understand the answer why it works. However,
you may use results from lecture, the theorems handout, and previous homeworks without proof.
1. A Modding Acquaintance (10 points)
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).
(a) gcd(44, 180)
(b) gcd(340, 178)
(c) gcd(232 − 1, 2
0 − 1).
2. Mod Squad (22 points)
(a) [5 Points] 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).
(b) [8 Points] 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.
(c) [6 Points] 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.
(d) [3 Points] Prove that all solutions to the equation in part (b) are also solutions to
34x + 3 ≡ 4x + 25 (mod 103).
1
3. Two Peas In a Mod (10 points)
(a) [7 Points] Compute 3
338 mod 100 using the efficient modular exponentiation algorithm. Show all intermediate results.
(b) [1 Point] How many multiplications does the algorithm use for this computation?
(c) [1 Point] For the multiplications performed by the algorithm, what is the maximum number of decimal
digits in the result?
(d) [1 Point] Suppose that we instead computed the integer 3
338. How many decimal digits does it have?
4. Weekend At Cape Mod (18 points)
Let m and n be positive integers.
(a) [6 Points] Prove that, if a ≡ b (mod m) and a ≡ c (mod n), then b ≡ c (mod d), where d = gcd(m, n).
(b) [10 Points] 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.
(c) [2 Points] 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 (20 points)
Prove, by induction, that n
3 + 2n is divisible by 3 for any positive integer n.
6. Super Colliding Super Inductor (20 points)
Prove that, for all n ∈ N and all x ∈ R with x > −2, the inequality (2 + x)
n ≥ 2
n + n2
n−1x holds.
2
7. RSA [Extra credit] (0 points)
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
10 mod 3 = 1 but 2
10 mod 3 mod 3 = 21 mod 3 = 2.
The correct law for the exponent is more subtle. We will prove it in steps….
(a) 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.
(b) 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|.
(c) Use the last result to show that, for any b ≥ 0 and a ∈ R, we have a
b ≡ a
b mod φ(m)
(mod m).
(d) Finally, prove the following two facts about the function φ above. 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.
3
