1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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


    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


    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


    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?

  9. Feb 22, 2008 #8


    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Fermat's little theorem
  1. Fermat Little Theorem? (Replies: 10)