8.1 What is a prime number?
Get 8.1 exercise solution
8.2 What is the meaning of the expression a divides b?
Get 8.2 exercise solution
8.3 What is Euler’s totient function?
Get 8.3 exercise solution
8.4 The Miller-Rabin test can determine if a number is not prime but cannot determine if a number is prim
e. How can such an algorithm be used to test for primality?
Get 8.4 exercise solution
8.5 What is a primitive root of a number?
Get 8.5 exercise solution
8.6 What is the difference between an index and a discrete logarithm?
Get 8.6 exercise solution
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 + p1 p2...pn. That is, X is equal to one plus the product of all the primes. Can we find a 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 + p1 p2..pn.
Get 8.1 exercise solution
8.2 The purpose of this problem is to demonstrate that the probability that two random numbers are relatively prime is about 0.6.
a. Let P = Pr[gcd(a, b) = 1]. Show that P = Pr[gcd(a, b) = d] = P/d2. Hint: Consider the quantity gcd
Get 8.2 exercise solution
8.3 Why is gcd(n, n + 1) = 1 for two consecutive integers n and n + 1?
Get 8.3 exercise solution
8.4 Using Fermat’s theorem, find 3201 mod 11.
Get 8.4 exercise solution
8.5 Use Fermat’s theorem to find a number a between 0 and 72 with a congruent to 9794 modulo 73.
Get 8.5 exercise solution
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.)
Get 8.6 exercise solution
8.7 Use Euler’s theorem to find a number a between 0 and 9 such that a is congruent to 71000 modulo 10. (Note: This is the same as the last digit of the decimal expansion of 71000.)
Get 8.7 exercise solution
8.8 Use Euler’s theorem to find a number x between 0 and 28 with x85 congruent to 6 modulo 35. (You should not need to use any brute-force searching.)
Get 8.8 exercise solution
8.9 Notice in Table 8.2 that o(n) is even for n >2. This is true for all n > 2. Give a concise argument why this is so.
Get 8.9 exercise solution
8.10 Prove the following: If p is prime, then f(pi) = pi - pi-1. Hint: What numbers have a factor in common with pi?
Get 8.10 exercise solution
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, the property developed in the preceding problem, and the property that f(p) = p - 1 for p 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)
Get 8.11 exercise solution
8.12 It can also be shown that for arbitrary positive integer a, f(a) is given by
where a is given by Equation (8.1), namely: a = P1 a1 P2 a2 cPt at. Demonstrate this result.
8.13 Consider the function: f(n) = number of elements in the set {a: 0 … a 6 n and gcd(a, n) = 1}. What is this function?
Get 8.13 exercise solution
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 (2n - 2).
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.
d. Unfortunately, the ancient Chinese never tried n = 341, which is nonprime (341 = 11 * 31), yet 341 divides 2341 - 2 without remainder. Demonstrate that 2341 K 2 (mod 341) (disproving the only if condition). Hint: It is not necessary to calculate 2341; play around with the congruences instead.
Get 8.14 exercise solution
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).
Get 8.15 exercise solution
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.
Get 8.16 exercise solution
8.17 A common formulation of the Chinese remainder theorem (CRT) is as follows: Let m1,c, 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,c, ak be integers. Then the set of congruences:
has a unique solution modulo M. Show that the theorem stated in this form is true.
Get 8.17 exercise solution
8.18 The example used by Sun-Tsu to illustrate the CRT was x K 2 (mod 3); x K 3 (mod 5); x K 2 (mod 7) Solve for x.
Get 8.18 exercise solution
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.
Get 8.19 exercise solution
8.20 Find all primitive roots of 25.
Get 8.20 exercise solution
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 K 10 (mod 29)
b. x2 - 4x - 16 K 0 (mod 29)
c. x7 K 17 (mod 29)
Get 8.21 exercise solution
