费马小定理证明

Modulo Arithmetic : Fermat's Little Theorem and some miscellaneous theorems

Previous Part

I'm sure you've heard about Fermat's Last Theorem.

Fermat's Little Theorem states that

Let $p$ be a prime and let $a$ be a positive integer. Then,

$a^p \equiv a \pmod{p}$.

Equivalently, if $p \nmid a$, we can write it as

$a^{p - 1} \equiv 1 \pmod{p}$, by dividing both sides by $a$.

Calm down. Since $p$ is a prime and $p \nmid a$ means that $\gcd(p, a) = 1$. So, we can divide both sides by $a$.

So, how does this seemingly bizarre theorem true? There're many proofs of this theorem. (You can find some of them here)

We'll show a proof using the following fact :

If $p$ is a prime and $p \nmid x$, then the $(p - 1)$ numbers

$x, 2x, 3x, ..., (p - 1)x$ are distinct in $\mathbb{Z}_p$. (i.e. their remainders when divided by $p$ are distinct)

Indeed, this is easy to proof. Suppose not, then let $ux \equiv vx$ for some distinct $u, v \in \{1, 2, ..., p - 1\}$. Then, we have $(u - v)x \equiv 0 \pmod{p}$. Since $\gcd(x, p) = 1$, we can divide both sides by $p$ to get $u - v \equiv 0 \pmod{p}$ or $u \equiv v \pmod{p}$. But this implies $u = v$, a contradiction.

Now, since their remainders are distinct, we can say that the sets

$\{x, 2x, 3x, ..., (p - 1)x\}$ and $\{1, 2, 3, ..., p - 1\}$ are equal modulo $p$.

So, the product of their elements must be equal modulo $p$, or

$(p - 1)!x^{p - 1} \equiv (p - 1)! \pmod{p}$.

But evidently, $\gcd((p - 1)!, p) = 1$. So, we can divide both sides by $(p - 1)!$ to get

$x^{p - 1} \equiv 1 \pmod{p}$.

This proves the theorem. $\blacksquare$.

Some other theorems

Wilson's Theorem

Wilson's Theorem states that if $p$ is a prime then

$(p - 1)! \equiv -1 \pmod{p}$.

Note that the converse is not true!

Euler's Theorem

This is just a generalization of Fermat's Little Theorem. It states that

For every positive integer $n$ and $a$ such that $\gcd(a, n) = 1$,

$a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is the Euler's totient function.

Since $\phi(p) = p - 1$, this theorem is in fact a generalization of Fermat's Little Theorem.

Fermat's Little Theorem (FLT), named as it is to distinguish it from Fermat's Last Theorem, is a very important theorem in number theory. FLT states the following:

If $p$ is a prime and $p$ does not divide $a$, then: $$a^{p-1}\equiv 1 \pmod{p}$$

This is by no means an obvious theorem, although you may have observed it if you play around with computing powers of numbers. For example, you may have noticed that all perfect $4$th powers can only end in the digits $0$, $1$, $5$, and $6$. This is a direct consequence of FLT.

To prove FLT, consider the set ${a, 2a, 3a, ..., (p-1)a}$. We will prove that this set is a complete residue class modulo $p$, meaning that it contains every remainder modulo $p$ except $0$ exactly once.

It is clear that none of the elements in the set is congruent to $0$ modulo $p$. Assume, for the sake of contradiction, that $ai\equiv aj \pmod{p}$ for $0\lt j\lt i\lt p$. Then, $a(i-j)\equiv 0 \pmod{p}$, which is a contradiction. Therefore, all of the elements ${a, 2a, 3a, ..., (p-1)a}$ are distinct modulo $p$. Thus, since these $p-1$ elements can only occupy $p-1$ residue classes, each residue class must be occupied exactly once.

Since ${a, 2a, 3a, ..., (p-1)a}$ is a complete residue class, it follows that: $$a \times 2a \times 3a \times ... \times (p-1)a \equiv 1\times 2\times 3\times ... \times(p-1) \pmod{p}$$ $$a^{p-1}(p-1)!\equiv (p-1)! \pmod{p}$$ Since $(p-1)!$ is relatively prime to $p$, we may divide by $(p-1)!$ in the above congruence to obtain: $$a^{p-1}\equiv 1 \pmod{p}$$ Thus, we have proved FLT.

An alternative statement of FLT states that, for a prime $p$ and any integer $a$, $$a^p\equiv a \pmod{p}$$

One way to prove this is to use induction. Note that, for $a=0$, $0^p\equiv 0 \pmod{p}$ is trivial. Now, assume that $a^p\equiv a \pmod{p}$. We will prove that $(a+1)^p\equiv a+1 \pmod{p}$.

By the Binomial Theorem, $$(a+1)^p = a^p + \binom{p}{p-1}a^{p-1} + \binom{p}{p-2}a^{p-2} + ... + 1$$ It is easy to show that $\binom{p}{x}$ is divisible by $p$ for all $1\le x\le p-1$. Therefore, $$(a+1)^p \equiv a^p + 1 \pmod{p}$$ $$(a+1)^p \equiv a+1 \pmod{p}$$ This completes the induction.

Fermat's Little Theorem

Fermat's Little Theorem (FLT) is as follows:

$a)$ For a $p$ and any integer $a,$ $$a^p \equiv a \pmod{p}$$

$b)$ Furthermore, if $p \nmid a,$ then $$a^{p-1} \equiv 1 \pmod{p}$$

In this explanation we will prove part $a)$ of Fermat's Little Theorem by mathematical induction.

Base case

The base case where $a = 1$ is easy to check. Indeed, $$1^{p} \equiv 1 \pmod{p}$$

Inductive Hypothesis

Now, fix a prime $p,$ and suppose that for some integer $a,$ $$a^p \equiv a \pmod{p}$$

Inductive Step

We want to show that: $$(a+1)^p \equiv (a+1) \pmod{p}$$

By the binomial theorem, we know that: $$(a+1)^p = a^p + \binom{p}{1} a^{p-1} + \binom{p}{2} a^{p-2} + \cdots + \binom{p}{p-1} a + 1.$$

Remember that $\binom{p}{k} = \dfrac{p!}{(p-k)!k!}.$ Thus, for all $0 < k < p,$ we can see that $p \mid \binom{p}{k}.$ Equivalently, for all $0 < k < p,$ $\binom{p}{k} \equiv 0 \pmod{p}.$

$\\$

So, $$\begin{align} (a+1)^p &= a^p + \binom{p}{1} a^{p-1} + \binom{p}{2} a^{p-2} + \cdots + \binom{p}{p-1} a + 1\\ \iff (a+1)^p &\equiv a^p + 0 + 0 + \cdots + 0 + 1 \pmod{p}\\ \iff (a+1)^p &\equiv a^p + 1 \pmod{p}\\ \end{align}$$

But by our inductive hypothesis, $a^p \equiv a \pmod{p}.$ So, $$\begin{align} (a+1)^p &\equiv a^p + 1 \pmod{p}\\ \iff (a+1)^p &\equiv a + 1 \pmod{p} \end{align}$$

That concludes the proof by induction. To prove part $b)$ of Fermat's Little Theorem, simply divide both sides of $a^p \equiv a \pmod{p}$ by $a.$ This is only valid when $p \nmid a.$