A+ Answers

1.   For each of the following, say whether a modular multiplicative inverse exists by considering relative primality.

(a) mod-7 inverse of 6?

(b) mod-7 inverse of 14?

(c) mod-25 inverse of 4

(d) mod-25 inverse of 5?

(e) mod-24 inverse of 21?

2.   Recall Euler’s phi function from Chapter 7. What is the smallest positive integer that has a mod-φ(21) multiplicative inverse?

(a) What is the greatest common divisor?

(b) Name two integers s and t such that the greatest common divisor equals s • 18 + t • 15.

4.   Consider the integers 70 and 40.

(a) What is the greatest common divisor?

(b) Name two integers s and t such that the greatest common divisor equals s • 70 + t • 40.

Setting s • 70 + t • 40 equal to the greatest common divisor found in part (a) gives:

5.   Use EuclidCards on inputs 55 and 24. Find the greatest common divisor and integers s and t such that the greatest common divisor equals s • 55 + t • 24.

6.   Use EuclidCards on inputs 259 and 105. Find the greatest common divisor and integers s and t such that the greatest common divisor equals s • 259 + t • 105.

7.   Use EuclidCards on inputs 34 and 21. Find the greatest common divisor and integers s and t such that the greatest common divisor equals s • 34 + t • 21.

8.   Use EuclidCards to find the mod-394820020 multiplicative inverse of 3.