← PC版は別頁
■簡単な合同方程式の解き方■
　高校の数学Aの教科書では，通常，整式の合同や合同式には触れない．発展学習として，軽く触れている教科書，参考書はある．
　すなわち，合同式の公式等を「覚えているか」どうかを問う大学入試問題は出題されないが，その性質は高校レベルで簡単に分かるものなので，合同式の性質を題材とする大学入試問題はあり得る．
【合同の定義】
　a, bは整数，mは正の整数とする．
　a−bがmで割り切れるとき，「aとbはmを法(modulus)として合同である」といい
a≡b (mod m)
と書く．
「aとbはmを法として合同である」とは「aとbをmで割った余りが等しい」と言うこともできる．
（証明）
a=q1m+r1 (0≦r1<m)
b=q2m+r2 (0≦r2<m)
とおくと
a−b=q1m+r1−q2m−r2 (0≦r1<m)
=(q1−q2)m+(r1−r2) (0≦r1<m)
(−m<r1−r2<m)
だから
a−bがmで割り切れる ⇔ r1−r2=0
⇔ r1=r2

【合同式の基本的性質】
(1.1) 反射律
a≡a (mod m)
（証明）
a−a=0=0·mだから，aとaはmを法として合同であると言える．
(1.2) 対称律
a≡b (mod m)ならばb≡a (mod m)
（証明）
a−b=q·mならばb−a=−q·mだから成り立つ．
(1.3) 推移律
a≡b (mod m)かつb≡c (mod m)
　　ならばa≡c (mod m)
（証明）
a−b=q1m
b−c=q2m
ならば
a−c=(a−b)+(b−c)=q1m+q2m
=(q1+q2)m
だから成り立つ

【合同式の四則計算(1)】
a≡b (mod m)かつc≡d (mod m)ならば
(2.1) a+c≡b+d (mod m)
(2.2) a−c≡b−d (mod m)
(2.3) ac≡bd (mod m)
（証明）
a≡b (mod m)かつc≡d (mod m)ならば
a−b=q1m
c−d=q2m
(2.1)
(a+c)−(b+d)=(a−b)+(c−d)
=q1m+q2m=(q1+q2)m
だから，a+c≡b+d (mod m)が成り立つ．
(2.2)
(a−c)−(b−d)=(a−b)−(c−d)
=q1m−q2m=(q1−q2)m
だから，a−c≡b−d (mod m)が成り立つ．
(2.3)
ac−bd=ac−bc+bc−bd
=(a−b)c+b(c−d)
=q1mc+bq2m=(q1c+q2b)m
だから，ac≡bd (mod m)が成り立つ．
※初歩的なことであるが，商については，成り立たない．そもそも，整数の商が整数になるとは限らないから，商がmで割り切れるかどうかという議論には意味がない．

【合同式の四則計算(2)】
a≡b (mod m)のとき，kを整数，nを正の整数とすると
(3.1) 両辺に同じ数を足してもよい
a+k≡b+k (mod m)
(3.2) 両辺から同じ数を引いてもよい
a−k≡b−k (mod m)
(3.3) 両辺に同じ数を掛けてもよい
ka≡kb (mod m)
(3.4) 両辺を何乗かしてもよい
an≡bn (mod m)
（証明）
a−b=qmのとき
(3.1)
(a+k)−(b+k)=a−b=qmだから
a+k≡b+k (mod m)が成り立つ
(3.2)
(a−k)−(b−k)=a−b=qmだから
a−k≡b−k (mod m)が成り立つ
(3.3)
ka−kb=k(a−b)=kqmだから
ka≡kb (mod m)が成り立つ
(3.4)


だから
が成り立つ
a≡b (mod m)のとき，cを整数，cとmの最大公約数をgとすると
(3.5)
ac≡bc (mod m)ならば
(3.6)
　特に，cとmが互いに素であるとき
ac≡bc (mod m)ならばa≡b (mod m)
(3.6)は，合同式の両辺をmと互いに素な数で割ってもよいことを示している．
（証明）
(3.5)←を示す
ac≡bc (mod m)ならばac−bc=kmとなる整数kが存在する．
cとmの最大公約数をgとすると
c=c'g m=m'g 　　（c', m'は互いに素）
とおける．このとき
ac−bc=km
(a−b)c=km
より
(a−b)c'g=km'g
(a−b)c'=km'
c', m'は互いに素だから，a−bはm'で割り切れる．
よって
ac≡bc (mod m)ならば
(3.6)←を示す
　特に，cとmが互いに素ならばg=1だから
a≡b (mod m)

