The Integers - Introduction to Cryptography with Java Applets - page 87

13. Prove proposition 10. (Hint: Use proposition 2 to show that the common divisors of c
and d are the same as the common divisors of d and r .)
14. Write a gcd() method for the Int class without using recursion.
15. Add a gcd button to the Int calculator developed in a previous exercise. Use your own
gcd() method from the previous exercise.
16. Express the gcd of each of the following pairs of integers as a linear combination of the
pair.
a. 45 and 75
b. 121 and 32
c. 512 and 96
d. 10101 and 27
e. 39 and 143
f. 1023 and 300
g. 25 and 26
h. 423102 and 462
i. 98 and 70
j. 23984756 and 9238475
17. Write a recursive version of the euclid() method for BigIntegers.
18. Give the prime power factorization of the following integers:
a. 10201
b. 874
c. 252
d. 5250
e. 1212
f. 36179
g. 4350
19. Prove that if a and b are nonzero integers, then lcm( a , b ) = ab /( a , b ).
20. Calculate the lcm of the following pairs of integers:
a. 104, 24
b. 252, 198
c. 17, 83
d.

123, 6

e. 987654321, 123456789