練習問題 5.10 (解答20) n個の合同方程式
x≡ai (mod. mi), i= 1, 2, · · ·, n が解を持つための必要十分条件は
ai≡aj (mod.(mi, mj)), i, j= 1, 2, · · ·, n
であることを示せ．このとき解はm1, m2, · · ·, mn の最小公倍数を法としてただ一つであること を示せ．
と同一の解を有する．pが素数であるからこの合同式は(x−a)またはf1(x)がpで割り切れる ときにかぎって成り立つ．ゆえにx≡a (mod. p)以外の解はn−1 次の合同方程式
f1(x)≡0 (mod. p)
の解でなければならない．帰納法の仮定によりこの解は n−1 個以下である．
よって(13)の解はn個以下である． ■
さて一般の合同方程式
f(x)≡0 (mod. m)
は，mが素数の場合に解ければ解くことが出来る．それを次に二段階に分けて示そう．
まず，mが素数pのべきつまり m=peのときの解は,m=pのときの解から構成することが 出来ることを示す(定理15)．
次に，mがm=peqf· · ·と因数分解されるときの解は, m=pe, m=qf, · · ·のときの解から 構成することが出来ることを示す(定理16)．
定理 15 合同方程式
f(x)≡0 (mod. pe) (14)
の解は
f(x)≡0 (mod. p) (15)
の解から構成することが出来る．実際 x0 を(15)の一つの解とするとき (1)
f0(x0)6≡0 (mod. p) ならば
f(x)≡0 (mod. pe)
の解のなかにx≡x0 (mod. p)であるものがmod. peに関してただ一つある．
(2)
f0(x0)≡0 (mod. p) ならば
f(x)≡0 (mod. pe) がx≡x0 (mod. p)の解をもつときに，その解から
f(x)≡0 (mod. pe+1) のp個の解が構成されることもあり，あるいは
f(x)≡0 (mod. pe+1) はx≡x0 (mod. pe)なる解をもたないこともある．
証明 eに関する帰納法で示す．
1． e= 2のときに示す．
f(x)≡0 (mod. p2) (16)
(16)の解はもとより(15)を満たす．したがって(16)の解xは pを法として(15)の何らかの解x0
と一致しなければならない．つまり(16)の解xは
x=x0+py (17)
という形をしたもののなかから求められる．ここで整数係数の整式 f(x)に対して f(x+y) =f(x) +yf0(x) +· · ·+ykf(k)(x)
k! +· · ·+ynf(n)(x) n!
と展開され，さらに各 f(k)(x)
k! はxのn−k次の整数係数の整式であることに注意する．そこで (17)を(16)に代入する．
f(x) = f(x0+py)
= f(x0) +pyf0(x0) +p2y2f00(x0)
2! +· · · ≡0 (mod. p2) 上の注意から各 f0(x0) , f00(x0)
2! · · · は整数である．ゆえにこの展開式の第3項以下はp2 で割り きれる．よって(17)の数で(16)を満たすものを求めることは，
f(x0) +pyf0(x0)≡0 (mod. p2)
を満たす y を求めることに帰着する．同じことであるがf(x0)はpで割り切れるので f(x0)
p +yf0(x0)≡0 (mod. p) (18)
ここで二つの場合を区別する．
(1)f0(x0)6≡0 (mod. p)のとき．このときは(18)はただ一つの解をもつ．それを y≡y0 (mod. p)
とする．このときpy≡py0 (mod. p2)だから(17)より x≡x0+py0 (mod. p2) を得る．つまり(16)の解が得られた．
(2)f0(x0)≡0 (mod. p)のとき．このときは(18)は f(x0)
p がさらに pで割り切れなければ解 がない．f(x0)
p が pで割り切れるなら任意のy が解になる．つまり x0, x0+p, x0+ 2p, · · ·, x0+ (p−1)p (mod. p)
が(16)を満たす．すなわち(17)の形の数xは一つも(16)の解を与えないか，あるいはp2を法と してp個の解を与える．
2． eのとき，つまり(14)の解x0 が得られたとして，e+ 1のときの解の構成法を示す．
このときも(mod. p)の解から(mod. p2)の解を構成したのと同様に出来る．すなわち x=x0+pey
の形の数で
f(x)≡0 (mod. pe+1) を満たすものは次のように構成される．
(A)f0(x0)6≡0 (mod. p)ならpe+1 を法としてただ一つ定まる．
(B)f0(x0)≡0 (mod. p)ならpe+1 を法として一つもないか，または p個ある．p個あるの
は f(x0)≡0 (mod. pe+1)のときである． ■
例 5.1 p6= 2が素数で,aは pで割り切れないとする．そのとき x2≡a (mod. p)
に解があるときは，その解は二つある．それを±x0とする．
x06≡0 (mod. p), x06≡ −x0 (mod. p) この場合には,f(x) =x2−a, f0(x) = 2xである．ゆえに
f0(±x0) =±2x06≡0 (mod. p) これは上定理の(1)の場合である．ゆえに
x2≡a (mod. pe) には二つの解がある．
例えば，
x2≡2 (mod. 7) の解は x0≡ ±3 である．これから
x2≡2 (mod.49) の解を求めてみよう．そのためにx= 3 + 7y とおく．
(3 + 7y)2≡2 (mod.49) から 9 + 42y≡2 (mod.49) つまり 6y≡ −1 (mod.7)
∴ y≡1 (mod.7) したがって x≡10 (mod.49)
他の解は x≡ −10≡39 (mod.49) 定理 16
法 mを素数べきに因数分解して
m=peqf· · ·
とするとき，
f(x) ≡ (mod. pe) (19)
f(x) ≡ (mod. qf) (20)
· · · がそれぞれl, l0, · · · 個の解をもつとすれば，
f(x)≡0 (mod. m) (21)
は ll0· · ·個の解をもつ．それれは
x ≡ α (mod. pe)
x ≡ β (mod. qf) (22)
· · · · · ·
から求められる．ここでα, β, · · ·はそれぞれpe, qf, · · ·を法としてのf(x)≡0の任意の解の一 組である．
証明 xが(21)の解ならば(19)，(20)の解である．したがって(22)を満たす．
逆に(21)を満たす xは，(19)，(20)を満たすから，(21)を満たす． ■
例 5.2
x2≡1 (mod. 3) x2≡1 (mod. 4)
の解はそれぞれ二つある．それらをα≡ ±1 (mod.3) とβ≡ ±1 (mod.4)とする．
x2≡1 (mod.12) は四つの解をもつ．それらは，
x≡1 x≡1
) x≡1 x≡ −1
) x≡ −1 x≡1
) x≡ −1 x≡ −1
) (mod. 3) (mod. 4) から求められる．
∴ x≡1, x≡7, x≡5, x≡11 (mod. 12) 練習問題 5.11 (解答21) 次の合同方程式を解け．
(1) x2+x+ 1≡3 (mod.25) (2) x2≡1 (mod. 39)