Page 307 - Discrete Mathematics and Its Applications

286 4 / Number Theory and Cryptography

38. a) Use Fermat’s little theorem to compute 3 302 mod 5, 54. Show that 2 is a primitive root of 19.
3 302 mod 7, and 3 302 mod 11. 55. Find the discrete logarithms of 5 and 6 to the base 2 mod-
b) Use your results from part (a) and the Chinese re- ulo 19.
mainder theorem to find 3 302 mod 385. (Note that 56. Let p be an odd prime and r a primitive root of p.
385 = 5 · 7 · 11.) Show that if a and b are positive integers in Z p , then
39. a) Use Fermat’s little theorem to compute 5 2003 mod 7, log (ab) ≡ log a + log b (mod p − 1).
r
r
r
5 2003 mod 11, and 5 2003 mod 13. 57. Write out a table of discrete logarithms modulo 17 with
b) Use your results from part (a) and the Chinese re- respect to the primitive root 3.
mainder theorem to find 5 2003 mod 1001. (Note that If m is a positive integer, the integer a is a quadratic residue
1001 = 7 · 11 · 13.) 2
of m if gcd(a, m) = 1 and the congruence x ≡ a(mod m)
40. Show with the help of Fermat’s little theorem that if n is has a solution. In other words, a quadratic residue of m is
7
a positive integer, then 42 divides n − n. an integer relatively prime to m that is a perfect square mod-
41. Show that if p is an odd prime, then every divisor of the ulo m.If a is not a quadratic residue of m and gcd(a, m) = 1,
p
Mersenne number 2 − 1 is of the form 2kp + 1, where we say that it is a quadratic nonresidue of m. For exam-
k is a nonnegative integer. [Hint: Use Fermat’s little the- ple, 2 is a quadratic residue of 7 because gcd(2, 7) = 1 and
2
orem and Exercise 37 of Section 4.3.] 3 ≡ 2 (mod 7) and 3 is a quadratic nonresidue of 7 because
2
42. Use Exercise 41 to determine whether M 13 = 2 13 − 1 = gcd(3, 7) = 1 and x ≡ 3 (mod 7) has no solution.
8191 and M 23 = 2 23 − 1 = 8,388,607 are prime. 58. Which integers are quadratic residues of 11?
43. Use Exercise 41 to determine whether M 11 = 2 11 − 1 = 59. Show that if p is an odd prime and a is an integer not
2
2047 and M 17 = 2 17 − 1 = 131,071 are prime. divisible by p, then the congruence x ≡ a(mod p) has
s
Let n be a positive integer and let n − 1 = 2 t, where s is a either no solutions or exactly two incongruent solutions
nonnegative integer and t is an odd positive integer. We say modulo p.
t
that n passes Miller’s test for the base b if either b ≡ 1 (mod 60. Show that if p is an odd prime, then there are exactly
j
n)or b 2 t ≡−1 (mod n) for some j with 0 ≤ j ≤ s − 1. It (p − 1)/2 quadratic residues of p among the integers
can be shown (see [Ro10]) that a composite integer n passes 1, 2,...,p − 1.
Miller’s test for fewer than n/4 bases b with 1 <b <n.A If p is an odd prime and a is an integer not divisible by p, the

composite positive integer n that passes Miller’s test to the a
Legendre symbol is defined to be 1 if a is a quadratic
base b is called a strong pseudoprime to the base b. p
∗ 44. Show that if n is prime and b is a positive integer with residue of p and −1 otherwise.
n | b, then n passes Miller’s test to the base b. 61. Show that if p is an odd prime and a and b are integers
45. Show that 2047 is a strong pseudoprime to the base 2 by with a ≡ b(mod p), then
showing that it passes Miller’s test to the base 2, but is

composite. a b
= .
46. Show that 1729 is a Carmichael number. p p
47. Show that 2821 is a Carmichael number.
62. Prove Euler’s criterion, which states that if p is an odd
∗
48. Show that if n = p 1 p 2 ··· p k , where p 1 ,p 2 ,...,p k
prime and a is a positive integer not divisible by p, then
are distinct primes that satisfy p j − 1 | n − 1 for j =
1, 2,...,k, then n is a Carmichael number.
a (p−1)/2
49. a) Use Exercise 48 to show that every integer of the form p ≡ a (mod p).
(6m + 1)(12m + 1)(18m + 1), where m is a positive
integer and 6m + 1, 12m + 1, and 18m + 1 are all [Hint: If a is a quadratic residue modulo p, apply Fer-
primes, is a Carmichael number. mat’s little theorem; otherwise, apply Wilson’s theorem,
b) Use part (a) to show that 172,947,529 is a Car- given in Exercise 18(b).]
michael number.
63. Use Exercise 62 to show that if p is an odd prime and a
50. Find the nonnegative integer a less than 28 represented by and b are integers not divisible by p, then
each of these pairs, where each pair represents (a mod 4,
a mod 7).
ab a b
a) (0, 0) b) (1, 0) c) (1, 1) p = p p .
d) (2, 1) e) (2, 2) f) (0, 3)
g) (2, 0) h) (3, 5) i) (3, 6)
64. Show that if p is an odd prime, then −1 is a quadratic
51. Express each nonnegative integer a less than 15 as a pair residue of p if p ≡ 1 (mod 4), and −1 is not a quadratic
(a mod 3, a mod 5). residue of p if p ≡ 3 (mod 4).[Hint: Use Exercise 62.]
2
52. Explain how to use the pairs found in Exercise 51 to 65. Find all solutions of the congruence x ≡ 29 (mod 35).
add 4 and 7. [Hint: Find the solutions of this congruence modulo 5 and
53. Solve the system of congruences that arises in Example 8. modulo 7, and then use the Chinese remainder theorem.]