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$.
注意，我们这里介绍的是费马小定理的群论表述；事实上，其拥有一个更为广为人知的数学表述。对于任意整数 $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}$.