No4. 多項式の合同 - H.Yagyu Web

22
数の性質をさぐる
No. 4
多項式の合同
多項式について，次のことは既知である．
!
定理 14
（代数学の基本定理）
複素数を係数とする n 次方程式 an xn + an−1 xn−1 + · · · + a1 x + a0 = 0 (an != 0) は，複素数の範囲に
重解を含めちょうど n 個の解を持つ．
#
これと同じことが合同方程式についても成り立つだろうか．明らかにそうではない．合同方程式
"
$
xp−1 − 1 ≡ 0 ( mod p)
はフェルマーの小定理によりちょうど p − 1 個の解 x ≡ 1, 2, · · · , p − 1 を持つが，次の合同方程式
x4 − 1 ≡ 0 ( mod 16)
は次数 4 よりも多い 8 個の解 x ≡ 1, 3, 5, 7, 9, 11, 13, 15 を持つ．また，合同方程式
x4 − 2 ≡ 0 ( mod 16)
は解を持たない．合同方程式は一般の代数方程式よりも複雑な特徴を持っているようである．この章で
は，一般の合同方程式の解について成り立つ種々の性質を調べよう．
1. 多項式の合同の定義
まずは多項式の合同を定義する．
!
定義 5
（整数を法とする多項式の合同）
整数を係数とする 2 つの多項式
"
f (x) = cn xn + cn−1 xn−1 + · · · + c1 x + c0
g(x) = c"n xn + c"n−1 xn−1 + · · · + c"1 x + c"0
の任意の i (0 ≤ i ≤ n) に対して ci ≡ c"i (mod m) が成り立つとき，f (x) と g(x) は m を法として合
同であるといい，
f (x) ≡P g(x) ( mod m)
と表す．
#
例： x + 2x + 4 ≡P 4x + 5x + 1 (mod 3) である．
2
2
備考：≡P という記号は，このプリント内だけで通用する記号である．整数の合同と多項式の合同に同
じ記号 ≡ を使用すると混乱が生じるおそれがあるため，両者を区別することにした．
問 16
f (x) ≡P g(x) (mod p) ならば，任意の整数 a に対して f (a) ≡ g(a) (mod p) が成り立つが，こ
の逆は成り立たない．反例を述べよ．
$
!
定義 6
23
（整数を法とする多項式の整除）
整数を係数とする多項式 f (x), g(x) に対して，
"
f (x) ≡P g(x)h(x) ( mod m)
を満たす整数を係数とする多項式 h(x) が存在するとき，m を法として f (x) は g(x) で割り切れると
いい，g(x) | f (x) (mod m ) と表す．
#
$
例： x3 + x2 + 1 ≡P (2x + 1)(2x2 + x + 1) (mod 3) なので，x3 + x2 + 1 は 3 を法として 2x + 1, 2x2 + x + 1
で割り切れる．また，1 ≡P (2x + 1)2 (mod 4) なので，1 は 4 を法として 2x + 1 で割り切れる．
整数を法とする多項式においても，因数定理が成り立つ．
!
定理 15
（因数定理）
f (x) を整数を係数とする多項式とする．このとき，f (x) が m を法として x − a で割り切れるため
の必要十分条件は，f (a) ≡ 0 (mod m) が成り立つことである．
#
(証明)
"
$
［必要性］
x − a | f (x) (mod m) とする．このとき，ある整数係数の多項式 h(x) が存在して
f (x) ≡P (x − a)h(x) ( mod m)
が成り立つから，両辺に a を代入して f (a) ≡ 0 (mod m) を得る．
［十分性］
f (a) ≡ 0 (mod m) とする．このとき f (x) ≡P f (x) − f (a) (mod m) である．
f (x) = cn xn + cn−1 xn−1 + · · · + c1 x + c0
とおく．
xk − a k
f (x) − f (a)
任意の自然数 k に対し，
は整数係数の x の多項式であることに留意する．h(x) =
と
x−a
x−a
おくと，
f (x) − f (a) (cn xn + cn−1 xn−1 + · · · + c1 x + c0 ) − (cn an + cn−1 an−1 + · · · + c1 a + c0 )
h(x) =
=
x−a
x−a
xn − a n
xn−1 − an−1
x−a
= cn
+ cn−1
+ · · · + c1
x−a
x−a
x−a
は整数係数の多項式である．
よって，f (x) ≡P (x − a)h(x) (mod m) が成り立ち，f (x) は m を法として x − a で割り切れる．
（証明終）
問 17
x4 − 1 が 10 を法として x − 3 で割り切れるかどうか判定せよ．
24
2. 素数を法とする合同方程式の解
代数方程式の場合，f (x) が f (x) = g(x)h(x) と因数分解されているとき，
x = a が f (x) = 0 の解である =⇒ x = a は g(x) = 0 または h(x) = 0 の解である
が成り立つ．したがって，我々は代数方程式を解くときには多項式を因数分解することをまず考えるわ
けである．
ところが，合同方程式の場合には因数分解が有効な方法でない場合がある．例えば合同方程式
x2 ≡ 0 ( mod 4)
を考えよう．x ≡ 0 (mod 4) は明らかにこの合同方程式の解である．しかし，4 を法として
x2 ≡P x2 − 4 = (x + 2)(x − 2) ( mod 4)
が成り立つが，x ≡ 0 (mod 4) は x + 2 ≡ 0 (mod 4) や x − 2 ≡ 0 (mod 4) の解ではない．しかし，素数
を法とする場合には代数方程式と同様に，次の定理が成り立つ．
!
定理 16
p を素数とし，f (x) ≡P g(x)h(x) (mod p) とする．このとき
"
f (a) ≡ 0 ( mod p) =⇒ g(a) ≡ 0 ( mod p) または h(a) ≡ 0 ( mod p)
が成り立つ．
#
$
(証明)
f (a) ≡ 0 (mod p) とすると，f (x) ≡P g(x)h(x) (mod p) より g(a)h(a) ≡ 0 (mod p) が成り立つ．
p は素数だから，g(a) ≡ 0 (mod p) または h(a) ≡ 0 (mod p) が成り立つ．
（証明終）
. 用例題
応
. .6
%
p を素数とする．2 次の合同方程式 ax2 + bx + c ≡ 0 (mod p) · · · &
1 が p を法として 3 個の
'
解説 (
&
異なる解を持つとき，ax2 + bx + c ≡P 0 (mod p) であることを証明せよ．
&
1 が p を法として異なる 3 解 x ≡ α, β, γ (mod p) を持つとする．x ≡ α (mod p) は
&
1 次式 h(x) が存在して
1 の解なので，因数定理（定理 15）より，ある!!!!!!!
ax2 + bx + c ≡P (x − α)h(x) (mod p)
が成り立つ．x ≡ β (mod p) も &
1 の解なので，定理 16 より x ≡ β (mod p) は x − α ≡ 0 (
mod p) または h(x) ≡ 0 (mod p) の解である．β − α !≡ 0 (mod p) より h(β) ≡ 0 (mod p)
である．よって，再び因数定理より，ある 0 次式（定数）k が存在して
h(x) ≡P k(x − β) (mod p)
となる．よって ax2 + bx + c ≡P k(x − α)(x − β) (mod p) となるが，x ≡ γ (mod p) も
&
1 の解なので k(γ − α)(γ − β) ≡ 0 (mod p) となり，γ − α, γ − β !≡ 0 (mod p) なので
k ≡ 0 (mod p) である．ゆえに ax2 + bx + c ≡P 0 (mod p) である．
（証明終）（終）
25
問 18
p を素数とする．3 次の合同方程式 ax3 + bx2 + cx + d ≡ 0 (mod p) が p を法として 4 個の異な
る解を持つとき，ax3 + bx2 + cx + d ≡P 0 (mod p) であることを証明せよ．
一般に次が成り立つ．
!
定理 17
p を素数とする．n 次の合同方程式 f (x) ≡ 0 (mod p) が p を法として n 個より多くの異なる解を持
つならば，f (x) ≡P 0 (mod p) である．
#
証明は上の例題と同じように帰納法でできる．
"
$
備考：ここで法が素数であるという条件は本質的である．たとえば 4 次の合同方程式 x4 −1 ≡ 0 (mod 16)
は 8 個の異なる解 x ≡ 1, 3, 5, 7, 9, 11, 13, 15 (mod 16) を持つ．
上の定理の証明より，同時に次の定理も示される．
!
定理 18
p を素数，f (x) を整数を係数とする n 次の多項式とする．f (x) ≡ 0 (mod p) が n 個の異なる解
"
a1 , a2 , · · · , an
を持つならば，f (x) は
f (x) ≡P c0 (x − a1 )(x − a2 ) · · · (x − an ) ( mod p)
と因数分解される．ここで c0 は f (x) の最高次の係数である．
#
$
3. フェルマーの小定理の拡張
フェルマーの小定理は，素数 p を法とする合同方程式 xp−1 ≡ 1 (mod p) がちょうど p − 1 個の（最大
限の）個数の解を持つことを主張していたが，一般に次の定理が成り立つ．
!
定理 19
素数 p を法とする合同方程式 xd ≡ 1 (mod p) は，d | p − 1 のときちょうど d 個の解を持つ．
#
(証明)
xp−1 − 1 = (xd − 1)g(x) (g(x) = xp−1−d + xp−1−2d + · · · + xd + 1)
と因数分解できる．
フェルマーの小定理より，xp−1 − 1 ≡ 0 (mod p) はちょうど p 個の解を持つ．これらの解は定理 16 よ
り xd − 1 ≡ 0 (mod p) または g(x) ≡ 0 (mod p) の解である．しかし，ラグランジュの定理からそれぞ
れの解の個数は高々d 個と高々p − 1 − d 個だから，両方がその最大限の個数の解を持たなければならな
い．よって xd − 1 ≡ 0 (mod p) はちょうど d 個の解を持つ．
（証明終）
"
$
26
問 19
合同方程式 x4 ≡ 1 (mod 13) の解の個数を求めよ．
問 20
合同方程式 x9 + x6 + x3 + 1 ≡ 0 (mod 37) の解の個数を求めよ．
4. 応用：ウィルソンの定理
フェルマーの小定理より
xp−1 − 1 ≡ 0 ( mod p)
は p − 1 個の解
x ≡ 1, 2, · · · , p − 1 ( mod p )
を持つ．よって定理 18 より
xp−1 − 1 ≡P (x − 1)(x − 2) · · · (x − (p − 1)) ( mod p) · · · (♭)
と因数分解される．(♭) の右辺を展開し，両辺の定数項を比較すれば，次の定理が得られる．
!
定理 20
（ウィルソンの定理）
p を素数とするとき，(p − 1)! ≡ −1 (mod p) が成り立つ．
#
"
$
例： (5 − 1)! = 4! = 24 ≡ −1 (mod 5), (11 − 1)! = 10! = 3628800 ≡ −1 (mod 11) である．
さらに，(♭) の展開式において x1 , · · · , xp−2 の係数を比較すると，次の定理が得られる．
!
定理 21
p を奇素数，1 ≤ k ≤ p − 2 とする．このとき，集合 {1, 2, · · · , p − 1} の中から異なる k 個の数を
とって作った積すべての和を Mk とすると，Mk ≡ 0 (mod p) である．
#
(証明)
恒等式
(x − 1)(x − 2) · · · (x − p + 1) = xp−1 − M1 xp−2 + M2 xp−3 − · · · − Mp−2 x + Mp−1
が成り立つから，(♭) により係数を比較して Mk ≡ 0 (mod p) (1 ! k ! p − 2) を得る．
（証明終）
例： 1 · 2 · 3 · 4 · 5 + 1 · 2 · 3 · 4 · 6 + 1 · 2 · 3 · 5 · 6 + 1 · 2 · 4 · 5 · 6 + 1 · 3 · 4 · 5 · 6 + 2 · 3 · 4 · 5 · 6
= 1764 ≡ 0 (mod 7) が成り立つ．
問 21
p を奇素数とするとき，分数
1 1
1
1 + + + ··· +
2 3
p−1
の分子は p で割り切れることを示せ．
"
$
27
5. 応用：ウルステンホルムの定理
問 21 で述べたように，分数
1 1
1
1 + + + ··· +
2 3
p−1
の分子は p で割り切れる．では p2 でも割り切れるだろうか．
!
定理 22
（ウルステンホルムの定理）
p を 3 より大きい素数とするとき，分数
"
1 1
1
1 + + + ··· +
2 3
p−1
の分子は p2 で割り切れる．
#
(証明)
恒等式
(x − 1)(x − 2) · · · (x − p + 1) = xp−1 − M1 xp−2 + M2 xp−3 − · · · + Mp−3 x2 − Mp−2 x + Mp−1
の両辺に x = p を代入すると,
(p − 1)! = pp−1 − M1 pp−2 + M2 pp−3 − · · · + Mp−3 p2 − Mp−2 p + Mp−1
よって
pp−1 − M1 pp−2 + M2 pp−3 − · · · + Mp−3 p2 − Mp−2 p = 0
が成り立つ．
（Mp−1 = (p − 1)! である．
）両辺を p で割って移項すると，
Mp−2 = pp−2 − M1 pp−3 + M2 pp−4 − · · · + Mp−3 p · · · ($)
である．仮定より p は 4 以上であり，また定理 21 より
M1 ≡ 0, M2 ≡ 0, · · · , Mp−2 ≡ 0 ( mod p)
であることから ($) の右辺は p2 で割り切れる．
ゆえに Mp−2 は p2 で割り切れる．Mp−2 は与えられた分数の分子である．
（証明終）
$

Download Report