📂整数論

ウィルソンの定理の証明

定理¹

2より大きい素数$p$に対して、$(p-1)! \equiv -1 \pmod{p}$

説明

フェルマーの小定理ほどではないにしても、ウィルソンの定理もあちこちで有用に使われる。その見た目からして、連続する数の積を計算するときに便利な形をしている。

証明

$\pmod{p}$における乗法逆元の存在性・一意性を利用した証明1と、原始根^{primitive root}の性質とフェルマーの小定理を利用した証明2の二つを紹介する。証明2の方が少し難しいが、少し洗練されている。好みに合う証明を身につけておこう。

原始根の性質を利用した証明 1

$i$が1より大きく$(p-1)$より小さい整数だとすると、$(p-1)!$を以下のように表すことができる。 $$ (p-1)! = 1 \cdot 2 \cdot 3 \cdots i \cdots (p-2) \cdot (p-1) $$

合同式における乗法逆元: 整数環$\mathbb{Z}_{p}$は$p$が素数ならば整数体である。言い換えれば、$\gcd(p,a) = 1$ならば方程式$a x \equiv 1 \pmod{p}$は$0<x<p$でただ一つの解を持つ。

整数は$\pmod{p}$で必ずただ一つの逆元を持つので、$1$と$(p-1)$を除くすべての整数は他のある整数と掛け合わされて$1$になるはずである。$p$は偶数でない素数なので、このような$i$はちょうど偶数個存在し、結局残るのは $$ (p-1)! \equiv 1 \cdot 1 \cdot 1 \cdots 1 \cdot (p-1) \pmod{p} $$ である。$(p-1) \equiv -1 \pmod{p}$なので、$(p-1)! \equiv -1 \pmod{p}$が成り立つ。

■

例えば$(7-1)! \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \pmod{7}$を見ると $$ 2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} \\ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7} $$ なので $$ (7-1)! \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv 6 \equiv -1 \pmod{7} $$ となる。もう少し大きい素数をいくつか実際に手で計算してみれば、確実に感覚がつかめるだろう。

フェルマーの小定理を利用した証明 2

$a$を素数$p$の原始根だとすると、$(p-1)!$を以下のように表すことができる。

$$ \begin{align*} (p-1)! & \equiv 1 \cdot 2 \cdot 3 \cdots (p-2) \cdot (p-1) \pmod{p} \\ & \equiv a^{1} \cdot a^{2} \cdot a^{3} \cdots a^{p-2} \cdot a^{p-1} \pmod{p} \\ & \equiv a^{{p(p-1)} \over {2}} \pmod{p} \\ & \equiv a^{ { {p-1} \over 2 } p } \pmod{p} \end{align*} $$

フェルマーの小定理: $a^{p-1} \equiv 1 \pmod{p}$

$a$は$p$の原始根なので、フェルマーの小定理により$a^{ { {p-1} \over 2 } p } \equiv (-1)^p \pmod{p}$が成り立つ。一方、$p$は2より大きい素数なので奇数であり、したがって次を得る。 $$ (p-1)! \equiv (-1)^p \equiv -1 \pmod{p} $$

■