189-235A: Basic Algebra I
Due: Wednesday, September 24.
1. Page 41, 1.48, 1.49, 1.55, 1.56 and 1.57.
(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
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