Page 293 - Discrete Mathematics and Its Applications

272 4 / Number Theory and Cryptography

Although we cannot divide both sides of a congruence by any integer to produce a valid
congruence, we can if this integer is relatively prime to the modulus. Theorem 7 establishes this
important fact. We use Lemma 2 in the proof.

THEOREM 7 Let m be a positive integer and let a, b, and c be integers. If ac ≡ bc (mod m) and
gcd(c, m) = 1, then a ≡ b(mod m).

Proof: Because ac ≡ bc (mod m), m | ac − bc = c(a − b). By Lemma 2, because
gcd(c, m) = 1, it follows that m | a − b. We conclude that a ≡ b(mod m).

Exercises

1. Determine whether each of these integers is prime. 14. Which positive integers less than 12 are relatively prime
a) 21 b) 29 to 12?
c) 71 d) 97 15. Which positive integers less than 30 are relatively prime
e) 111 f) 143 to 30?
2. Determine whether each of these integers is prime. 16. Determine whether the integers in each of these sets are
a) 19 b) 27 pairwise relatively prime.
c) 93 d) 101 a) 21, 34, 55 b) 14, 17, 85
e) 107 f) 113 c) 25, 41, 49, 64 d) 17, 18, 19, 23
3. Find the prime factorization of each of these integers. 17. Determine whether the integers in each of these sets are
a) 88 b) 126 c) 729 pairwise relatively prime.
d) 1001 e) 1111 f) 909,090 a) 11, 15, 19 b) 14, 15, 21
4. Find the prime factorization of each of these integers. c) 12, 17, 31, 37 d) 7, 8, 9, 11
a) 39 b) 81 c) 101 18. We call a positive integer perfect if it equals the sum of
d) 143 e) 289 f) 899 its positive divisors other than itself.
5. Find the prime factorization of 10!. a) Show that 6 and 28 are perfect.
p−1
p
b) Show that 2 (2 − 1) is a perfect number when
∗ 6. How many zeros are there at the end of 100!? p
2 − 1 is prime.
7. Express in pseudocode the trial division algorithm for n
19. Show that if 2 − 1 is prime, then n is prime. [Hint: Use
determining whether an integer is prime. ab a a(b−1) a(b−2)
the identity 2 − 1 = (2 − 1) · (2 + 2 +
8. Express in pseudocode the algorithm described in the text ··· + 2 + 1).]
a
for finding the prime factorization of an integer. 20. Determine whether each of these integers is prime, veri-
m
9. Show that if a + 1 is composite if a and m are integers fying some of Mersenne’s claims.
greater than 1 and m is odd. [Hint: Show that x + 1isa 7 9
m
factor of the polynomial x + 1if m is odd.] a) 2 − 1 b) 2 − 1
11
13
− 1
c) 2
− 1
d) 2
m
10. Show that if 2 + 1 is an odd prime, then m = 2 n
for some nonnegative integer n.[Hint: First show that The value of the Euler φ-function at the positive integer n
is defined to be the number of positive integers less than or
k
m
the polynomial identity x + 1 = (x + 1)(x k(t−1) − equal to n that are relatively prime to n.[Note: φ is the Greek
k
x k(t−2) + ··· − x + 1) holds, where m = kt and t
letter phi.]
is odd.]
21. Find these values of the Euler φ-function.
∗ 11. Show that log 3 is an irrational number. Recall that an ir-
2
rational number is a real number x that cannot be written a) φ(4). b) φ(10). c) φ(13).
as the ratio of two integers. 22. Show that n is prime if and only if φ(n) = n − 1.
k
12. Prove that for every positive integer n, there are n con- 23. What is the value of φ(p ) when p is prime and k is a
secutive composite integers. [Hint: Consider the n con- positive integer?
secutive integers starting with (n + 1)!+ 2.] 24. What are the greatest common divisors of these pairs of
∗ 13. Prove or disprove that there are three consecutive odd integers?
2
3
5
3
5
positive integers that are primes, that is, odd primes of a) 2 · 3 · 5 ,2 · 3 · 5 2
9
the form p, p + 2, and p + 4. b) 2 · 3 · 5 · 7 · 11 · 13, 2 11 · 3 · 11 · 17 14