**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.