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
    Definition/Summary

    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

    Equations

    [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.

    Theorem
    Let a and p be coprime, then

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

    Proof
    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.

    Remark
    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.



    Corollary
    Let [itex]p[/itex] be a prime and [itex]a[/itex] any integer, then [itex]a^p \equiv a\ (p)[/itex].
    Proof
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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



Similar Discussions: What is Fermat's little theorem
  1. Fermat's Last Theorem (Replies: 3)

Loading...