合同式に基づく古典的な素数判定法

$N=2$ のときは $(N-1)!=1$ なので、$(N-1)!\equiv -1\Mod{N}$ は明らか。

$N$ を奇素数とし、$N$ を法とする原始根をひとつとり、それを $g$ とすると、$g, g^2, \ldots, g^{N-1}=1\Mod{N}$ は $N$ を法とする既約剰余類全体と一致する。よって
$$(N-1)!\equiv \prod_{k=1}^{N-1} g^k\equiv g^{(N-1)N/2}\Mod{N}$$
となる。$N$ は奇数なので
$$(N-1)!\equiv g^{(N-1)/2}\equiv -1\Mod{N}$$
が成り立つ。

$N=4$ は合成数で $(N-1)!=6\equiv 2\Mod{N}$ だから、$(N-1)!\not\equiv -1\Mod{N}$.

$N$ が $4$ より大きい合成数のとき、$N=ab, 2\leq a, b\leq N-1$ となる $a, b$ をとる。$a\neq b$ のとき $a, b$ はともに $1, 2, \ldots, N-1$ のなかにあらわれるから
$$N=ab\mid (N-1)!$$
となる。$a=b$ のときは $N>4$ より $a=\sqrt{N}< N/2$ となるので、$a, 2a$ がともに $1, 2, \ldots, N-1$ のなかにあらわれるから
$$N=a^2\mid a\times 2a\mid (N-1)!$$
となる。よって $N$ が $4$ より大きい合成数のとき $(N-1)!\equiv 0\Mod{N}$ となる。

$N$ が素数のとき Fermatの小定理 より、
$$X^{N-1}-1\equiv 0\Mod{N}$$
はすべての既約剰余類 $1, 2, \ldots, N-1\Mod{N}$ を解にもつ。よって 多項式の合同の基礎:定理3 より
$$X^{N-1}-1\equiv (X-1)(X-2)\cdots (X-(N-1))Q(X)\Mod{N}$$
となる多項式 $Q(X)$ が存在するが、左辺は $N-1$ 次式で、最高次の係数は1だから
$$Q(X)\equiv 1\Mod{N}$$
つまり
$$X^{N-1}-1\equiv (X-1)(X-2)\cdots (X-(N-1))\Mod{N}$$
となる。$X=0$ を代入すると
$$-1\equiv (-1)^{N-1} (N-1)!\Mod{N}$$
となる。$N=2$ のとき $-1\equiv 1\Mod{2}$ となり、$N$ が奇素数のとき $(-1)^{N-1}=1$ となるから、いずれにせよ
$$-1\equiv (N-1)!\Mod{N}$$
が成り立つ。

$N$ が素数ならば、$N$ の原始根 $a$ について \eqref{eq1}, \eqref{eq2} はともに成り立つ。逆に
\eqref{eq1}, \eqref{eq2} がともに成り立つとき $N$ が素数であることを示す。

\eqref{eq1} が成り立つとき、$N$ を法とする $a$ の位数は $N-1$ の約数となる。
そこで $N$ を法とする $a$ の位数を $(N-1)/d$ とおく。
$q\mid d$ のとき $N$ を法とする $a$ の位数は $(N-1)/q$ の約数となるから
$$a^{(N-1)/q}\equiv 1\Mod{N}$$
となって、\eqref{eq2} が成り立たなくなる。よって $d$ は $N-1$ の素因数 $q$ では割り切れないから
$d=1$ つまり $N$ を法とする $a$ の位数は $N-1$ である。
Eulerの定理 より $N-1$ は $\varphi(N)$ を割り切るので、$\varphi(N)=N-1$ となる。
よって $N$ は素数である。

$N$ が素数ならば、$N$ の原始根 $a$ について \eqref{eq1}, \eqref{eq2} はともに成り立つ。

$$N-1=\prod_{i=1}^r q_i^{e_i}$$
と素因数分解し、$a_i=a(q_i)$ とおく。

各 $j=1, 2, \ldots, r$ について
$$a_j^{N-1}\equiv 1\Mod{N}$$
となるが
$$a_j^{(N-1)/q_j}\not\equiv 1\Mod{N}$$
が成り立つ。$N$ を法とする $a_j$ の位数を $d_j$ とおくと 乗法的位数の定義 で述べたように
$d_j$ は $N-1$ を割り切るが $(N-1)/q_j$ を割り切らない。
$$d_j=\prod_{i=1}^r q_i^{f_i}$$
とおくと $d_j\mid (N-1)$ より $0\leq f_i\leq e_i$ が成り立つ。$f_j\leq e_j-1$ とすると
$d_j$ は $(N-1)/q_j$ を割り切ってしまうので、$f_j=e_j$ となる。つまり $q_j^{e_j}$ は $d_j$ を割り切る。
乗法的位数:定理1 より $d_j$ は $\varphi(N)$ を割り切るから
$q_j^{e_j}$ は $\varphi(N)$ を割り切る。

これが各 $j=1, 2, \ldots, r$ について成り立つので結局 $N-1$ が $\varphi(N)$ を割り切ることになり、
$\varphi(N)=N-1$ であるから、 $N$ は素数である。

$N$ が素数ならば、$N$ の原始根 $a$ について \eqref{eq3} が成り立つ。

\eqref{eq3} が成り立つ $a$ をとり、$N$ の素因数 $p$ をひとつとると
$$\label{eq4}a^{(N-1)/2}\equiv -1\Mod{p}\tag{4})$$
も成り立つ。さらに、この両辺を$2$乗すると
$$a^{N-1}\equiv 1\Mod{p}$$
も成り立つから、$p$ を法とする $a$ の位数を $d$ とおくと $d$ は $N-1=h\times 2^n$ の約数である。
\eqref{eq4} より $d$ は $(N-1)/2=h\times 2^{n-1}$ の約数ではない。よって $d$ は $2^n$ の倍数であるから
乗法的位数:定理1 より
$$2^n\mid d\mid\varphi(p)=p-1$$
となり
$$p\equiv 1\Mod{2^n}$$
が成り立つ。とくに $p\geq 2^n+1$ が成り立つ。
$N$ が合成数ならば、$p_1 p_2\mid N$ となる素数 $p_1, p_2$ （$p_1=p_2$ であってもよい） が存在するので
$$N\geq p_1 p_2\geq (2^n+1)^2 > 2^{2n}+1>h\times 2^n+1$$
となって、矛盾するから $N$ は素数である。

$$F=\prod_{i=1}^r q_i^{e_i}$$
と素因数分解し、$a_i=a(q_i)$ とおく。
$p$ を $N$ の素因数とし、$p$ を法とする $a_i$ の位数を $d_i$ とおく。

各 $j$ について、\eqref{eq5} より $p$ は $a_j^{(N-1)/q_j}-1$ を割り切らない、つまり
$$a_j^{(N-1)/q_j}\not\equiv 1\Mod{p}$$
となるから、 定理3 の証明と同様にして
$$q_j^{e_j}\mid d_j\mid \varphi(p)=p-1$$
が成り立つ。

よって $p-1$ は $\prod_i q_i^{e_i}=F$ で割り切れる。