Security Akademeia

目次 †

目次
ウィルソンの定理
ウィルソンの定理の応用
参考文献

↑

ウィルソンの定理 †

ウィルソンの先輩であり友人であったE.ウェアリングの著者『Meditationes algebraicae』（1770）に、ウィルソンの定理として証明なしで発表された。
同年にJ.L.ラグランジュは同じ結果を証明付きで発表した。

[定理]ウィルソンの定理
p：素数
⇒ $(p-1)!~\equiv~-1~\,~\pmod{p}$

[証明]

$$~p-1~$~!$
$=~1~\times~2~\times~\cdots~\times~$~p-1~$$
$\equiv~g^1~\times~g^2~\times~\cdots~\times~g^{$~p-1~$}$ 　（∵pの原始根をgとすると、(p-1)までのすべての数を原始根のべきの形で表せる）
$\equiv~g^{1~+~2~+~\cdots~+~$~p-1~$}$
$=g^{\frac{p~$~p-1~$}{2}}$
$=~g^{\frac{1}{2}~$~p-1~$~$~p-1~$}~\times~g^{\frac{1}{2}~$~p-1~$}$
$=~$~g^{p-1}~$^{\frac{p-1}{2}}~\times~g^{\frac{p-1}{2}}$
$\equiv~1^{\frac{p-1}{2}}~\cdot~g^{\frac{p-1}{2}}~\,~$~mod~\,~p$$ 　（∵フェルマーの小定理）
$=~g^{\frac{p-1}{2}}$
$\equiv~-1~\,~$~mod~\,~p~$$ 　（∵±1であるが、gは原始根であるから、(p-1)乗までは+1とは不合同であるから。pは奇素数であることに注意）　□

[別証]

　体Z/(p)をFと書く。F[X]の多項式f(X)=Xp-1-1を考える。

　フェルマーの小定理によって、次が成り立つ。

$f~$~1~$~=0$
$f~$~2~$~=0$
…
$f~$~p-1~$~=0$

　ここにおける0,1,…などは、Fにおいて考えているし、等号もFにおいて考えているのである。

　Fにおいても、1,2,…,p-1は相異なるから、f(X)はF[X]の多項式として、 $~X-1~\)~$~X-2~$~\cdots~\(~X-p+1~$ となる。

　定数項の比較によって、 $$~p-1~$~!~=~-1~\,~in~\,~F$

　即ち、 $~p-1~\)!~\equiv~-1~\,~\(~mod~\,~p~$ 　□

[別証]

　p=2のとき、（左辺）＝1、（右辺）＝-1≡1 (mod 2)で成り立っている。

　そこで、pは3以上の奇素数とする。

　「Fpにおいて、 $x^{p-1}~-1~=~$~x-1~$~$~x-2~$~\cdots~\{~x-~$~p-1~$~\}$ と分解される」という定理がある。この等式の両辺のxに0を代入すると、次のようになる。

（左辺）＝-1
（右辺）＝(-1)(-2)…{-(p-1)}＝(-1)p-1(p-1)!＝(p-1)!　（∵pは奇数だから、p-1は偶数で、(-1)p-1=1になる）

　ゆえに、(p-1)!≡-1 (mod p)がいえた。　□

[別証]（ガウスの証明）

[1]p≠2の場合

aを1,2,…,p-2,p-1のどれかとする。
各々のa（1≦a≦p-1）に対して、a・b≡1 (mod p)となるb（1≦b≦p-1）が存在する。
なぜならば、「ax≡1 (mod p)はただ1つの解x=b（1≦b≦p-1）を持つ」からである。

このとき、a=bとなるようなaはx2≡1 (mod p)の解である。

$x^2~\equiv~1~\,~\pmod{p}$
$x^2~-1~\equiv~0~\,~\pmod{p}$
$(x+1)(x-1)~\equiv~0~\,~\pmod{p}$
$x+1~\equiv~0~\,~\pmod{p}~\,~or~\,~x-1~\equiv~0~\,~\pmod{p}$
$x~\equiv~\pm~1~\,~\pmod{p}$
$x~\equiv~1~\,~p-1~\,~\pmod{p}$ 　（∵解x≡-1はx≡p-1と同じため）

このようにして、{2,3,…,p-2}はab≡1となるa,bを1組として $\frac{p-3}{2}$ 個の組に分けられる。

よって、次が成り立つ。

$2~\cdot~3~\cdot~\cdots~\cdot~(p-3)(p-2)~\equiv~1~\,~\pmod{p}$
$(p-1)!~\equiv~-1~\,~\pmod{p}$ 　（∵ $p-1~\equiv~-1~\,~\pmod{p}$ ）

[1]p=2の場合

$1!~\equiv~-1~\,~\pmod{2}$ 　□

[別証]（ルジャンドルの証明）

オイラーの階乗公式より、以下が成り立つ。

$n!~=~\sum_{k=0}^{n}~(-1)^k~\left(\begin{matrix}n~\\~k~\\\end{matrix}\right)~(a-k)^n$
$(p-1)!~=~\sum_{k=0}^{p-1}~(-1)^k~\left(\begin{matrix}p-1~\\~k~\\\end{matrix}\right)~(p-k)^{p-1}$ 　（∵a=p,n=p-1とおいた）
$(p-1)!~\equiv~\sum_{k=1}^{p-1}~(-1)^k~\left(\begin{matrix}p-1~\\~k~\\\end{matrix}\right)~\,~\pmod{p}$ 　（∵pは素数なので、フェルマーの小定理より、k≠0の項は $(p-k)^{p-1}~\equiv~1~\,~\pmod{p}$ 。一方、k=0の項は $p~\equiv~0~\,~\pmod{p}$ より、 $p^{p-1}~\equiv~0~\,~\pmod{p}$ );　←シグマのk=1に注目。
$(p-1)!~\equiv~(1-1)^{p-1}~-~1~\,~\pmod{p}$ 　（∵[定理]「pを素数とすると、 $\left(\begin{matrix}p~\\~k~\\\end{matrix}\right),~\,~(1~\le~k~\le~p-1)$ はすべてpで割り切れる」）
$(p-1)!~\equiv~-1~\,~\pmod{p}$ 　□

