素数に関する重要な定理として、Fermatが発見した合同式に関する定理がある。
$a^n (n=0, 1, 2, 3, \ldots)$ を素数 $p$ で割った余りが $n$ に対してどのように変化していくかを考えよう。
もちろん $a$ が $p$ の倍数ならば $a^n$ も $p$ の倍数だから、余りはつねに $0$ である。したがって
$a$ が $p$ の倍数でない場合が重要である。
$2^n$ を $7$ で割った余りは $1, 2, 4, 1, 2, 4, \ldots$ となり、その後 $1, 2, 4$ の繰り返しとなる。
$3^n$ を $7$ で割った余りは $1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, \ldots$ となり、その後 $1, 3, 2, 6, 4, 5$ の繰り返しとなる。
$2^n$ を $5$ で割った余りは $1, 2, 4, 3, 1, 2, 4, 3, \ldots$ となり、その後 $1, 2, 4, 3$ の繰り返しとなる。
もちろん、 $a=1$ ならば $a^n$ を $p$ で割った余りは常に $1$ である。
これらの例では、いずれもどこかで余りは $1$ となり、その後は同じパターンの繰り返しとなる。
$1$ になる場所はそれぞれ異なっている、同じ素数 $p=7$ でも $a=1, 2, 3$ でそれぞれ異なっているが、
少なくとも $p=7$ のとき $n=6$ ならば $a^n$ を $p$ で割った余りは $1$ となり、また $p=5$ のときは
$n=4$ で $a^n$ を $p$ で割った余りは $1$ になると思われる。
Fermatはこれらのことから、（$a$ が $p$ の倍数でない限り） $a^n$ を $p$ で割った余りは
$n=p-1$ で必ず $1$ になると考えた。つまり、次のことが成り立つと考えたのである。
Fermatの小定理
$p$ が素数で、 $a$ が $p$ で割り切れない整数ならば
\[a^{p-1}\equiv 1\pmod{p}\]
が成り立つ。
長年解決されなかったFermatの最終定理に対して、この定理をFermatの小定理という。
Fermatの最終定理同様、Fermatの小定理についてもFermat自身が証明を残したことは確認されておらず、
最初に証明を公表したのはEulerとされているが、Burton, History of mathematics/an introduction,
7th Ed., McGrawHill, 2011 の p.p.514-515 によればLeibnizがそれ以前に未公開の草稿の中で証明していた
ようである。
LeibnizやEulerの証明は二項係数を用いたものである。すなわち
$1\leq a\leq p-1$ ならば $\binom{p}{a}=p!/a!(p-a)!$ は（分子が $p$ の倍数だが分母が $p$ の倍数でないから）
$p$ の倍数であるから $a^p\equiv a\pmod{p}$ ならば
\[(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{1}a+1\equiv a^p+1\equiv a+1\pmod{p}\]
が成り立つことから、数学的帰納法より $a^p\equiv a\pmod{p}$ がすべての自然数 $a$ について成り立つことがわかる。
一方で、Fermatの小定理は剰余の性質から自然に証明することもできる。
初等整数論の基本定理の証明の
第5節の最後に書いた注意点から $p$ 個の整数
$0, a, 2a, 3a, \ldots, (p-1)a$ を $p$ で割った余りは
$0, 1, \ldots, p-1$ を1回ずつとる。ここから $0$ を除くと
$p-1$ 個の整数 $a, 2a, 3a, \ldots, (p-1)a$ を $p$ で割った余りは
$1, 2, \ldots, p-1$ を1回ずつとる。よって
\[(p-1)! a^{p-1}=a\times (2a)\times \cdots (p-1)a\equiv (p-1)!\pmod{p}\]
つまり
\[(p-1)! (a^{p-1}-1)\equiv 0\pmod{p}\]
となるが、となるが先述の文書内で証明したEuclidの補題から $(p-1)!$ は
$p$ と互に素なので、
$a^{p-1}-1\equiv 0\pmod{p}$
が成り立つ。
Fermatの小定理は、素数で割った余りについて触れていたが、法が素数ではないときにはどうなるか？
$3^3\equiv 3\pmod{4}, 2^{14}\equiv 4\pmod{15}$ などから、
単純に一般化した式 $a^{n-1}\equiv 1\pmod{n}$ は成り立たない（しかし、
$n$ が素数でなく、かつ $a\equiv 1\pmod{n}$ ではないにも
かかわらず、$a^{n-1}\equiv 1\pmod{n}$ が成り立つような場合はある）。
まず法が素数のべきである場合、次のような合同式が成り立つ。
Fermatの小定理の素数べきへの一般化
$p$ が素数、$e$ が正の整数で、 $a$ が $p$ で割り切れない整数ならば
\[a^{p^{e-1}(p-1)}\equiv 1\pmod{p^e}\]
が成り立つ。
実際 $a^{p-1}=Ap+1$ とおくと二項定理より
\[a^{p^{e-1}(p-1)}=(Ap+1)^{p^{e-1}}=1+Ap^e+\frac{Ap^e(p^{e-1}-1)}{2}+\cdots \equiv 1\pmod{p^e}\]
となる。
二項定理を使わず、Fermatの小定理の上記の証明を一般化した証明も可能である。
$u_k$ を $ka (0\leq k\leq p^e-1)$ を $p^e$ で割った余りとする。
$u_k$ は $0, 1, \ldots, p^e-1$ を1回ずつとる。
このうち $k$ が $p$ の倍数であるものを考える。それらは $p^{e-1}$ 個ある。
$k$ が $p$ の倍数ならば $ka$ を $p^e$ で割った余りも $p$ の倍数になるから
それらは $p^{e-1}$ 個の値 $0, p, \ldots, (p^{e-1}-1)p$ を1回ずつとる。
よって $k$ が $p$ の倍数ではないものを考えると、それらは $p^e-p^{e-1}=p^{e-1}(p-1)$ 個あり、
$u_k$ は $0, 1, \ldots, p^e-1$ のうち $p$ で割れない値を1回ずつとる。よって
\[\sideset{}{^*}\prod_k ka\equiv \sideset{}{^*}\prod_k k\pmod{p^e}\]
となる。ここで積 $\sideset{}{^*}\prod_k$ における $k$ は $0, 1, \ldots, p^e-1$ のち
$p$ で割れない数全体を走るとする。
積 $\sideset{}{^*}\prod_k k$ は $p$ で割れないから、先と同様に
\[a^{p^{e-1}(p-1)}\equiv 1\pmod{p^e}\]
が成り立つ。
なお、$p=2, e\geq 3$ のときはやや強く、 $a$ が奇数のとき
\[a^{2^{e-2}}\equiv 1\pmod{2^e}\]
が成り立つ。実際 $1^2\equiv 3^2\equiv 5^2\equiv 7^2\equiv 1\pmod{8}$ 、かつ
\[a^{2^{e-2}}-1=A\times 2^e\]
ならば
\[a^{2^{e-1}}-1=A\times 2^e(a^{2^{e-2}}+1)=A\times \frac{a^{2^{e-2}}+1}{2}\times 2^{e+1}\]
となる。
ここから、さらにFermatの小定理は一般の正の整数 $n$ にまで一般化される。
Carmichaelの関数 $\lambda(n)$ を奇素数べき $p^e$ および $p=2, e=1, 2$ に対しては
\[\lambda(p^e)=p^{e-1}(p-1),\]
$2$ の累乗 $2^e (e\geq 3)$ に対しては
\[\lambda(2^e)=2^{e-2},\]
一般の整数 $n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ （$p_1, p_2. \ldots, p_k$ は相異なる素数）
に対しては
\[\lambda(p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k})=\mathrm{LCM}[\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), \ldots, \lambda(p_k^{e_k})]\]
により定義する。
たとえば $\lambda(2)=1, \lambda(3)=\lambda(4)=\lambda(6)=\lambda(8)=2, \lambda(7)=\lambda(9)=6$ となる。
特に$\lambda(n)$ は $\prod_{i=1}^k p^{e-1}(p-1)$ の約数である。
Fermatの小定理の一般化
$n>0, a, n$ が互に素な整数ならば
\[a^{\lambda(n)}\equiv 1\pmod{n}.\]
$n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ （$p_1, p_2. \ldots, p_k$ は相異なる素数）
とおくと、先に述べたFermatの小定理の素数べきへの一般化から各 $i=1, \ldots, k$ に対して
\[a^{\lambda(p_i^{e_i})}\equiv 1\pmod{p_i^{e_i}}\]
が成り立つ。各 $\lambda(p_i^{e_i})$ は $\lambda(n)$ の約数だから
\[a^{\lambda(n)}\equiv 1\pmod{p_i^{e_i}}\]
が各 $i=1, 2, \ldots, k$ に対して成り立つ。すなわち
$a^{\lambda(n)}-1$ は各 $p_i^{e_i}$ で割り切れる。
Euclidの補題の「双対」から、$a^{\lambda(n)}-1$ は $n$ で割り切れる。
特に $n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ に対して
\[\varphi(n)=\prod_{i=1}^k p^{e-1}(p-1)\] とおくと
$\varphi(n)$ は $\lambda(n)$ の倍数だから
\[a^{\varphi(n)}\equiv 1\pmod{n}\] が成り立つ。
$\varphi(n)$ は $1, 2, \ldots, n-1$ のうち $n$ と互に素なものの個数を与える関数で（証明は省略する）、
Eulerの $\varphi$ 関数とよばれる。
素数判定との関係
Fermatの小定理から $p$ が素数で $a$ が $p$ の倍数でない整数ならば
$a^{p-1}\equiv 1\pmod{p}$ となる。
しかし、$n$ が素数でなく、かつ $a\equiv 1\pmod{n}$ ではないにも
かかわらず、$a^{n-1}\equiv 1\pmod{n}$ が成り立つような場合はある。たとえば
\[2^{340}\equiv 1\pmod{341}\]
となる。
それで、Fermatの小定理を一つの数 $a$ に対して使うだけで $p$ が素数であることを
確かめることは出来ない。複数の $a$ を使うとどうなるか？実はこの場合も、
$a$ が $n$ と互いに素である限り $a^{n-1}\equiv 1\pmod{n}$ が常に成り立つような
合成数 $n$ が存在する。たとえば $561=3\times 11\times 17$ だが
$a$ が $561$ と互いに素ならば
\[a^{560}\equiv 1\pmod{561}\]
は常に成り立つ。
もちろん $a$ が $n$ の（$1$ でも $n$ 自身でもない）約数であれば、 $a^n\equiv 1\pmod{n}$ は成り立たない。
しかし、そのような $a$ を見つけるのは結局 $n$ の $1$ でも $n$ 自身でもない約数を実際に見つけることを意味するから
素数の判定法としては、「$n$ の $1$ でも $n$ 自身でもない約数を実際に見つける」という
素朴な（かつ非常に時間のかかる）判定法に比べて簡単になっていないのである。
それにもかかわらず、Fermatの小定理は様々な素数判定法の基礎として重要であり、その他にも
数論において様々な形で用いられている。
乗法位数
\[a^e\equiv 1\pmod{n}\]
となる最小の正の整数 $e$ を $a\pmod{n}$ の乗法位数（あるいは単に位数）という。
次の重要な事実が分かる。
\[a^m\equiv 1\pmod{n}\]
ならば $m$ は $a\pmod{n}$ の乗法位数 $e$ の倍数である。
特に $a\pmod{n}$ の乗法位数は $\lambda(n)$ の約数である。
$m=qe+r, 0\leq r\leq e-1$
とおくと
\[a^m\equiv a^{qe+r}\equiv a^r\pmod{n}\]
より $a^r\equiv 1\pmod{n}$ だが、$0\leq r\leq e-1$ である。$r$ が正のとき
$r$ は $e$ より小さい正の整数となってしまい、
$e$ を $a^e\equiv 1\pmod{n}$ となる最小の正の整数としたことに矛盾する。
よって $r=0$ である。つまり $m$ は $e$ の倍数である。
ここから、たとえば次のようなことがわかる。
$x^2+1$ の素因数は $2$ または $4n+1$ の形のものでなければならない。
$p$ を $x^2+1$ の奇数の素因数とする。
そうすると $x^2\equiv -1\pmod{p}$ より $x^4\equiv 1\pmod{p}$
だから $x\pmod{p}$ の乗法位数は $4$ の約数である。しかし
$p\neq 2$だから $x^2\equiv -1\not\equiv 1\pmod{p}$ となる。よって
$x\pmod{p}$ の乗法位数は $2$ の約数ではないので、正確に $4$ であることがわかる。
Fermatの小定理より $p-1$ は $4$ の倍数なので $p$ は $4n+1$ の形の素数でなければならない。
さらに、ここから、$4n+1$ の形の素数は無限に多く存在することがわかる。
実際、$4n+1$ の形の素数 $p_1, p_2, \ldots, p_r$ を任意にとれば、
$(2p_1 p_2 \cdots p_r)^2+1$ は奇数で $p_1, p_2, \ldots, p_r$ のいずれとも互いに素なので、
先の定理から、この数の素因数は $4n+1$ の形のものであり、かつそれは $p_1, p_2, \ldots, p_r$
とは異なるものでなければならない。