(4.1) ［バシェの定理］
　a, bは整数，mは正の整数とする．
合同方程式a≡b (mod m)
の解xについて
1)　aとmが互いに素のとき，解はただ１つ存在する．
2)　a, mの最大公約数がg (≠1)で，bがgで割り切れるとき，g個の非合同解が存在する．
3)　a, mの最大公約数がg (≠1)で，bがgで割り切れないとき，解は存在しない．

【例題1.1】
5x≡3 (mod 7)を解いてください．
（解答）
5×3=15=7×2+1
だから
5×3≡1 (mod 7)
両辺に3を掛けると
5×9≡3 (mod 7)
したがって，x≡9≡2 (mod 7)は1つの解になる．
(4.1)により，解はただ1つであるから，
x≡2 (mod 7)…（答）
単純計算で検算してみる
mod 7で分類すると，整数は次の７種類に分かれる．
x=7n, 7n+1, 7n+2, 7n+3, 7n+4, 7n+5, 7n+6
各々5xを求めると
5x=35n≡0 (mod 7)
5x=35n+5≡5 (mod 7)
5x=35n+10≡3 (mod 7)⇒〇
5x=35n+15≡1 (mod 7)
5x=35n+20≡6 (mod 7)
5x=35n+25≡4 (mod 7)
5x=35n+30≡2 (mod 7)
以上のように，x=7n+2の場合だけ，合同式を満たす．

【例題1.2】
17x≡11 (mod 13)を解いてください．
（解答）
17×3=51=13×4−1
17×3≡ −1 (mod 13)
17×(−3)≡ 1 (mod 13)
17×(−33)≡ 11 (mod 13)
x=−33≡ 6 (mod 13)…（答）
検算
x≡ 6 (mod 13)
ならば
17x≡ 102=13×7+11 (mod 13)
17x≡ 11 (mod 13)

【例題2.1】
15x≡6 (mod 21)を解いてください．
（解答）
15と21の最大公約数はg=3
6はg=3の倍数になっているから解は存在する（3個ある）
15x≡6 (mod 21) の各数を3で割ると
5x≡2 (mod 7) −5=−7+2
だから
5×(−1)≡2 (mod 7)
1つの解は
x≡−1≡6 (mod 7)
元の問題の解は
x≡6, 13, 20 (mod 21)
検算
15×6=90=21×4+6≡6 (mod 21)
15×13=195=21×9+6≡6 (mod 21)
15×20=300=21×14+6≡6 (mod 21)
【例題2.2】
35x≡15 (mod 20)を解いてください．
（解答）
35と20の最大公約数はg=5
15はg=5の倍数になっているから解は存在する（5個ある）
35x≡15 (mod 20)
の各数を5で割ると
7x≡3 (mod 4)
7=4+3
だから
7×1≡3 (mod 4)
1つの解は
x≡1 (mod 4)
元の問題の解は
x≡1, 5, 9, 13, 17 (mod 20)
検算
35×1=35=20+15≡15 (mod 20)
35×5=175=20×8+15≡15 (mod 20)
35×9=315=20×15+15≡15 (mod 20)
35×13=455=20×15+15≡15 (mod 20)
35×17=595=20×29+15≡15 (mod 20)

【例題3.1】
7x+5y=3となる整数x, yを求めてください．
（解答）
mod 5で
7x≡3 (mod 5)
7×4=28=5×5+3
7×4≡3 (mod 5)
x≡4 (mod 5)
x=5t+4（tは整数）
これを元の問題に戻すと
7(5t+4)+5y=3
5y=−25t−25
y=−7t−5
（tは整数）
（別解）
mod 7で
5y≡3 (mod 7)
5×2=10=7+3
5×2≡3 (mod 7)
y≡2 (mod 7)
y=7s+2（sは整数）
これを元の問題に戻すと
7x+5(7s+2)=3
7x=−35s−7
x=−5s−1
（sは整数）

【例題3.2】
11x−19y=13となる整数x, yを求めてください．
（解答）
mod 11で
問題から
−19y≡13 (mod 11)…(1)
他方で，自明なこととして
22y≡0 (mod 11)…(2)
(1)+(2)
3y≡13 (mod 11)…(3)
ところで
3×(−3)=−9=−11+2
だから
3×(−3)≡2 (mod 11)
1つの解は
y≡−3≡8 (mod 11)
したがって
y=11t+8（tは整数）
これを元の問題に戻すと
11x−19(11t+8)=13
11x=19×11t+165
x=19t+15
（tは整数）
（別解）
mod 19で
問題から
11x≡13 (mod 19)…(1)
他方で，自明なこととして
19x≡0 (mod 19)…(2)
(2)−(1)
8x≡−13 (mod 19)…(3)
(1)−(3)
3x≡7 (mod 19)…(4)
ところで
3×(−4)=−12=−19+7
だから
3×(−4)≡7 (mod 19)
1つの解は
x≡−4≡15 (mod 19)
したがって
x=19s+15（sは整数）
これを元の問題に戻すと
11(19s+15)−19y=13
19y=11×19s+152
y=11s+8
（sは整数）…（答）