[別証]（ディリクレの証明）

[定理]「pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、 $a^{\frac{p-1}{2}}~\equiv~1$
[2]x2≡aに解がある場合、 $a^{\frac{p-1}{2}}~\equiv~-1$ 」において、[2]の場合かつa=1の場合を考える。
すると、ウィルソンの定理そのものである。　□

↑

ウィルソンの定理の応用 †

[定理]pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、 $a^{\frac{p-1}{2}}~\equiv~1$
[2]x2≡aに解がある場合、 $a^{\frac{p-1}{2}}~\equiv~-1$

[証明]（ディリクレの証明）

pを素数とし、pはaを割り切らないとする。

[定理]「pは素数、aは整数でpの倍数でないとすると、任意の整数cに対して、方程式ax≡c (mod p)はただ1つの解を持つ」より、1≦m≦p-1ならば、 $mn~\equiv~a~\,~\pmod{p}$ となるn（1≦n≦p-1）がちょうど1つ存在する。

[1]x2≡a (mod p)に解がない場合

{1,2,…,p-1}はmn≡aとなる(p-1)/2個の組{m,n}に分割されるから、次が成り立つ。

$(p-1)!~\equiv~a^{\frac{p-1}{2}}~\,~\pmod{p}$

[2]x2≡a (mod p)に解がある場合

1つの解をkとすると、残りの解はp-k（≡-k）である。

kとp-kを除くと、{1,2,…,p-1}はmn≡aとなる(p-3)/2個の組{m,n}に分割されるから、次のように展開できる。

$(p-1)!$
$\equiv~k(p-k)a^{\frac{p-3}{2}}$
$\equiv~-k^2~a^{\frac{p-3}{2}}$ 　（∵p-k≡-kだから）
$\equiv~-a^{\frac{p-1}{2}}$ 　□

[定理]
[1]「p：1型の素数」⇒「 $((\frac{p-1}{2})!)^2~\equiv~-1~\,~\pmod{p}$ 」
[2]「p：3型の素数」⇒「 $(\frac{p-1}{2})!~\equiv~1~\,~or~\,~-1~\,~\pmod{p}$ 」

[証明]

[1]pが1型の素数の場合

