This assignment is due next Thursday (10/1) but start it over the weekend so we can discuss it some on Tuesday.

1. Compute

   	1237894276541 (mod 101)
   

   The numbers are too large for your calculator. There are some programming languages that will do the computation. But you should be able to figure it out by hand in a few minutes, using a little long division and Fermat's (Little) Theorem.

2. Prove or disprove:

   1. If gcd(a,b) = gcd(a,c) = 1 then gcd(a,bc) = 1.

   2. If a == 1 (mod b) and a == 1 (mod c) then a == 1 mod(bc).

      (I'll write "==" for "is congruent to" since the triple equal sign isn't easily available in html.)

   3. If gcd(b,c) = 1 and a == 1 (mod b) and a == 1 (mod c) then a == 1 mod(bc).

   4. If a == 1 (mod b) and a == 1 (mod c) then a == 1 mod(bc).

3. 1. Compute

      	2560 (mod 561)
      

      Warning: 561 isn't prime. (Since the sum of the first and last digits equals the middle digit one factor is obvious).

   2. Suppose gcd(a,561) = 1. Compute

      	a560 (mod 561)
      

      Hint. Use the answer to question 2 even if you couldn't do that question.

   3. State the converse to Fermat's Little Theorem. Is it true?

   4. What are Carmichael numbers?

4. We have proved Fermat's Little Theorem three or four ways. For each of them, find the place in the proof where you need the hypothesis that n is prime, and show how the proof fails when it's not.

5. Fermat's Litte Theorem says that for an odd prime p, a ^p-1 == 1 (mod p) when gcd(a,p) = 1.

   Say as much as you can about a^(p-1)/2 (mod p).

   I'm looking for conjectures of increasing sophistication, proofs where you can manage them.

Katie

The converse to Fermat I'd like you to think about is

    if gcd(a,p) = 1 implies a^p-1 == 1 (mod p)
    then p is prime

Ethan

 > From: Katie Byers 
 > To: eb@cs.umb.edu
 > Subject: Re: hw3
 > Date: Wed, 30 Sep 2009 13:13:46 -0400 (EDT)
 > 
 > Hi, Ethan.
 > 
 > Quick question on the HW. I'm having trouble figuring out the exact converse of Fermat's Little Theorem, because there are two suppositions in the original. Do both of them become the conclusions? Only one? Which one? My possible options seem to be:
 > 
 > If a^p-1 == 1 (mod p), for some a and p where (a,p)=1, then p is a prime.
 > 
 > If a^p-1 == 1 (mod p) for some prime p, then (a,p)=1.
 > 
 > If a^p-1 == 1 (mod p), then p is a prime and (a,p)=1.
 > 
 > I'm inclined to go with the third one, because the (a,p)=1 part
seems to follow almost directly from p being prime (when p is prime,
(a,p)=1 just means that a isn't a multiple of p; we already knew this
because if it were, no power of a could ever == anything other than 0
(mod p)). 
 > 
 > Just wanted to make sure, though, before I spend a lot of time
trying to prove/disprove the statement. (The good news is -- and this
is the other reason I'm leaning towards the third reading -- that 561
is a nice counterexample if either #1 or #3 is correct). 
 > 
 > Thanks,
 > Katie
 >