## Description

## 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