$(p-1)!~\equiv~1~\cdot~2~\cdot~\cdots~\cdot~\frac{p-1}{2}~\cdot~\frac{p+1}{2}~\cdot~\cdots~\cdot~(p-2)~(p-1)$
$(p-1)!~\equiv~(-1)^{\frac{p-1}{2}}~(1~\cdot~2~\cdot~\cdots~\cdot~\frac{p-1}{2})^2~\,~\pmod{p}$ 　（∵ $p-1~\equiv~-1,~p-2~\equiv~-2,~\cdots,~\frac{p+1}{2}~\equiv~-~\frac{p-1}{2}~\,~\pmod{p}$ ）
$(p-1)!~\equiv~(-1)^{\frac{p-1}{2}}~((\frac{p-1}{2})!)^2~\,~\pmod{p}$
$-1~\equiv~(-1)^{\frac{p-1}{2}}~((\frac{p-1}{2})!)^2~\,~\pmod{p}$ 　（∵ウィルソンの定理より、 $(p-1)!~\equiv~-1~\,~\pmod{p}$ ） $((\frac{p-1}{2})!)^2~\equiv~(-1)^{\frac{p+1}{2}}\,~\pmod{p}$ 　←(*)
$((\frac{p-1}{2})!)^2~\equiv~-1~\,~\pmod{p}$ 　（∵pが1型の素数の場合、即ちp=4n+1の場合、 $(-1)^{\frac{p+1}{2}}~=~(-1)^{2n+1}~=~-1$ ）

[2]pが3型の素数の場合

$((\frac{p-1}{2})!)^2~\equiv~1~\,~\pmod{p}$ 　（∵pが3型の素数の場合、即ちp=4n-1の場合、 $(-1)^{\frac{p+1}{2}}~=~(-1)^{2n}~=~1$ ）
$((\frac{p-1}{2})!+1)((\frac{p-1}{2})!-1)~\equiv~0~\,~\pmod{p})$
$(\frac{p-1}{2})!~\equiv~1~\,~or~\,~-1~\,~\pmod{p}$ 　□

[例]p=13の場合

$(\frac{p-1}{2})!=(\frac{13-1}{2})!=6!=720~\equiv~5~\,~\pmod{13}$ より、 $((\frac{p-1}{2})!)^2~=~5^2~\equiv~-1~\,~\pmod{13}$

一方、p=13は1型の素数である（なぜならば、p=4・3+1であるため）。
よって、上記の定理より、法13で-1が成り立つ。　◇

[定理]n＞4が素数でなければ、n|(n-1)!

[証明]

[1]nが素数の2乗でない場合

nはn=kl（1＜k＜l＜n-1）のように分解できる。

kもlも(n-1)!=1・2・…・k・…・l・…・(n-1)の中に因子として現れるから、klは(n-1)!を割り切る。即ち、kl|(n-1)!である。

[2]nが素数pの2乗の場合

pと2pが(n-1)!=1・2・…・p・…・2p・…・(n-1)の中に因子として現れるから、p2は(n-1)!を割り切る。即ち、p2|(n-1)!である。
ただし、2p＞n-1=p2-1の場合は、この議論は通用しないが、それはp=2の場合だけであり、n＞4という仮定よりこの問題は生じない。　□

[定理]
[1]「n：素数」⇒「 $(n-1)!~\equiv~-1~\,~\pmod{n}$ 」
[2]「n：素数ではない」⇒「 $(n-1)!~\not{\equiv}~-1~\,~\pmod{n}$ 」

[証明]

[1]ウィルソンの定理そのものである。

[2][定理]「n＞4が素数でなければ、n|(n-1)!」より、(n-1)!はnで割り切れる。つまり、n-1では割り切れない。　□

[補講]この定理を素数判定に利用できるが、nが少しでも大きくなると(n-1)!は巨大な数となり実際には役に立たない。　◇

[定理]pが奇素数のとき、次の合同式が成り立つ。
[1] $1^2~\cdot~3^2~\cdot~5^2~\cdot~\cdots~\cdot~(p-2)^2~\equiv~(-1)^{\frac{p+1}{2}}~\,~\pmod{p}$
[2] $2^2~\cdot~4^2~\cdot~6^2~\cdot~\cdots~\cdot~(p-1)^2~\equiv~(-1)^{\frac{p+1}{2}}~\,~\pmod{p}$

[証明]

[1]

