[定理]ウィルソンの定理
p:素数
⇒
[証明]
(∵pの原始根をgとすると、(p-1)までのすべての数を原始根のべきの形で表せる)
(∵フェルマーの小定理)
(∵±1であるが、gは原始根であるから、(p-1)乗までは+1とは不合同であるから。pは奇素数であることに注意) □
[別証]
体Z/(p)をFと書く。F[X]の多項式f(X)=Xp-1-1を考える。
フェルマーの小定理によって、次が成り立つ。
…
ここにおける0,1,…などは、Fにおいて考えているし、等号もFにおいて考えているのである。
Fにおいても、1,2,…,p-1は相異なるから、f(X)はF[X]の多項式として、となる。
定数項の比較によって、
即ち、 □
[別証]
p=2のとき、(左辺)=1、(右辺)=-1≡1 (mod 2)で成り立っている。
そこで、pは3以上の奇素数とする。
「Fpにおいて、と分解される」という定理がある。この等式の両辺の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≡-1はx≡p-1と同じため)
このようにして、{2,3,…,p-2}はab≡1となるa,bを1組として個の組に分けられる。
よって、次が成り立つ。
(∵
)
[1]p=2の場合
□
[別証](ルジャンドルの証明)
オイラーの階乗公式より、以下が成り立つ。
(∵a=p,n=p-1とおいた)
(∵pは素数なので、フェルマーの小定理より、k≠0の項は
。一方、k=0の項は
より、
); ←シグマのk=1に注目。
(∵[定理]「pを素数とすると、
はすべてpで割り切れる」)
□
[別証](ディリクレの証明)
[定理]「pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、
[2]x2≡aに解がある場合、」において、[2]の場合かつa=1の場合を考える。
すると、ウィルソンの定理そのものである。 □
[定理]pを素数、pはaを割り切らないとする。
[1]x2≡aに解がない場合、
[2]x2≡aに解がある場合、
[証明](ディリクレの証明)
pを素数とし、pはaを割り切らないとする。
[定理]「pは素数、aは整数でpの倍数でないとすると、任意の整数cに対して、方程式ax≡c (mod p)はただ1つの解を持つ」より、1≦m≦p-1ならば、となるn(1≦n≦p-1)がちょうど1つ存在する。
[1]x2≡a (mod p)に解がない場合
{1,2,…,p-1}はmn≡aとなる(p-1)/2個の組{m,n}に分割されるから、次が成り立つ。
[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-k≡-kだから)
□
[定理]
[1]「p:1型の素数」⇒「」
[2]「p:3型の素数」⇒「」
[証明]
[1]pが1型の素数の場合
(∵
)
(∵ウィルソンの定理より、
)
←(*)
(∵pが1型の素数の場合、即ちp=4n+1の場合、
)
[2]pが3型の素数の場合
(∵pが3型の素数の場合、即ちp=4n-1の場合、
)
□
[例]p=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:素数」⇒「」
[2]「n:素数ではない」⇒「」
[証明]
[1]ウィルソンの定理そのものである。
[2][定理]「n>4が素数でなければ、n|(n-1)!」より、(n-1)!はnで割り切れる。つまり、n-1では割り切れない。 □
[補講]この定理を素数判定に利用できるが、nが少しでも大きくなると(n-1)!は巨大な数となり実際には役に立たない。 ◇
[定理]pが奇素数のとき、次の合同式が成り立つ。
[1]
[2]
[定理]ライプニッツの定理
自然数p>2について、次が成り立つ。
「p:素数」⇔「がpの倍数」
[証明]
[1]⇒を示す。
(∵pは素数なので、ウィルソンの定理が使える)
(∵(p-1)(p-2)!を分解する)
∴
[2]←を示す。
整数p(>2)について、がpの倍数であるとする。
(∵両辺にp-1をかけた)
←(*)
ここで、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は素数である。 □
[例]
◇