Page 294 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 273

2
3
c) 17, 17 17 d) 2 · 7, 5 · 13 40. Using the method followed in Example 17, express the
e) 0, 5 f) 2 · 3 · 5 · 7, 2 · 3 · 5 · 7 greatest common divisor of each of these pairs of integers
25. What are the greatest common divisors of these pairs of as a linear combination of these integers.
integers? a) 9, 11 b) 33, 44 c) 35, 78
5
3
7
3
a) 3 · 5 · 7 ,2 11 · 3 · 5 9 d) 21, 55 e) 101, 203 f) 124, 323
5
9
7
b) 11 · 13 · 17, 2 · 3 · 5 · 7 3 g) 2002, 2339 h) 3457, 4669 i) 10001, 13422
31
c) 23 ,23 17 The extended Euclidean algorithm can be used to express
d) 41 · 43 · 53, 41 · 43 · 53 gcd(a, b) as a linear combination with integer coefficients of
17
e) 3 13 · 5 ,2 12 · 7 21 the integers a and b. We set s 0 = 1, s 1 = 0, t 0 = 0, and t 1 = 1
f) 1111, 0
and let s j = s j−2 − q j−1 s j−1 and t j = t j−2 − q j−1 t j−1 for
26. What is the least common multiple of each pair in Exer- j = 2, 3,...,n, where the q j are the quotients in the di-
cise 24?
visions used when the Euclidean algorithm finds gcd(a, b),
27. What is the least common multiple of each pair in Exer- as shown in the text. It can be shown (see [Ro10]) that
cise 25? gcd(a, b) = s n a + t n b. The main advantage of the extended
28. Find gcd(1000, 625) and lcm(1000, 625) and verify that Euclidean algorithm is that it uses one pass through the steps
gcd(1000, 625) · lcm(1000, 625) = 1000 · 625. of the Euclidean algorithm to find Bézout coefficients of a
29. Find gcd(92928, 123552) and lcm(92928, 123552), and and b, unlike the method in the text which uses two passes.
verify that gcd(92928, 123552) · lcm(92928, 123552) = 41. Use the extended Euclidean algorithm to express
92928 · 123552. [Hint: First find the prime factorizations gcd(26, 91) as a linear combination of 26 and 91.
of 92928 and 123552.] 42. Use the extended Euclidean algorithm to express
7 8 2 11
30. If the product of two integers is 2 3 5 7 and their great- gcd(252, 356) as a linear combination of 252 and 356.
3 4
est common divisor is 2 3 5, what is their least common 43. Use the extended Euclidean algorithm to express
multiple?
gcd(144, 89) as a linear combination of 144 and 89.
31. Show that if a and b are positive integers, then ab =
gcd(a, b) · lcm(a, b).[Hint: Use the prime factorizations 44. Use the extended Euclidean algorithm to express
gcd(1001, 100001) as a linear combination of 1001 and
of a and b and the formulae for gcd(a, b) and lcm(a, b)
in terms of these factorizations.] 100001.
32. Use the Euclidean algorithm to find 45. Describe the extended Euclidean algorithm using pseu-
docode.
a) gcd(1, 5). b) gcd(100, 101).
c) gcd(123, 277). d) gcd(1529, 14039). 46. Find the smallest positive integer with exactly n different
e) gcd(1529, 14038). f) gcd(11111, 111111). positive factors when n is
33. Use the Euclidean algorithm to find a) 3. b) 4. c) 5.
a) gcd(12, 18). b) gcd(111, 201). d) 6. e) 10.
c) gcd(1001, 1331). d) gcd(12345, 54321). 47. Can you find a formula or rule for the nth term of a se-
e) gcd(1000, 5040). f) gcd(9888, 6060). quence related to the prime numbers or prime factoriza-
34. How many divisions are required to find gcd(21, 34) us- tions so that the initial terms of the sequence have these
ing the Euclidean algorithm? values?
35. How many divisions are required to find gcd(34, 55) us- a) 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,...
ing the Euclidean algorithm? b) 1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2,...
∗ 36. Show that if a and b are both positive integers, then c) 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4,...
b
a
(2 − 1) mod (2 − 1) = 2 a mod b − 1. d) 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1,...
∗ 37. Use Exercise 36 to show that if a and b are posi- e) 1, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13,...
a
b
tive integers, then gcd(2 − 1, 2 − 1) = 2 gcd(a, b) − 1. f) 1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690,
[Hint: Show that the remainders obtained when the Eu- 223092870,...
b
a
clidean algorithm is used to compute gcd(2 − 1, 2 − 1) 48. Can you find a formula or rule for the nth term of a se-
r
are of the form 2 − 1, where r is a remainder arising quence related to the prime numbers or prime factoriza-
when the Euclidean algorithm is used to find gcd(a, b).] tions so that the initial terms of the sequence have these
38. Use Exercise 37 to show that the integers 2 35 − 1, 2 34 − values?
1, 2 33 − 1, 2 31 − 1, 2 29 − 1, and 2 23 − 1 are pairwise a) 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13,...
relatively prime. b) 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6,...
39. Using the method followed in Example 17, express the c) 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1,...
greatest common divisor of each of these pairs of integers d) 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1,...
as a linear combination of these integers. e) 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0,...
a) 10, 11 b) 21, 44 c) 36, 48 f) 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369,...
d) 34, 55 e) 117, 213 f) 0, 223 49. Prove that the product of any three consecutive integers
g) 123, 2347 h) 3454, 4666 i) 9999, 11111
is divisible by 6.