Fermat's Little Theorem

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $p$ be a prime number.

Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.


Then:

$n^{p - 1} \equiv 1 \pmod p$


Corollary 1

If $p$ is a prime number, then $n^p \equiv n \pmod p$.


Corollary 2

Let $p$ be a prime number.

Then:

$n^{p - 1} \equiv \sqbrk {p \nmid n} \pmod p$

where:

$\nmid$ denotes non-divisibility
$\sqbrk \cdots$ is Iverson's convention.


Corollary 3

Let $p^k$ be a prime power for some prime number $p$ and $k \in \Z_{\gt 0}$.

Then:

$\forall n \in \Z_{\gt 0}: n^{p^k} \equiv n \pmod p$


Corollary 4

Let $p^k$ be a prime power for some prime number $p$ and $k \in \Z_{\gt 0}$.

Let $n \in \Z_{\gt 0}$ with $p \nmid n$.

Then:

$n^{p^k - 1} \equiv 1 \pmod p$


Proof 1

Consider the integer sequence $n, 2 n, 3 n, \dotsc, \paren {p - 1} n$.

Note that none of these integers is congruent modulo $p$ to any of the others.

If this were the case, we would have $a n \equiv b n \pmod p$ for some $1 \le a < b \le p - 1$.

Then as $\map \gcd {n, p} = 1$, and we can cancel the $n$, we get $a \equiv b \pmod p$ and so $a = b$.


We have that:

$\forall c \in \set {1, 2, \dotsc, p - 1}: p \nmid n \land p \nmid c$

So by Euclid's Lemma:

$p \nmid c n$

for any such $c n$, which means:

$c n \not \equiv 0 \pmod p$

Thus, each integer in the sequence can be reduced modulo $p$ to exactly one of $1, 2, 3, \ldots, p - 1$.

So $\set {1, 2, 3, \ldots, p - 1}$ is the set of Reduced Residue System modulo $p$.


So, upon taking the product of these congruences, we see that:

$n \times 2 n \times 3 n \times \dots \times \paren {p - 1} n \equiv 1 \times 2 \times 3 \times \cdots \times \paren {p - 1} \pmod p$

This simplifies to:

$n^{p - 1} \times \paren {p - 1}! \equiv \paren {p - 1}! \pmod p$

Since $p \nmid \paren {p - 1}!$, we can cancel $\paren {p - 1}!$ from both sides, leaving us with:

$n^{p - 1} \equiv 1 \pmod p$

$\blacksquare$


Proof 2

By Prime not Divisor implies Coprime:

$p \nmid n \implies p \perp n$

and Euler's Theorem can be applied.

Thus:

$n^{\map \phi p} \equiv 1 \pmod p$

But from Euler Phi Function of Prime Power:

$\map \phi p = p \paren {1 - \dfrac 1 p} = p - 1$

and the result follows.

$\blacksquare$


Proof 3

Let $\struct {\Z'_p, \times}$ denote the multiplicative group of reduced residues modulo $p$.

From the corollary to Reduced Residue System under Multiplication forms Abelian Group, $\struct {\Z'_p, \times}$ forms a group of order $p - 1$ under modulo multiplication.

By Element to Power of Group Order is Identity, we have:

$n^{p - 1} \equiv 1 \pmod p$

$\blacksquare$


Proof 4

Proof by induction over $n$.

Induction base:

$1^p \equiv 1 \pmod p$

Induction step:

Assume $n^p \equiv n \pmod p$

\(\ds \paren {n + 1}^p\) \(=\) \(\ds \sum_{k \mathop = 0}^p {p \choose k} n^{p - k} \cdot 1^k\) Binomial Theorem
\(\ds \forall k: 0 < k < p: \, \) \(\ds {p \choose k}\) \(\equiv\) \(\ds 0 \pmod p\) Binomial Coefficient of Prime

and so:

\(\ds \sum_{k \mathop = 0}^p {p \choose k} n^{p - k}\) \(\equiv\) \(\ds n^p + n^0 \pmod p\)
\(\ds \) \(\equiv\) \(\ds n^p + 1 \pmod p\)
\(\ds \) \(\equiv\) \(\ds n + 1 \pmod p\) Induction Step

Dividing by $n$:

$\forall n: n^p \equiv n \pmod p \implies n^{p - 1} \equiv 1 \pmod p$

$\blacksquare$


Examples

$12$ Divides $n^2 - 1$ if $\gcd \set {n, 6} = 1$

$12$ divides $n^2 - 1$ if $\gcd \set {n, 6} = 1 \implies 12 \divides n^2 - 1$


Also known as

Some sources call this Fermat's Theorem, but it needs to be appreciated that this may cause confusion with Fermat's Last Theorem.


Also defined as

Some sources refer to the corollary $n^p \equiv n \pmod p$ as Fermat's little theorem and from it derive this result.


Source of Name

This entry was named for Pierre de Fermat.


Historical Note

Fermat's Little Theorem was first stated, without proof, by Pierre de Fermat in $1640$.

Chinese mathematicians were aware of the result for $n = 2$ some $2500$ years ago.


The appearance of the first published proof of this result is the subject of differing opinions.

Some sources have it that the first published proof was by Leonhard Paul Euler $1736$.
Others state that it was first proved by Gottfried Wilhelm von Leibniz in an undated manuscript, and that he may have known a proof before $1688$, perhaps as early as $1683$.
MathWorld's page on the subject reports the first published proof as being by Leonhard Paul Euler $1749$, but it is possible this has been conflated with the proof for Fermat's Two Squares Theorem.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Fermat%27s_Little_Theorem&oldid=605979"