# 189-235A: Basic Algebra I

## 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 four years ago by A. Granville that there are infinitely many Carmichael numbers. Incidentally, the integer 1729 is also famous for the story of Ramanujan and Hardy's taxicab; see ``A mathematician's Apology" by G.H. Hardy.

3. Consider the set of all numbers of the form a+b sqrt(-5) where a and b are integers. A number of this form is called prime if its only divisors are (up to sign) 1 and itself.

a) Show that the numbers 2,3, 1+sqrt(-5) and 1-sqrt(-5) are prime in this sense.

b) Show that 6 can be factored as a product of primes, but that this factorization is not unique; hence the fundamental theorem of arithmetic fails for these numbers.