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