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

ウィルソン(Wilson)の定理

22 以上の整数 pp について,pp が素数     (p1)!1(modp)\iff (p-1)!\equiv -1 \pmod{p}

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

ウィルソンの定理

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

重要なのは左から右です。

実際に pp が小さい場合に実験してウィルソンの定理の主張を確認してみます。

p=211(mod2)p=2 → 1\equiv -1\pmod{2}

p=321(mod3)p=3 → 2\equiv -1\pmod{3}

p=5241(mod5)p=5 → 24\equiv -1\pmod{5}

p=77201(mod7)p=7 → 720\equiv -1\pmod{7}

合同式に慣れていない人は合同式の意味とよく使う6つの性質を参考にしてください。

以下modp\bmod{p} の表記を省略します。

ウィルソンの定理の証明では特に,合同式の性質:

abacab\equiv ac で,aapp が互いに素なら bcb\equiv c

が重要になります。

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

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

nn が小さい場合に証明しようとすれば自然に出てくる発想です。

(71)!=123456=(53)(42)1661(mod7)(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\equiv -1\pmod{7}

方針

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

証明

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

m,2m,3m,(p1)mm,2m,3m\cdots,(p-1)mpp で割った余りはすべて異なるので,

mn1mn\equiv 1 となる nn11 から p1p-1 の間にただ1つ存在する(注1)。

そのような nn が,mm と等しい場合は困るのでそのような良くない場合を探す:

m21m^2\equiv 1

つまり,(m1)(m+1)0(m-1)(m+1)\equiv 0

合同式の性質より m10m-1\equiv 0 または m+10m+1\equiv 0

よって,m1,p1m\neq 1,p-1 のときは mnm\neq n となる。

よって,2,3,p22,3,\cdots p-2 の中でそのような mmnn のペアを p32\dfrac{p-3}{2} 個作ることにより,

(p1)!1p321(p1)(p-1)!\equiv 1^{\frac{p-3}{2}}\cdot 1\cdot (p-1)

が分かりウィルソンの定理が示された。

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

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

方針

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

証明

f(x)=xp11f(x)=x^{p-1}-1

という関数を考える。

フェルマーの小定理より,x=1,2,,p1x=1,2,\cdots,p-1 に対して,

f(x)0f(x)\equiv 0

である。

f(x)f(x)(x1)(x-1) で割った商を Q1(x)Q_1(x),余りを R1R_1 とおくと

f(x)=Q1(x)(x1)+R1f(x)=Q_1(x)(x-1)+R_1

x=1x=1 を代入すると,f(1)0f(1)\equiv 0 より R10R_1\equiv 0

つまり f(x)Q1(x)(x1)f(x)\equiv Q_1(x)(x-1)

さらに,Q1(x)Q_1(x)(x2)(x-2) で割った商を Q2(x)Q_2(x),余りを R2R_2 とおくと

f(x){Q2(x)(x2)+R2}(x1)f(x)\equiv \{Q_2(x)(x-2)+R_2\}(x-1)

x=2x=2 を代入すると,f(2)0f(2)\equiv 0 より R20R_2\equiv 0

以下同様にして,

f(x)Qp1(x)(x1)(x2)(xp+1)f(x)\equiv Q_{p-1}(x)(x-1)(x-2)\cdots(x-p+1)

となる。ここで,割り算の等式を見ながら,

  • Q1(x)Q_1(x)(p2)(p-2) 次で最高次の係数は 11
  • Q2(x)Q_2(x)(p3)(p-3) 次で最高次の係数は 11

と順々に考えていくと Qp1(x)Q_{p-1}(x)00 次で最高次の係数は 11,つまり Qp1(x)=1Q_{p-1}(x)=1 である。

以上より,

f(x)(x1)(x2)(xp+1)f(x)\equiv (x-1)(x-2)\cdots(x-p+1)

この式の xx00 を代入すると,

(1)p1(p1)!1(-1)^{p-1}(p-1)!\equiv -1

p=2p=2 のときは自明に成立し,それ以外のとき pp は奇数なのでウィルソンの定理を得る。

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

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

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