Section 2.4 Number Theory
153
For Exercises 21–24, find the gcd and lcm of the two numbers given.
21. a = 2
2 # 3 # 11, b = 2 # 3 # 11
2 # 13
22. a = 2
4 # 5
2 # 7
3
, b = 5 # 7
2
23. a = 3 # 5
3 # 11
2
, b = 3
2 # 5 # 11 # 17
24. a = 5 # 11 # 23
2
, b = 5
3 # 11
3
25. Prove that for any positive integers a and b, gcd(a, b) = gcd(a, a + b).
26. Prove that gcd(n, n + 1) = 1 for all positive integers n.
27. Find an example where n 0 ab but n | a and n | b. Does this violate the theorem of division by prime
numbers?
28. The division of a full circle into 360° probably dates back to the early Persian calendar from around
700 b.c. that used 360 days in a year, so one day represented a rotation of 1/360 of other stars around the
North Star. But it was also chosen because it is divisible by so many factors, avoiding the need to deal with
fractions. Find the distinct nontrivial (but not necessarily prime) factors of 360.
29. Prove that there exist three consecutive odd positive integers that are prime numbers.
30. Prove that for any positive integer n, there exist n consecutive composite numbers. [Hint: Start with
(n + 1)! + 2]
For Exercises 31–34, find φ(n) together with the numbers that give those values.
31. n = 8
32. n = 9
33. n = 10
34. n = 11
35. By Practice 16, if p is prime then φ(p) = p − 1. Prove that this is an “if and only if” condition by proving
that if φ(n) = n – 1 for a positive integer n > 1, then n is prime.
36. For any prime number p and any positive integer k, φ(p
k
) = p
k−1
φ(p). Although this result follows directly
from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.
37. Compute φ(2
4
) and state the numbers being counted. (Hint: See Exercise 36.)
38. Compute φ(3
3
) and state the numbers being counted. (Hint: See Exercise 36.)
For Exercises 39–42, compute φ(n).
39. n = 117612 = 2
2 # 3
5 # 11
2
40. n = 233206 = 2 # 17 # 19
3
41. n = 1795625 = 5
4 # 13
2 # 17
42. n = 1,690,541,699 = 7
4 # 11
3 # 23
2
43. If p and q are prime numbers with p ≠ q, then φ(pq) = φ(p)φ(q). Although this result follows directly
from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.
44. Prove that if r and s are relatively prime, then φ(rs) = φ(r) φ(s).
45. Prove that for n and m positive integers, φ(n
m
) = n
m−1
φ(n).
46. Except for n = 2, all the values of φ(n) in Example 34 are even numbers. Prove that φ(n) is even for all
n > 2.
47. A particular class of prime numbers is known as Mersenne primes, named for a French monk and mathematician of the seventeenth century who studied them. Mersenne primes are numbers of the form 2
p
− 1
where p is a prime, but not all numbers of this form are primes. For example, 2
11
− 1 = 23 # 89 is not
153
For Exercises 21–24, find the gcd and lcm of the two numbers given.
21. a = 2
2 # 3 # 11, b = 2 # 3 # 11
2 # 13
22. a = 2
4 # 5
2 # 7
3
, b = 5 # 7
2
23. a = 3 # 5
3 # 11
2
, b = 3
2 # 5 # 11 # 17
24. a = 5 # 11 # 23
2
, b = 5
3 # 11
3
25. Prove that for any positive integers a and b, gcd(a, b) = gcd(a, a + b).
26. Prove that gcd(n, n + 1) = 1 for all positive integers n.
27. Find an example where n 0 ab but n | a and n | b. Does this violate the theorem of division by prime
numbers?
28. The division of a full circle into 360° probably dates back to the early Persian calendar from around
700 b.c. that used 360 days in a year, so one day represented a rotation of 1/360 of other stars around the
North Star. But it was also chosen because it is divisible by so many factors, avoiding the need to deal with
fractions. Find the distinct nontrivial (but not necessarily prime) factors of 360.
29. Prove that there exist three consecutive odd positive integers that are prime numbers.
30. Prove that for any positive integer n, there exist n consecutive composite numbers. [Hint: Start with
(n + 1)! + 2]
For Exercises 31–34, find φ(n) together with the numbers that give those values.
31. n = 8
32. n = 9
33. n = 10
34. n = 11
35. By Practice 16, if p is prime then φ(p) = p − 1. Prove that this is an “if and only if” condition by proving
that if φ(n) = n – 1 for a positive integer n > 1, then n is prime.
36. For any prime number p and any positive integer k, φ(p
k
) = p
k−1
φ(p). Although this result follows directly
from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.
37. Compute φ(2
4
) and state the numbers being counted. (Hint: See Exercise 36.)
38. Compute φ(3
3
) and state the numbers being counted. (Hint: See Exercise 36.)
For Exercises 39–42, compute φ(n).
39. n = 117612 = 2
2 # 3
5 # 11
2
40. n = 233206 = 2 # 17 # 19
3
41. n = 1795625 = 5
4 # 13
2 # 17
42. n = 1,690,541,699 = 7
4 # 11
3 # 23
2
43. If p and q are prime numbers with p ≠ q, then φ(pq) = φ(p)φ(q). Although this result follows directly
from Equation (2) in this section, give a direct proof using the definition of the Euler phi function.
44. Prove that if r and s are relatively prime, then φ(rs) = φ(r) φ(s).
45. Prove that for n and m positive integers, φ(n
m
) = n
m−1
φ(n).
46. Except for n = 2, all the values of φ(n) in Example 34 are even numbers. Prove that φ(n) is even for all
n > 2.
47. A particular class of prime numbers is known as Mersenne primes, named for a French monk and mathematician of the seventeenth century who studied them. Mersenne primes are numbers of the form 2
p
− 1
where p is a prime, but not all numbers of this form are primes. For example, 2
11
− 1 = 23 # 89 is not