📂整数論

ウィルソンの定理の証明

定理 ¹

2より大きい素数$p$について、$(p-1)! \equiv -1 \pmod{p}$が成り立つ。

説明

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

証明

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

1

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

合同式での乗法の逆元: 素数$p$について$\gcd(p,a) = 1$の時、方程式$a x \equiv 1 \pmod{p}$は$0<x<p$でただ1つの解を持つ。

$\pmod{p}$の整数は必ず逆元をただ1つ持つので、$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}$$

■