(2) n5−nは10の倍数である．
(3) nが奇数ならn2−1は8で割り切れる．
(4) n4+ 2n3+ 11n2+ 10nは、24の倍数である．
練習問題 5.5 (解答15)
(1) 整数a, bに対して，a2+b2=c2となる整数cが存在するとき，a, bの少なくとも一方は3 の倍数であるとを示せ．
(2) 整数a, b, cが a2+b2=c2を満たすとき，a, b, c のうち少なくとも1つは5 の倍数であ ることを示せ．
練習問題 5.6 (解答16) a, b は正の整数で，aを 11 で割ると余りが3，a3+b を 11で割ると 余りが 4であるという．このときb を11で割ると，余りはいくらか．
もまたmを法とする剰余系である．なぜならもし axi≡axj (mod. m) なら,aがmと互いに素であることから
xi≡xj (mod. m) となる．それはi=j のときにかぎるからである．
ゆえに任意のbに対して {x1, x2, · · ·, xm}のなかのただ一つ axi ≡b (mod. m) となるxi が存在する．
(ii) (a, m) =d >1のとき．
ax≡b (mod. m) (7)
に解があるとすると, ax−b = mN (N は整数) と表される．ゆえに b = ax−mN は d= (a, m)で割りきれる．そこで
a=da0, m=dm0, b=db0 とおく．(7)は定理11より
a0x≡b0 (mod m0) (8)
と同値である．ここでa0 とm0 は互いに素であるから(8)を満たすxはm0 を法とする一つ の類である．それをx≡x0 (mod. m)とする．(8)の解は
x=x0+m0t tは任意の整数 (9) によって与えられる．t1 とt2 に対する xがm を法として合同になるのは
m0(t1−t2)≡0 (mod. m) つまり
t1−t2≡0 (mod. d)
となるときにかぎる．したがって，(9)でt をdを法とする剰余系{0, 1, · · ·, d−1}の値 を与えるとき,mを法とする(7)のすべての解が得られる．すなわちその解の個数はdであ
る． ■
このように合同方程式(7)を解くことは，一次不定方程式 ax+my =b の整数解を求めることと同じである．
定理 13
m1, m2, · · ·, mk が二つずつ互いに素で,a1, a2, · · ·, ak は任意の整数であるとする．
x ≡ a1 (mod. m1) x ≡ a2 (mod. m2)
· · · · · · (10)
x ≡ ak (mod. mk) を満たす xは M =m1m2· · ·mk を法としてただ一つ存在する．
証明 第一の合同式を満たすxは
x=a1+m1t (11)
と書ける．これが第二の合同式も満たすのは
a1+m1t≡a2 (mod. m2) すなわち
m1t≡a2−a1 (mod. m2) のときである．ところが,m1 とm2 は互いに素なのでこれには
t=t0+m2s
のように m2 を法とするただ一つの類が解として存在する．これを(11)に代入して x=a1+m1t0+m1m2s
つまり
x≡a1+m1t0 (mod. m1m2)
この一つの合同式を(10)の最初の二つの合同式に置き換えてよい．同様の操作を繰りかえすこと ができる．ついには
x≡x0 (mod. M)
を得る． ■
この定理は 中国の剰余定理(Chinese Remainder Teorem) と呼ばれる．中国古代(一世紀 頃)の書『孫子算経』の中に，「3で割れば2余り，5で割れば3余り，7で割れば2余るような数は 何か」という問いと解の求め方が述べられている．この種の問題が孫子以降の中国の算術の書に見 られる．下って16世紀の終わり頃の『算法統宗』(程大位)にはこの孫子の問いに対する解の求め 方が歌で述べられている．このような歴史があるのでこの定理が上のように呼ばれるのである．
ここでガウス(Gauss)による対称性を用いたより美しい別証を紹介する．
ガウスの別証明
M =m1m2· · ·mkに対し
M =m1M1=m2M2=· · ·=mkMk (12) とおく．そして
Mntn≡1 (mod. mk) (n= 1, 2, · · ·, k) となる tn (n= 1, 2, · · ·, k)を求める．このとき(10)の解は
x≡a1M1t1+a2M2t2+· · ·+akMktk (mod. M) である．実際，(12)から
anMntn≡an (mod. mn) で,M1, · · ·, Mk のうちMn 以外はすべてmn で割りきれるので，
x≡an (mod. mn)(n= 1, 2, · · ·, k) である．
唯一の解であることは,x1 とx2 がともに(10)を満たせば x1≡x2 (mod. mn)(n= 1, 2, · · ·, k) なので,m1, m2, · · ·, mk の最小公倍数M に関して
x1≡x2 (mod. M)
となるからである． ■
練習問題 5.7 (解答17)
26x≡1 (mod.57) を解け．
練習問題 5.8 (解答18) 3で割れば1余り，5で割れば2余り，7で割れば3余る正で最小の整数 を求めよ．
練習問題 5.9 (解答19) 法m, nの最大公約数をd，最小公倍数をl とする．
( x≡a (mod. m), x≡b (mod. n).
が解を持つ必要十分条件は
a≡b (mod. d)
であることを示せ．またこのとき，解はl を法としてただ一つであることを示せ．
練習問題 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 の最小公倍数を法としてただ一つであること を示せ．