| 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. Define X = 1 +p1p2...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? What can you say about m? Deduce that the total number of primes cannot be finite. Show that pn+1  1 + p2...pn.
|
|
[Page 255] |
| 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 The sum of the result of part (a) over all possible values of d is 1. That is:  . Use this equality to determine the value of P. Hint: Use the identity .
|
| 8.3 | Why is gcd(n,n +1) = 1 for two consecutive integers n and n + 1? |
| 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 71000 modulo 10. (Note that this is the same as the last digit of the decimal expansion of 71000.) |
| 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.) |
| 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 pi1. Hint: What numbers have a factor in common with pi? |
| 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 for p prime, it is straightforward to determine the value of f(n) for any n. Determine the following: f(41) f(27) f(231) f(440)
|
| 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:  . Demonstrate this result. |
| 8.13 | Consider the function: f(n) = number of elements in the set {a: 0 n and gcd(a,n) = 1}. What is this function? |
| 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). Give an example that satisfies the condition using an odd prime. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime (proving the if condition) 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 nonprime (341 = 11 x 31) and yet 341 divides 2341 2 with out remainder. Demonstrate that 2341  2 (mod 341) (disproving the Hint: It is not necessary to calculate 2341; play around with the congruences instead.
|
|
[Page 256] |
| 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 j i  M to be the product of all the mi's. Let a1,..., ak be integers. Then the set of congruences: x m1) x m2) 
x 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); 3(mod 5); 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.20 | Find all primitive roots of 25. |
| 8.21 | Given 2 as a primitive root of 29, construct a table of discrete logarithms, and use it to solve the following congruences: 17x2 10(mod 29) 0(mod 29) 17(mod 29)
|
