Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Fermat's little theorem

  1. Feb 21, 2008 #1
    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. jcsd
  3. Feb 22, 2008 #2

    StatusX

    User Avatar
    Homework Helper

    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).
     
  4. Feb 22, 2008 #3
    Why is ap is congruent to a mod p trivial if p does divide a? Sorry, I can't see your point...
     
  5. Feb 22, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Because both sides are zero.
     
  6. Feb 22, 2008 #5
    OK, I got it! :)

    Any idea about my 2nd question?
     
  7. Feb 22, 2008 #6

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Like StatusX said, if p is a prime, then they are equivalent.
     
  8. Feb 22, 2008 #7
    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!
     
  9. Feb 22, 2008 #8

    StatusX

    User Avatar
    Homework Helper

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook