このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

ウィルソンの定理

  • ウィルソンの先輩であり友人であった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の倍数である。

参考文献

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