2014/05/30

ウィルソンの定理とその2通りの証明

分野: 整数問題  レベル: 数学オリンピック

ウィルソン(Wilson)の定理:
正の整数 $p$ について,
$p$ が素数 $\iff (p-1)!\equiv -1 \:\mathrm{mod}\:p$


入試や数学オリンピックで見かける機会は少ないですが,合同式を扱うよい練習になります。

ウィルソンの定理

$p$ が合成数のとき,$2$ から $p-1$ の中には $p$ の約数が含まれているので,$(p-1)!$ を $p$ で割った余りはその約数の倍数です。つまりウィルソンの定理の右から左(の対偶)が分かります。

重要なのは左から右です。
実際に $p$ が小さい場合に実験してウィルソンの定理の主張を確認してみます。


$p=2 → 1\equiv -1\:\mathrm{mod}\:2\\
p=3 → 2\equiv -1\:\mathrm{mod}\:3\\
p=5 → 24\equiv -1\:\mathrm{mod}\:5\\
p=7 → 720\equiv -1\:\mathrm{mod}\:7$

合同式に慣れていない人は合同式の意味とよく使う6つの性質を参考にしてください。
以下 $\:\mathrm{mod}\:p$ の表記を省略します。

ウィルソンの定理の証明では特に,合同式の性質:
「 $ab\equiv ac$ で,$a$ と $p$ が互いに素なら $b\equiv c$ 」
が重要になります。

以下ではウィルソンの定理の証明を2通り解説します。

ウィルソンの定理の証明1

$n$ が小さい場合に証明しようとすれば自然に出てくる発想です。
$(7-1)!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\\
=(5\cdot 3)(4\cdot 2)\cdot 1\cdot 6\equiv 6=-1\:\mathrm{mod}\:7$

方針:$p-3$ 個の数 $2,3,\cdots,p-2$ を2つずつペアにして消していきます。そのために,$m$ を固定して $mn\equiv 1$ となるような相方 $n$ を探します。そのときに整数の有名な性質「 $m,2m,3m\cdots,(p-1)m$ を $p$ で割った余りはすべて異なる」が使えます。(この性質の証明は一次不定方程式ax+by=cの整数解の「ax+by=1についての証明」の下側参照)

証明

$p=2$ のときは成立。以下 $p\geq 3$ の場合について考える。

$m,2m,3m\cdots,(p-1)m$ を $p$ で割った余りはすべて異なるので,
$mn\equiv 1$ となる $n$ が $1$ から $p-1$ の間にただ1つ存在する(注1)。
そのような $n$ が,$m$ と等しい場合は困るのでそのような良くない場合を探す:
$m^2\equiv 1$
つまり,$(m-1)(m+1)\equiv 0$
合同式の性質より $m-1\equiv 0$ または $m+1\equiv 0$
よって,$m\neq 1,p-1$ のときは $m\neq n$ となる。
よって,$2,3,\cdots p-2$ の中でそのような $m$ と $n$ のペアを $\dfrac{p-3}{2}$ 個作ることにより,
$(p-1)!\equiv 1^{\frac{p-3}{2}}\cdot 1\cdot (p-1)$
が分かりウィルソンの定理が示された。

注1:群論の言葉を使えば「 $p$ の剰余群の任意の元が逆元を持つ」と簡潔に表現できます。

ウィルソンの定理の証明2

方針:フェルマーの小定理を用います。発想力が必要なエレガントな証明です。

証明

フェルマーの小定理より,$x=1,2,\cdots,p-1$ に対して,
$f(x)=x^{p-1}-1\equiv 0$
よって,剰余の定理より(注2)
$f(x)\equiv(x-1)(x-2)\cdots(x-p+1)$
$x$ に $0$ を代入すると,
$(-1)^{p-1}(p-1)!\equiv -1$
$p=2$ のときは自明に成立し,それ以外のとき $p$ は奇数なのでウィルソンの定理を得る。

(注2)厳密には合同式における剰余の定理も証明する必要がありますが省略します。

ちなみに,原始根の存在定理を仮定すれば原始根を使っても証明できます。→位数の性質と原始根の応用

知名度は高くないですがなかなかにエレガントな定理です

Tag: 素数にまつわる覚えておくべき性質まとめ

分野: 整数問題  レベル: 数学オリンピック