Wilsonの定理（高校数学）

方針：$x^2-1$ を因数分解し、素数が積を割るときの性質を使う。
段 1（⇐）。$x\equiv\pm1$ なら $x^2\equiv(\pm1)^2=1$ である。
段 2（⇒）。$x^2\equiv1$ とすると、$p$ は $x^2-1=(x-1)(x+1)$ を割る。$p$ は素数なので、合同式の割り算と逆元 の系「素数を法とする積が 0 と合同なら」により、$p$ は $x-1$ か $x+1$ を割る。前者なら $x\equiv1$、後者なら $x\equiv-1$ である。
段 3（$1$ から $p-1$ までの数）。$x\equiv1$ となるのは $x=1$、$x\equiv-1$ となるのは $x=p-1$ だけである。$p=2$ では $1$ と $p-1$ は同じ数 $1$ である。$\square$

方針：rem-wlhs-inverse で数と逆元を結び、lem-wlhs-square-one で自分自身と結ばれる数を除く。
段 1（逆元は同じ範囲にある）。$2\le a\le p-2$ とする。rem-wlhs-inverse により、$a$ の逆元 $a'$ が $1$ から $p-1$ までにただ 1 つある。$a'=1$ なら $1\equiv aa'=a$ となり、$a'=p-1\equiv-1$ なら $1\equiv aa'\equiv-a$ から $a\equiv-1$ となって、どちらも $2\le a\le p-2$ に反する。よって $2\le a'\le p-2$ である。
段 2（$a\ne a'$）。$a'=a$ なら $a^2\equiv1$ で、lem-wlhs-square-one により $a=1$ か $a=p-1$ となり、$2\le a\le p-2$ に反する。よって $a'\ne a$ である。
段 3（組に分ける）。$a'$ の逆元は $a$ なので、$a$ と $a'$ は互いに相手を指す。$2$ から $p-2$ までの数を、それぞれ自分の逆元と結ぶと、どの数もちょうど 1 つの組 $\{a,a'\}$ に入り、各組は相異なる 2 数からなる。$p-3$ 個の数が 2 個ずつの組に分かれるので、組の数は $\frac{p-3}2$ である（$p$ は奇数なので $p-3$ は偶数）。$\square$

方針：⇒ は、lem-wlhs-pairing の組ごとに積をとる。⇐ は対偶を示す。$n$ が素数でなければ、$n$ の約数 $a$（$2\le a\le n-1$）が $(n-1)!$ と $(n-1)!+1$ の両方を割ることになり、矛盾する。
段 1（⇒、$p=2,3$）。$p=2$ では $1!=1\equiv-1\pmod2$、$p=3$ では $2!=2\equiv-1\pmod3$ である。
段 2（⇒、$p\ge5$）。$(p-1)!$ を
$$ (p-1)!=1\cdot\underbrace{\bigl(2\cdot3\cdots(p-2)\bigr)}_{\text{組に分ける}}\cdot(p-1) $$
と分ける。lem-wlhs-pairing により、真ん中の $p-3$ 個の数は、積が $1$ と合同になる $\frac{p-3}2$ 個の組に分かれる。掛ける順番を組ごとに並べかえると、真ん中の積は $1$ を $\frac{p-3}2$ 回掛けたものと合同で、$1$ と合同である。よって
$$ (p-1)!\equiv1\cdot1\cdot(p-1)=p-1\equiv-1\pmod p $$
である。
段 3（⇐：$n$ が素数でない場合）。$n\ge2$ が素数でないとすると、$n$ は $1$ と $n$ 以外の正の約数 $a$ をもち、$2\le a\le n-1$ である。$a$ は $1$ から $n-1$ までの数の 1 つなので、$(n-1)!$ の因数に含まれ、$a$ は $(n-1)!$ を割る。もし $(n-1)!\equiv-1\pmod n$ なら、$n$ は $(n-1)!+1$ を割り、$a$ は $n$ を割るので、$a$ も $(n-1)!+1$ を割る。すると $a$ は差 $\bigl((n-1)!+1\bigr)-(n-1)!=1$ を割ることになり、$a\ge2$ に反する。よって $(n-1)!\not\equiv-1\pmod n$ である。対偶をとって ⇐ を得る。$\square$

方針：$n=ab$ と分け、$a$ と $b$（または $a$ と $2a$）が $1$ から $n-1$ までの相異なる数として $(n-1)!$ に現れることを示す。
段 1（$n=4$）。$3!=6=4+2$ なので $3!\equiv2\pmod4$ である。
段 2（$n>4$ で $n=ab$、$2\le a< b$ と書ける場合）。$b=\frac na\le\frac n2< n$ なので、$a$ と $b$ は $1$ から $n-1$ までの相異なる数である。$(n-1)!$ は $a$ と $b$ を別々の因数として含むので、$ab=n$ で割り切れる。
段 3（$n>4$ で段 2 のように書けない場合）。$n$ は素数でないので $n=ab$、$2\le a\le b$ と書ける。段 2 のように書けないなら $a=b$ で、$n=a^2$ である。$n>4$ なので $a\ge3$ である。$a$ と $2a$ は相異なり、$a\ge3$ から $2a< a\cdot a=n$ なので、どちらも $1$ から $n-1$ までの数である。$(n-1)!$ は $a$ と $2a$ を別々の因数として含むので、$a\cdot2a=2n$ で割り切れ、特に $n$ で割り切れる。$\square$

方針：$(p-1)!$ の因数を $k$ と $p-k$ の組に並べかえ、$p-k\equiv-k$ を使って $(p-1)!$ を $x^2$ で書く。そこに thm-wlhs-main を使う。
段 1（組に並べる）。$h=\dfrac{p-1}2$ とおく。$1$ から $p-1$ までの数は、$k$ と $p-k$（$k=1,2,\dots,h$）の $h$ 組に分かれる。$k\le h$ なら $p-k\ge p-h=h+1$ なので、組は重ならない。よって
$$ (p-1)!=\prod_{k=1}^{h}k\,(p-k) $$
である。
段 2（$p-k\equiv-k$ を使う）。$p-k\equiv-k\pmod p$ なので
$$ (p-1)!\equiv\prod_{k=1}^{h}k\cdot(-k)=(-1)^h\bigl(1\cdot2\cdots h\bigr)^2=(-1)^h\,x^2\pmod p $$
である。
段 3（$h$ は偶数）。$p=4m+1$ と書けるので $h=2m$ は偶数で、$(-1)^h=1$ である。段 2 と thm-wlhs-main から $x^2\equiv(p-1)!\equiv-1\pmod p$ を得る。$\square$

方針：Fermat の小定理 $x^{p-1}\equiv1$ と、$x^2\equiv-1$ から出る $x^{p-1}\equiv-1$ を比べる。
$x^2\equiv-1$ となる $x$ があったとする。$p$ が $x$ を割るなら $x^2\equiv0\not\equiv-1$ なので、$p$ は $x$ を割らない。Fermat の小定理により $x^{p-1}\equiv1\pmod p$ である。一方 $h=\dfrac{p-1}2$ は奇数なので（$p=4m+3$ なら $h=2m+1$）、
$$ x^{p-1}=(x^2)^h\equiv(-1)^h=-1\pmod p $$
である。2 つを合わせると $1\equiv-1$、つまり $p$ が $2$ を割ることになり、$p\ge3$ に反する。$\square$