$1^2~\cdot~3^2~\cdot~5^2~\cdot~\cdots~\cdot~(p-2)^2~\,~\pmod{p}$
$\equiv~(-1)^{\frac{p-1}{2}}~1~\cdot~(-1)~\cdot~3~\cdot~(-3)~\cdot~\cdots~\cdot~(p-2)(-p+2)~\,~\pmod{p}$ 　（∵1～p-2の奇数は(p-2)/2個である）
$\equiv~(-1)^{\frac{p-1}{2}}~1~\cdot~(p-1)~\cdot~3~\cdot~(p-3)~\cdot~\cdots~\cdot~(p-2)(2)~\,~\pmod{p}$ 　（∵法pで考える）
$\equiv~(-1)^{\frac{p-1}{2}}~1~\cdot~2~\cdot~3~\cdot~4~\cdot~\cdots~\cdot~(p-1)~\,~\pmod{p}$
$\equiv~(-1)^{\frac{p-1}{2}}~(p-1)!~\,~\pmod{p}$
$\equiv~(-1)^{\frac{p-1}{2}}~(-1)~\,~\pmod{p}$ 　（∵ウィルソンの定理）
$\equiv~(-1)^{\frac{p+1}{2}}~\,~\pmod{p}$ 　□

[2]

$(p-1)!~\equiv~-1~\,~\pmod{p}$ 　（∵ウィルソンの定理）
$((p-1)!)^{2}~\equiv~1~\,~\pmod{p}$ 　（∵両辺を2乗した）
$1^2~\cdot~2^2~\cdot~\cdots~\cdot~(p-1)^2~\equiv~1~\,~\pmod{p}$
$1^2~\cdot~3^2~\cdot~\cdots~\cdot~(p-2)^2~\cdot~2^2~\cdot~4^2~\cdot~6^2~\cdot~\cdots~\cdot~(p-1)^2~\equiv~1~\,~\pmod{p}$
$(-1)^{\frac{p+1}{2}}~\cdot~2^2~\cdot~4^2~\cdot~6^2~\cdot~\cdots~\cdot~(p-1)^2~\equiv~1~\,~\pmod{p}$ 　（∵[1]より）
∴ $2^2~\cdot~4^2~\cdot~6^2~\cdot~\cdots~\cdot~(p-1)^2~\equiv~(-1)^{\frac{p+1}{2}}~\,~\pmod{p}$ 　□

[定理]ライプニッツの定理
自然数p＞2について、次が成り立つ。
「p：素数」⇔「 $(p-2)!-1$ がpの倍数」

[証明]

[1]⇒を示す。

$(p-1)!~\equiv~-1~\,~\pmod{p}$ 　（∵pは素数なので、ウィルソンの定理が使える）
$(p-1)!~+1~\equiv~0~\,~\pmod{p}$
$(p-1)(p-2)!~+1~\equiv~0~\,~\pmod{p}$
$p(p-2)!~-~(p-2)!~+1~\equiv~0~\,~\pmod{p}$ 　（∵(p-1)(p-2)!を分解する）
$-(p-2)!~+1~\equiv~0~\,~\pmod{p}$
∴ $(p-2)!~-1~\equiv~0~\,~\pmod{p}$

[2]←を示す。

整数p（＞2）について、 $(p-2)!-1$ がpの倍数であるとする。

$(p-2)!-1~\equiv~0~\,~\pmod{p}$
$(p-1)((p-2)!-1)~\equiv~0~\,~\pmod{p}$ 　（∵両辺にp-1をかけた）
$(p-1)(p-2)!-(p-1)~\equiv~0~\,~\pmod{p}$
$(p-1)!-(p-1)~\equiv~0~\,~\pmod{p}$
$(p-1)!+1~\equiv~0~\,~\pmod{p}$ 　←(*)

ここで、pが素数ではないと仮定する。
すると、1より大きく、pより小さい整数a,bがあり、p=abと書ける。
このとき、a,bはpより小さく、p=abであるため、a,bは(p-1)!の約数になる。また、(*)より、(p-1)!+1はpの倍数であり、p=abであるため、a,bは(p-1)!+1の約数になる。
しかし、この両方を満たすのは不可能である。
したがって、pは素数である。　□

[例]

p=3の場合
- (3-2)!-1=1-1=0は3の倍数である。
p=4の場合
- (4-2)!-1=2-1=1は4の倍数ではない。
p=5の場合
- (5-2)!-1=6-1=5は5の倍数である。
p=6の場合
- (6-2)!-1=24-1=23（素数）は6の倍数ではない。
p=7の場合
- (7-2)!-1=119=7・24は7の倍数である。

◇

↑

参考文献 †

『なっとくするオイラーとフェルマー』

Top / ウィルソンの定理ウィルソンの定理

目次 †

ウィルソンの定理 †

ウィルソンの定理の応用 †

参考文献 †

Top / ウィルソンの定理
ウィルソンの定理