费马小定理 — Lalande.

Fermat's Little Theorem.

Theorem. Let $\mathbb{G}$ be a finite group of order $m=|\mathbb{G}|$ . Then for any $g\in \mathbb{G}$ , it holds that $g^m=1$ .

Proof. $\mathbb{G}=\{g_1,g_2,...,g_m\}$ , $g\in \mathbb{G}$ . $g_i\neq g_j$ for all $i,j$ , therefore $gg_i\neq gg_j$ for all $i,j$ . With the closure property of the group $\mathbb{G}$ , $\{gg_1,gg_2,...gg_m\}$ is a permutation of $\{g_1,g_2,...,g_m\}$ . Then we have $(gg_1)(gg_2)...(gg_m)=g_1g_2...g_m$ , which could be reduced to $g^m=1$ .

We could see the similarity between the proof of Fermat's little theorem and Euler's theorem. In fact, Fermat's little theorem is the general form of Euler's theorem. Let $\mathbb{G}$ be the modulo multiplication group $(\mathbb{Z}/n)^{*}$ , one could derive the Euler's theorem.

Corollary 1

Corollary (Fermat's Little Theorem). Let $\mathbb{G}$ be a finite group of order $m$ . Then for any $g\in \mathbb{G}$ , and any integer $x$ , we have $g^x=g^{[x\mod m]}$ .

Many exponents calculation could be simplified using this corollary.

For example, if computing $5^{1000}\mod 11$ , we could see $5\in (\mathbb{Z}/11)^{*}$ since $\gcd(5,11)=1$ . Therefore $5^{1000}\mod{11}=5^{[1000\mod \varphi(11)]}\mod{11}=5^{[1000\mod{10}]}\mod{11}=1$ .

Corollary 2

Corollary (Fermat's Little Theorem). Let $\mathbb{G}$ be a finite group of order $m$ . Let $e>0$ be an integer, and define the function, $f_e:\mathbb{G}\to \mathbb{G}$ by $f_e(g)=g^e$ .

If $\gcd(e,m)=1$ , then $f_e$ is a permutation, i.e., a bijection.
Moreover, if $d=e^{-1}\mod{m}$ , then $f_d$ is the inverse of $f_e$ .

Eureka moment!

注意，我们这里介绍的是费马小定理的群论表述；事实上，其拥有一个更为广为人知的数学表述。对于任意整数 $a$ , 质数 $p$ ，有 $a^{p}\equiv a\pmod{p}$ 。

当 $\gcd(a,p)=1$ 时，我们能够由此推导出欧拉定理。

当 $\gcd(a,p)\neq 1$ 时，由于 $p$ 是质数， $a$ 一定是 $p$ 的倍数 $p|a$ . 那么显然此时 $a^p \equiv a \equiv 0\pmod{p}$ .