Menu
Home
My entries
Defined browse
Select

Then Select

Then Select

Search

 

Fermat's little theorem

Edit

Edit
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

Edit
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]

Edit
Scientists
Pierre de Fermat (1601?-1665)

Recent forum threads on Fermat's little theorem
 
Edit
Breakdown
Mathematics
> Number Theory
>> Congruences

Edit
See Also
Wikipedia
Mathworld

Edit
Images

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

Commentary

matt grime @ 10:45 AM Jun8-08
Done the tex'ing. Removed (unneccessary and unused) reference to there being a minimal d with some property. Made it clearer what each 'proof' was proving.

Gokul43201 @ 12:37 PM May24-08
Definition amended

Gokul43201 @ 05:30 PM May22-08
Error in definition - fixed now, but it's still only the weaker form.