CSE311-Homework 5 Solved

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).

(a)     gcd(44,180)

(b)    gcd(340,178)

(c)     gcd(232 − 1,20 − 1).

2. Mod Squad
(a)     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)    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)      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)    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
(a)     Compute 3338 mod 100 using the efficient modular exponentiation algorithm. Show all intermediate results.

(b)    How many multiplications does the algorithm use for this computation?

(c)     For the multiplications performed by the algorithm, what is the maximum number of decimal digits in the result?

(d)    Suppose that we instead computed the integer 3338. How many decimal digits does it have?

4. Weekend At Cape Mod
Let m and n be positive integers.

(a)     Prove that, if a ≡ b (mod m) and a ≡ c (mod n), then b ≡ c (mod d), where d = gcd(m,n).

(b)    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)     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 n3 + 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)n ≥ 2n + n2n−1x holds.

7. RSA [Extra credit]
We know that we can reduce the base of an exponent modulo m : ak ≡ (a mod m)k (mod m). But the same is not true of the exponent itself! That is, we cannot write ak ≡ ak mod m (mod m). This is easily seen to be false in general. Consider, for instance, that 210 mod 3 = 1 but 210 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 ab ≡ ab 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.