# Homework Help: Fermat's little theorem

1. Feb 21, 2008

### kingwinner

1st question:
Fermat's little theorem: If p is prime and p does not divide a, a E Z, then ap-1 is congruent to 1 mod p.

Corollary: For all a E Z and all primes p, ap is congruent to a mod p.

I don't really understand the corollary part, why is the assumption "p does not divide a" removed?

I can see why Corollary => Fermat's little theorem,
but I can't see why Fermat's little theorem => Corollary

2nd question:
(i) p does not divide a
(ii) a and p are relatively prime
Are (i) and (ii) equivalent? (i.e. (i)=>(ii) and (ii)=>(i) )

Can someone help? Thanks!

2. Feb 22, 2008

### StatusX

If p does divide a, then a=0 mod p, so the congruence is trivial. And those two statements are equivalent (assuming p is a prime, as I'm assuming you are assuming).

3. Feb 22, 2008

### kingwinner

Why is ap is congruent to a mod p trivial if p does divide a? Sorry, I can't see your point...

4. Feb 22, 2008

### morphism

Because both sides are zero.

5. Feb 22, 2008

### kingwinner

OK, I got it! :)

Any idea about my 2nd question?

6. Feb 22, 2008

### morphism

Like StatusX said, if p is a prime, then they are equivalent.

7. Feb 22, 2008

### kingwinner

I thought StatusX said that Fermat's little theorem and the Corollary are equivalent, my bad...

2nd question: So, why does p have to be a prime for them to be equivalent and why are they equivalent?

Thanks!

8. Feb 22, 2008

### StatusX

Sorry, that was a little unclear.

The condition that two numbers are relatively prime means that they have no common divisors (I'll ignore 1 as a divisor). The only divisor of a prime p is p itself, so p can only have a common divisor with n if p is a divisor of n, ie, p divides n. On the other hand, composite numbers n and m can have common divisors even if one doesn't divide the other, eg, 6 and 8 have 2 as a common divisor.