8.1 What is a prime number?
8.2 What is the meaning of the expression a divides b?
8.3 What is Euler's totient function?
8.4 The Miller-Rabin test can determine if a number is not prime but cannot determine if a number is prime. How
can such an algorithm be used to test for primality?
8.5 What is a primitive root of a number?
8.6 What is the difference between an index and a discrete logarithm?
Problems
8.1 The purpose of this problem is to determine how many prime numbers there are. Suppose there are a total of n prime numbers, and we list these in order:
p1 = 2 < p2 = 3 < p3 = 5 < ... < pn.
a. Define X = 1 +p1p2...pn. That is, X is equal to one plus the product of all the primes. Can we find
prime number pm that divides X?
b. What can you say about m?
c. Deduce that the total number of primes cannot be finite.
d. Show that pn+1 <= 1 + p1p2...pn.
8.2 The purpose of this problem is to demonstrate that the probability that two random numbers are relatively prime is about 0.6.
Let P = Pr[gcd(a,b) = 1]. Show that Pr[gcd(a,b) = d] = P/d2
Hint: Consider the quantity gcd (a/d , b/d)
b. The sum of the result of part (a) over all possible values of d is 1. That is:
8.4 Using Fermat's theorem, find 3201 mod 11.
8.5 Use Fermat's Theorem to find a number a between 0 and 72 with a congruent to 9794 modulo 73.
8.6 Use Fermat's Theorem to find a number x between 0 and 28 with x85 congruent to 6 modulo 29. (You should not need to use any brute force searching.)
8.7 Use Euler's Theorem to find a number a between 0 and 9 such that a is congruent to 7
1000 modulo 10. (Note that this is the same as the last digit of the decimal expansion of 7
1000.)
8.8 Use Euler's Theorem to find a number x between 0 and 28 with x 85
congruent to 6 modulo 35. (You should not need to use any brute force searching.)
8.9 Notice in Table 8.2 that f(n) is even for n > 2. This is true for all n > 2. Give a concise argument why this is so.
8.10 Prove the following: If p is prime, then f(pi) = pi p i1. Hint: What numbers have a factor in common with p i?
8.11 It can be shown (see any book on number theory) that if gcd(m, n) = 1 then f(mn) = f(m)f(n). Using this property and the property developed in the preceding problem and the property that f(p) = p 1 forp prime, it is straightforward to determine the value of f(n) for any n. Determine the following:
a. f(41)
b. f(27)
c. f(231)
d. f(440)
8.12 It can also be shown that for arbitrary positive integer a,f(a) is given by:
8.14 Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that n is prime if and only if n divides (2n2).
a. Give an example that satisfies the condition using an odd prime.
b. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime
(proving the if condition)
c. Give an example of an odd n that is not prime and that does not satisfy the condition. You can do
this with nonprime numbers up to a very large value. This misled the Chinese mathematicians
into thinking that if the condition is true then n is prime.
Unfortunately, the ancient Chinese never tried n = 341, which is non prime (341 = 11 x 31) and yet
341 divides 2 341 = 2 with out remainder. Demonstrate that 2 341 = 2 (mod 341) (disproving theonly if condition). Hint: It is not necessary to calculate 2 341; play around with the congruences instead.
8.15 Show that if n is an odd composite integer, then the Miller-Rabin test will return inconclusive for a = 1 and a = (n 1).
8.16 If n is composite and passes the Miller-Rabin test for the base a, then n is called a strong pseudoprime to the base a. Show that 2047 is a strong pseudoprime to the base 2.
8.17 A common formulation of the Chinese remainder theorem (CRT) is as follows: Let m1,..., mk be integers that are pairwise relatively prime for 1 i, j k, and i j. Define M to be the product of all the mi's. Let a1,..., ak be integers. Then the set of congruences:
x = a1(mod m1)
x = a2(mod m2)
.
.
.
x = ak(mod mk)
has a unique solution modulo M. Show that the theorem stated in this form is true.
8.18 The example used by Sun-Tsu to illustrate the CRT was x 2(mod 3); x 3(mod 5); x 2(mod 7)
Solve for x.
8.19 Six professors begin courses on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday,
respectively, and announce their intentions of lecturing at intervals of 2, 3, 4, 1, 6, and 5 days, respectively. The regulations of the university forbid Sunday lectures (so that a Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture? Hint: Use the CRT.
8.21 Given 2 as a primitive root of 29, construct a table of discrete logarithms, and use it to solve the following congruences:
a. 17x2 = 10(mod 29)
b. 4x 16 0(mod 29)
c. x7 = 17(mod 29)
