1. Limited time only! Sign up for a free 30min personal 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!

What is Fermat's little theorem

  1. Jul 23, 2014 #1

    Fermat's little theorem states that if [itex]p[/itex] is a prime number, then for any integer [itex]a[/itex], [itex]a^{p}-a[/itex] will be divisible by


    [tex]a^{p-1}\equiv1\pmod p \quad (\text{for\ }a \not\equiv 0 \pmod p)[/tex]

    [tex]a^p\equiv a\pmod p[/tex]

    Extended explanation

    Fermat's Little Theorem
    If p is a prime number and a an integer, then
    [tex]a^p\equiv a\ (p)[/tex]

    In order to prove Fermat's Little theorem, we will start by proving a superficially slightly weaker result, which is also referred to as Fermat's Little Theorem, on occasion. The two results imply each other, however.

    Let a and p be coprime, then

    [tex]a^{p-1}-1 \equiv 0\ (p).[/tex]

    Start by listing the first p-1 positive multiples of a:

    [tex]a, 2a, 3a, \ldots, (p -1)a[/tex]

    Suppose that [itex]ra[/itex] and [itex]sa[/itex] are the same modulo [itex]p[/itex], with [itex]0 <r,s < p[/itex]. Since [itex]a[/itex] is nonzero mod [itex]p[/itex], we can cancel, giving [itex]r \equiv s\ (p)[/itex]. So the [itex]p-1[/itex] multiples of [itex]a[/itex] above are distinct and nonzero; that is, they must be congruent to [itex]1, 2, 3, \ldots, p-1[/itex] in some order. Multiply all these congruences together and we find

    [tex]a2a3a\ldots (p-1)a \equiv 1.2.3\ldots(p-1)\ (p)[/tex]

    or better,

    [tex]a^{p-1}(p-1)! \equiv\ (p-1)! (mod p)[/tex].

    Divide both side by (p-1)! to complete the proof.

    This result can be proven by appeal to Lagrange's theorem, since the non-zero residues form a group modulo [itex]p[/itex]. Although we haven't proven, they are a group, we are explicitly using that multiplicative inverses modulo [itex]p[/itex] exist, which is an elementary application of Euclid's algorithm.

    Let [itex]p[/itex] be a prime and [itex]a[/itex] any integer, then [itex]a^p \equiv a\ (p)[/itex].
    The result is trival (both sides are zero) if [itex]p[/itex] divides [itex]a[/itex]. If not then we need only multiply the congruence in Fermat's Little Theorem by [itex]a[/itex] to complete the proof.

    * This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted