Page 329 - Discrete Mathematics and Its Applications

308 4 / Number Theory and Cryptography

∗∗ 14. Show that if a and b are positive irrational numbers such 30. Explain why you cannot directly adapt the proof that there
that 1/a + 1/b = 1, then every positive integer can be are infinitely many primes (Theorem 3 in Section 4.3) to
uniquely expressed as either ka or kb for some posi- show that there are infinitely many primes in the arith-
tive integer k. metic progression 3k + 1, k = 1, 2,....
15. Prove there are infinitely many primes by showing that 31. Explain why you cannot directly adapt the proof that there
Q n = n!+ 1 must have a prime factor greater than n are infinitely many primes (Theorem 3 in Section 4.3) to
whenever n is a positive integer. show that are infinitely many primes in the arithmetic
progression 4k + 1, k = 1, 2,....
16. Find a positive integer n for which Q n = n!+ 1isnot
prime. 32. Show that if the smallest prime factor p of the positive
√
integer n is larger than 3 n, then n/p is prime or equal to
17. Use Dirichlet’s theorem, which states there are infinitely
many primes in every arithmetic progression ak + b 1.
where gcd(a, b) = 1, to show that there are infinitely A set of integers is called mutually relatively prime if the
many primes that have a decimal expansion ending greatest common divisor of these integers is 1.
with a 1. 33. Determine whether the integers in each of these sets are
mutually relatively prime.
18. Prove that if n is a positive integer such that the sum of
the divisors of n is n + 1, then n is prime. a) 8, 10, 12 b) 12, 15, 25
c) 15, 21, 28 d) 21, 24, 28, 32
∗ 19. Show that every integer greater than 11 is the sum of two
composite integers. 34. Find a set of four mutually relatively prime integers such
that no two of them are relatively prime.
20. Find the five smallest consecutive composite integers.
4
n
∗ 35. For which positive integers n is n + 4 prime?
21. Show that Goldbach’s conjecture, which states that ev-
ery even integer greater than 2 is the sum of two primes, 36. Show that the system of congruences x ≡ 2 (mod 6) and
is equivalent to the statement that every integer greater x ≡ 3 (mod 9) has no solutions.
than 5 is the sum of three primes. 37. Find all solutions of the system of congruences x ≡
22. Find an arithmetic progression of length six beginning 4 (mod 6) and x ≡ 13 (mod 15).
with 7 that contains only primes. ∗ 38. a) Show that the system of congruences x ≡ a 1 (mod m 1 )
∗ 23. Prove that if f(x) is a nonconstant polynomial with inte- and x ≡ a 2 (mod m 2 ), where a 1 ,a 2 ,m 1 , and m 2 are
ger coefficients, then there is an integer y such that f(y) is integers with m 1 > 0 and m 2 > 0, has a solution if
composite. [Hint:Assume that f(x 0 ) = p is prime. Show and only if gcd(m 1 ,m 2 ) | a 1 − a 2 .
that p divides f(x 0 + kp) for all integers k. Obtain a con- b) Show that if the system in part (a) has a solution, then
tradiction of the fact that a polynomial of degree n, where it is unique modulo lcm(m 1 ,m 2 ).
n> 1, takes on each value at most n times.] 39. Prove that 30 divides n − n for every nonnegative
9
∗ 24. How many zeros are at the end of the binary expansion integer n.
of 100 10! ? 40. Prove that n 12 − 1 is divisible by 35 for every integer n
25. Use the Euclidean algorithm to find the greatest common for which gcd(n, 35) = 1.
divisor of 10,223 and 33,341. 41. Show that if p and q are distinct prime numbers, then
p q−1 + q p−1 ≡ 1 (mod pq).
26. How many divisions are required to find gcd(144, 233)
using the Euclidean algorithm? The check digit a 13 for an ISBN-13 with initial digits
a 1 a 2 ...a 12 is determined by the congruence (a 1 + a 3 +
27. Find gcd(2n + 1, 3n + 2), where n is a positive integer.
··· + a 13 ) + 3(a 2 + a 4 + ··· + a 12 ) ≡ 0 (mod 10).
[Hint: Use the Euclidean algorithm.]
42. Determine whether each of these 13-digit numbers is a
28. a) Show that if a and b are positive inte-
valid ISBN-13.
gers with a ≥ b, then gcd(a, b) = a if a = b,
a) 978-0-073-20679-1
gcd(a, b) = 2 gcd(a/2,b/2) if a and b are even,
gcd(a, b) = gcd(a/2,b) if a is even and b is odd, and b) 978-0-45424-521-1
gcd(a, b) = gcd(a − b, b) if both a and b are odd. c) 978-3-16-148410-0
b) Explain how to use (a) to construct an algorithm for d) 978-0-201-10179-9
computing the greatest common divisor of two posi- 43. Show that the check digit of an ISBN-13 can always detect
tive integers that uses only comparisons, subtractions, a single error.
and shifts of binary expansions, without using any 44. Show that there are transpositions of two digits that are
divisions.
not detected by an ISBN-13.
c) Find gcd(1202, 4848) using this algorithm.
A routing transit number (RTN) is a bank code used in
29. Adapttheproofthatthereareinfinitelymanyprimes(The- the United States which appears on the bottom of checks.
orem 3 in Section 4.3) to show that are infinitely many The most common form of an RTN has nine digits, where
primes in the arithmetic progression 6k + 5, k = 1, 2,.... the last digit is a check digit. If d 1 d 2 ...d 9 is a valid RTN,