　次の定理は「中国剰余定理」と呼ばれる．このページでは，定理の証明は省略するが，この定理によって存在と一意性が示される連立１次合同式の解き方を考えてみる．
　が互いに素であるとき，連立１次合同式

はを法としてただ1つの解を持つ．

【例題4.1】
　7で割ると1余り，5で割ると2余る整数をすべて求めてください．
（解答）

(1)よりx=7s+1（sは整数）とおける．
これを(2)に代入すると
7s+1≡2 (mod 5)
7s≡1 (mod 5)
ここで
5s≡0 (mod 5)
だから，差を取ると
2s≡1 (mod 5)
2×3=6=5+1
だから
s≡3 (mod 5)
s=5t+3
結局
x=7(5t+3)+1=35t+22（tは整数）…（答）
（算数で攻める･･･）
(1)から，35で割ったときの余りは，1,8,15,22,29
このうちで，5で割ると2余るのは22
x=35t+22（tは整数）･･･（答）
【例題4.2】のように数字が大きくなったときに，この答案の書き方では，大変だという心配はある

【例題4.2】
　5で割ると2余り，7で割ると3余り，11で割ると4余る整数をすべて求めてください．
（解答）

(1)よりx=5s+2（sは整数）とおける．
これを(2)に代入すると
5s+2≡3 (mod 7)
5s≡1 (mod 7)…(2’)
ところで
7s≡0 (mod 7)
だから，(2’)との差を取ると
2s≡−1 (mod 7)
ここで
2×3=6
だから
s≡3 (mod 7)
s=7t+3（tは整数）とおける．
x=5(7t+3)+ 2=35t+17（tは整数）…(4)
これを(3)に代入
35t+17≡4 (mod 11)
35t≡−13≡−2≡9 (mod 11)
ところで
33t≡0 (mod 11)
だから，差を取ると
2t≡9 (mod 11)
ここで
2×10=20=11+9
だから
2×10≡9 (mod 11)
t≡10 (mod 11)
t=11w+10（wは整数）…(5)
(5)を(4)に代入する
x=35(11w+10)+17=385w+367（wは整数）…（答）
（算数で攻める･･･）
(1)(2)から，35で割ったときの余りは17
つまり，385で割ったときの余りは，
　17,52,8/7,122,157,192,227,262,297,332,367
このうちで，11で割ると4余るのは367
x=385t+367（tは整数）･･･（答）

ｎ次合同式（ｎ次合同方程式）

を解くための解の公式のようなものはないが，次の例のように気長に計算すれば，いずれは解が求まる．
【例題5.1】
となる整数xを求めてください．
（解答）
mod 5で整数は次のいずれかの形に書ける．
5t, 5t±1, 5t±2
各々題意を満たすかどうか調べてみると
2(5t)2+3≡3 (mod 5)
2(5t±1)2+3≡5≡0 (mod 5)
2(5t±2)2+3≡11≡1 (mod 5)
したがって，x=5t±1
すなわち解は次の２通りある．
x≡1 (mod 5)
x≡4 (mod 5)
※この問題が，もしとなっていれば解は1通り，となっていれば解はなし，となっていれば解は2通りある．
　一般に，mod mのｎ次合同式の解はm通り以下であるとは言えるが，具体的に何通りになるのかは問題ごとに異なる．

【例題5.2】
となる整数xを求めてください．
（解答）


は1つの解
が の１つの解であるとき，x≡m−a (mod m)もx2≡b (mod m)の解になる．
（∵）
a2≡b (mod m)ならば
(m−a)2=m2−2am+a2 (mod m)
により
(m−a)2≡b (mod m)
となるから
x≡8 (mod 11)は解
したがって，x≡3, 8 (mod 11)…（答）
　mod mの合同方程式が与えられたとき，上記の【例題9, 10】のようにmの剰余類で分類すれば解けるが，mが大きな値の場合には，分類が煩雑になるため，この方法だけで解くことは容易でない．
●==目次に戻る