189-235A: Basic Algebra I

Assignment 3

Due: Wednesday, September 24.

1. Page 41, 1.48, 1.49, 1.55, 1.56 and 1.57.

2. (Fermat's little theorem and primality testing).

a) Show that p is prime if and only if p divides the binomial coefficient (p/k) for all p > k >0 .
b) Show that if p is prime, then a^p= a (mod p) for all integers a. This is known as Fermat's little theorem.
c) Show that if n=1729, then a^n=a (mod n) for all a, even though n is not prime. Hence the converse to b) is not true. An integer which is not prime but still satisfies a^n= a (mod n) for all a is sometimes called a strong pseudo-prime, or a Carmichael number. It was shown only three years ago by A. Granville that there are infinitely many Carmichael numbers. Incidentally, the integer 1729 is aloso:wq of Hardy's taxicab, and Ramanujan noted that it is remarkable for other reasons as well.