■簡単な合同方程式の解き方■
 高校の数学Aの教科書では,通常,整式の合同や合同式には触れない.発展学習として,軽く触れている教科書,参考書はある.
 すなわち,合同式の公式等を「覚えているか」どうかを問う大学入試問題は出題されないが,その性質は高校レベルで簡単に分かるものなので,合同式の性質を題材とする大学入試問題はあり得る.
【合同の定義】
 a, bは整数,mは正の整数とする.
 a−bmで割り切れるとき,「abmを法(modulus)として合同である」といい
a≡b (mod m)
と書く.
abmを法として合同である」とは「abmで割った余りが等しい」と言うこともできる.
(証明)
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−bmで割り切れる ⇔ r1−r2=0
r1=r2

【合同式の基本的性質】
(1.1) 反射律
a≡a (mod m)
(証明)
a−a=0=0·mだから,aamを法として合同であると言える.
(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を整数,cmの最大公約数をgとすると
(3.5)
ac≡bc (mod m)ならば
(3.6)
 特に,cmが互いに素であるとき
ac≡bc (mod m)ならばa≡b (mod m)
(3.6)は,合同式の両辺をmと互いに素な数で割ってもよいことを示している.
(証明)
(3.5)を示す
ac≡bc (mod m)ならばac−bc=kmとなる整数kが存在する.
cmの最大公約数を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−bm'で割り切れる.
よって
ac≡bc (mod m)ならば
(3.6)を示す
 特に,cmが互いに素ならばg=1だから
a≡b (mod m)
(4.1) [バシェの定理]
 a, bは整数,mは正の整数とする.
合同方程式a≡b (mod m)
の解xについて
1) amが互いに素のとき,解はただ1つ存在する.
2) a, mの最大公約数がg (≠1)で,bgで割り切れるとき,g個の非合同解が存在する.
3) a, mの最大公約数がg (≠1)で,bgで割り切れないとき,解は存在しない.

【例題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で分類すると,整数は次の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+4tは整数)
これを元の問題に戻すと
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+2sは整数)
これを元の問題に戻すと
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+8tは整数)
これを元の問題に戻すと
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+15sは整数)
これを元の問題に戻すと
11(19s+15)−19y=13
19y=11×19s+152
y=11s+8
sは整数)…(答)

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

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

【例題4.1】
 7で割ると1余り,5で割ると2余る整数をすべて求めてください.
(解答)

(1)よりx=7s+1sは整数)とおける.
これを(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+22tは整数)…(答)
(算数で攻める・・・)
(1)から,35で割ったときの余りは,1,8,15,22,29
このうちで,5で割ると2余るのは22
x=35t+22tは整数)・・・(答)
【例題4.2】のように数字が大きくなったときに,この答案の書き方では,大変だという心配はある
【例題4.2】
 5で割ると2余り,7で割ると3余り,11で割ると4余る整数をすべて求めてください.
(解答)

(1)よりx=5s+2sは整数)とおける.
これを(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+3tは整数)とおける.
x=5(7t+3)+ 2=35t+17tは整数)…(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+10wは整数)…(5)
(5)を(4)に代入する
x=35(11w+10)+17=385w+367wは整数)…(答)
(算数で攻める・・・)
(1)(2)から,35で割ったときの余りは17
つまり,385で割ったときの余りは,
 17,52,8/7,122,157,192,227,262,297,332,367
このうちで,11で割ると4余るのは367
x=385t+367tは整数)・・・(答)

n次合同式(n次合同方程式)

を解くための解の公式のようなものはないが,次の例のように気長に計算すれば,いずれは解が求まる.
【例題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
すなわち解は次の2通りある.
x≡1 (mod 5)
x≡4 (mod 5)
※この問題が,もしとなっていれば解は1通り,となっていれば解はなし,となっていれば解は2通りある.
 一般に,mod mのn次合同式の解はm通り以下であるとは言えるが,具体的に何通りになるのかは問題ごとに異なる.
【例題5.2】
となる整数xを求めてください.
(解答)


は1つの解
の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が大きな値の場合には,分類が煩雑になるため,この方法だけで解くことは容易でない.
●==目次に戻る