ウィルソンの定理

この記事の所要時間: 550

ウィルソンの定理

定理: 2以上の正整数pが素数であることと, 次の合同式が成り立つことは同値です.

(1) \begin{equation*} (p-1)!\equiv-1 \pmod{p} \end{equation*}

合同式が関係する有名な定理の一つです. (合同式についてはこちら. )

証明

pが素数なら式(1)が成り立つことの証明は1通り, 逆の証明は2通り紹介します. 前半の証明は分かりにくいかもしれませんが, 対偶を示しています. 逆の証明は,

  1. フェルマーの小定理合同式における剰余の定理を用いる方法.
  2. 1p-1を積の剰余が1になる組に分けられることを示す方法.

です.

(\Leftarrow)

対偶をとって, p\geqq 2が素数でないならば(p-1)!\equiv -1\pmod{p}が成り立たないことを示します.

[1] p=4のとき

(2) \begin{equation*} (4-1)!=6\not\equiv -1 \pmod{4} \end{equation*}

[2] p>4のとき

素数でないpが次のように素因数分解されたとする.

(3) \begin{equation*} p=p_1^{e_1}\cdot p_2^{e_2}\cdots p_m^{e_m} \end{equation*}

ただし, mは素因数の個数で, 各p_iは素数, p_i\neq p_j, i\neq j, 各e_iは1以上とします. このとき,

(4) \begin{eqnarray*} \frac{p}{p_1} &=& p_1^{e_1-1}\cdot p_2^{e_2}\cdots p_m^{e_m}\\ &\geqq& p_1^{e_1-1}\\ &\geqq& 2^{e_1-1}\\ &\geqq& e_1 \end{eqnarray*}

但し, 最後の部分では不等式2^{n-1}\geqq nを用いていますが, これはnについての数学的帰納法で示されます. 等号がすべて成り立つのはm=1, p_1=2, e_1=1, 2のときのみ, つまりp=2, 4のときのみなので, p>4なら\displaystyle\frac{p}{p_1}>e_1. 両辺にp_1を掛ければ\displaystyle p>p_1e_1, つまりp-1以下にp_1の倍数が最低でもe_1個は存在する, ということになります. 同様にして, p_2, \ldots, p_mについてもそれぞれの倍数がp-1以下にe_2, \ldots, e_m個存在します.

このことから, p-1以下の自然数を全て掛け合わせたものがp_1^{e_1}, p_2^{e_2}, \ldots, p_m^{e_m}で割り切れる, つまりpで割り切れます. 故に,

(5) \begin{equation*} (p-1)!\equiv 0 \not\equiv -1 \pmod{p} \end{equation*}

(\Rightarrow)の証明Ⅰ.

p=2の場合は代入すれば成り立つことがすぐにわかるので, p>2の場合, つまりpが奇素数の場合を考えます.

1, 2, \cdots, p-1pと互いに素であるので, フェルマーの小定理より,

(6) \begin{equation*} 1^{p-1}\equiv 2^{p-1}\equiv \cdots\equiv (p-1)^{p-1}\equiv 1\pmod{p} \end{equation*}

最右辺の1を移項して,

(7) \begin{equation*} 1^{p-1}-1\equiv 2^{p-1}-1\equiv\cdots\equiv(p-1)^{p-1}-1\equiv 0 \end{equation*}

ここで, F(x)=x^{p-1}-1とおくと, 上の式は

(8) \begin{equation*} F(1)\equiv F(2)\equiv\cdots\equiv F(p-1)\equiv 0 \end{equation*}

ここで, 合同式における剰余の定理によって, 次のように書ける.

(9) \begin{equation*} F(x)\equiv (x-1)(x-2)\cdots\{x-(p-1)\} \end{equation*}

ここにx=0を代入して, また, F(0)=-1, pが奇数であることを用いて,

(10) \begin{eqnarray*} -1 &\equiv& (-1)\cdot(-2)\cdots\{-(p-1)\}\\ &\equiv& (p-1)! \end{eqnarray*}

となり示された.

(\Rightarrow)の証明Ⅱ.

pが素数のとき, 1\leqq k\leqq p-1を満たす整数kに対して, 以下の方程式はただ一つの解をもつ.

(11) \begin{equation*} kx\equiv 1\pmod{p} \ (1\leqq x\leqq p-1) \end{equation*}

(\because) kpと互いに素なので, k, 2k, \ldots, (p-1)kpで割った余りは1, 2, \ldots, p-1と1対1に対応する(フェルマーの小定理の証明Ⅱ参照). これは式(11)の解がただ一つ存在することを意味している.

ここで, k=1に対する解はx=1, k=p-1に対する解はx=p-1で, 2\leqq k\leqq p-2に対してはk^2\not\equiv 1より解x\neq k. つまり, 2, 3, \ldots, p-2pを法としてその積の剰余が1となるような2つずつの組に分けることができる. よって,

(12) \begin{eqnarray*} (p-1)! &\equiv& (p-1)\cdot 1^{\frac{p-3}{2}}\cdot 1\\ &\equiv& p-1\\ &\equiv& -1 \pmod{p} \end{eqnarray*}

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。

This site uses Akismet to reduce spam. Learn how your comment data is processed.