ウィルソンの定理について

ウィルソンの定理について
風あざみ
2014/04/07
1
証明の準備編
定理１：素数 p と正の整数 a を任意にとるとき、以下が成り立つ。
ap ≡ a
(mod p)
証明：数学的帰納法を用いる。
a = 1 のときは明らか。
a = k のとき正しいと仮定する。
p−1 ( )
∑
p
(k + 1)p − (k + 1) = k p − k +
· k p−i
i
i=1
( )
p
p!
=
の分子は素数 p で割り切れ、分母は割り切れないから
i
i!(p − i)!
( )
p
は p で割り切れることがいえるので、
i
p−1 ( )
∑
p
p
k −k+
· k p−i ≡ k p − k ≡ 0 (mod p)
i
i=1
したがって a = k + 1 のときも正しい。
以上より、定理１がいえた。
□
定理２：p − 1 以下の 0 以上の整数 m をとる.。整数係数のモニックな m 次式
f (x) をとるとき、f (x) ≡ 0 (mod p) の解は法 p で m 個以下である。
証明：m = 0 のときは明らか。m = e のとき、定理２が成立すると仮定する。
m = e + 1 のとき
f (x) ≡ 0 (mod p) が解を持たないとき解は 0 個だから、当然成り立つ。
f (x) ≡ 0 (mod p) が解 x0 を待つとき
f (x) を x − x0 で割り、商を q(x)、余りを r とすると f (x) = (x − x0 )q(x) + r
1
とかける（ここで q(x) は h 次式である）。
r ≡ (x0 − x0 )q(x0 ) + r ≡ f (x0 ) ≡ 0 (mod p) より r ≡ 0 (mod p)
よって f (x) ≡ (x − x0 )q(x)
(mod p) がいえる。p は素数だから、x ≡ x0
(mod p) あるいは q(x) ≡ 0 (mod p) が成り立つことがいえる。帰納法の仮定
より、q(x) ≡ 0 (mod p) をみたす x は法 p での個数は e 以下だから f (x) ≡ 0
(mod p) の解の個数は法 p で e + 1 個以下であることが言える。したがって、
m = e + 1 のときも定理２は正しい以上から任意の 0 以上の整数 m に対し
て、定理２が成立することがいえた。
2
□
ウィルソンの定理及びその逆の証明編
定理３：p を素数とするとき、(p − 1)! ≡ −1
(mod p) が成り立つ。
証明：整数を係数とする多項式 f (x), g(x) を
f (x) = x(x + 1)(x + 2) · · · x + (p − 1)、g(x) = xp − x とおく
0, 1, · · · , p − 1 から任意に a をとると、定理１より g(a) ≡ 0 (mod p) がいえ
るから f (a) − g(a) ≡ 0 − 0 ≡ 0 (mod p) がいえるから f (x) − g(x) = 0 の
解は法 p で p 個である。f (x) − g(x) は明らかに p − 1 次以下である。ここで
f (x) − g(x) がある 0 以上 p − 1 以下の整数 h に対して h 次式と仮定すると、
定理２より f (x) − g(x) の解の個数は h 個以下でなければならないので、こ
のことは上記の事実に反する。したがって、f (x) − g(x) の任意の係数が素数
p で割り切れることがいえる。とくに、f (x) − g(x) の 1 次の係数を比較して
(p − 1)! + 1 が p で割り切れることつまり、(p − 1)! ≡ −1 (mod p) が成り立
つことがいえた。
□
定理３はウィルソンの定理そのものである。
定理４：n を合成数とするとき、(n − 1)! ≡ −1
(mod n) は成立しない。
証明：n の 1 より大きな約数 d をとる。
このとき 0 ≡ (n−1)! ≡ −1
(mod d) がいえるが、これは不合理、したがって
定理４が成立することが言えた。
□
定理４はいわゆる「ウィルソンの定理の逆」である。
また、定理３と定理４を合わせると、以下がいえる。
n を 2 以上の整数とするとき、n が素数であるための必要十分条件は
(n − 1)! ≡ −1 (mod n) が成り立つことである。
2

Download Report