簡単な合同方程式の解き方

■簡単な合同方程式の解き方■

　高校の数学Aの教科書では，通常，整式の合同や合同式には触れない．発展学習として，軽く触れている教科書，参考書はある．

【合同の定義】
　 $a,\hspace{2}b$ は整数， $m$ は正の整数とする．
　 $a-b$ が $m$ で割り切れるとき，「 $a$ と $b$ は $m$ を法(modulus)として合同である」といい
$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$
と書く．

「 $a$ と $b$ は $m$ を法として合同である」とは「 $a$ と $b$ を $m$ で割った余りが等しい」と言うこともできる．

（証明）
$a=q_1m+ r_1\hspace{10}(0\underline{\le}r_1\lt m)$
$b=q_2m+ r_2\hspace{10}(0\underline{\le}r_2\lt m)$
とおくと
$a-b=q_1m+ r_1-q_2m-r_2$
$=(q_1-q_2)m+ (r_1-r_2)$
$(-m\lt r_1-r_2\lt m)$
だから
$a-b$ が $m$ で割り切れる $\leftarrow\rightarrow$ $r_1-r_2=0$
$\leftarrow\rightarrow$ $r_1=r_2$

【合同式の基本的性質】

(1.1) 反射律
$a\equiv a\hspace{2}(\rm{mod}\hspace{2}m)$

（証明）
$a-a=0=0\cdot m$ だから， $a$ と $a$ は $m$ を法として合同であると言える．

(1.2) 対称律
$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ ならば $b\equiv a\hspace{2}(\rm{mod}\hspace{2}m)$

（証明）
$a-b=q\cdot m$ ならば $b-a=-q\cdot m$ だから成り立つ．

(1.3) 推移律
$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ かつ $b\equiv c\hspace{2}(\rm{mod}\hspace{2}m)$
　　ならば $a\equiv c\hspace{2}(\rm{mod}\hspace{2}m)$

（証明）
$a-b=q_1m$
$b-c=q_2m$
ならば
$a-c=(a-b)+ (b-c)=q_1m+ q_2m$
$=(q_1+ q_2)m$
だから成り立つ

【合同式の四則計算(1)】

$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ かつ $c\equiv d\hspace{2}(\rm{mod}\hspace{2}m)$ ならば
(2.1) $a+ c\equiv b+ d\hspace{2}(\rm{mod}\hspace{2}m)$
(2.2) $a-c\equiv b-d\hspace{2}(\rm{mod}\hspace{2}m)$
(2.3) $ac\equiv bd\hspace{2}(\rm{mod}\hspace{2}m)$

（証明）
$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ かつ $c\equiv d\hspace{2}(\rm{mod}\hspace{2}m)$ ならば
$a-b=q_1m$
$c-d=q_2m$
(2.1) $(a+ c)-(b+ d)=(a-b)+ (c-d)$
$=q_1m+ q_2m=(q_1+ q_2)m$
だから， $a+ c\equiv b+ d\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ．
(2.2) $(a-c)-(b-d)=(a-b)-(c-d)$
$=q_1-q_2m=(q_1-q_2)m$
だから， $a-c\equiv b-d\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ．
(2.3) $ac-bd=ac-bc+ bc-bd$
$=(a-b)c+ b(c-d)$
$=q_1mc+ bq_2m=(q_1c+ q_2b)m$
だから， $ac\equiv bd\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ．
※初歩的な注意であるが，商 $a/c\hspace{2},\hspace{3}b/d$ については，成り立たない．

【合同式の四則計算(2)】

$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ のとき， $k$ を整数， $n$ を正の整数とすると
(3.1) 両辺に同じ数を足してもよい
$a+ k\equiv b+ k\hspace{2}(\rm{mod}\hspace{2}m)$
(3.2) 両辺から同じ数を引いてもよい
$a-k\equiv b-k\hspace{2}(\rm{mod}\hspace{2}m)$
(3.3) 両辺に同じ数を掛けてもよい
$ka\equiv kb\hspace{2}(\rm{mod}\hspace{2}m)$
(3.4) 両辺を何乗かしてもよい
$a^n\equiv b^n\hspace{2}(\rm{mod}\hspace{2}m)$

（証明）
$a-b=qm$ のとき
(3.1)
$(a+ k)-(b+ k)=a-b=qm$ だから
$a+ k\equiv b+ k\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ
(3.2)
$(a-k)-(b-k)=a-b=qm$ だから
$a-k\equiv b-k\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ
(3.3)
$ka-kb=k(a-b)=kqm$ だから
$ka\equiv kb\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ
(3.4)
$a^n-b^n=(a-b)(a^{n-1}+ a^{n-2}b+\cdots+ ab^{n-2}+ b^{n-1})$
$=qm(a^{n-1}+ a^{n-2}b+\cdots+ ab^{n-2}+ b^{n-1})$
だから
$a^n\equiv b^n\hspace{2}(\rm{mod}\hspace{2}m)$ が成り立つ

$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$ のとき， $c$ を整数， $c$ と $m$ の最大公約数を $g$ とすると
(3.5)
$ac\equiv bc\hspace{2}(\rm{mod}\hspace{2}m)$ ならば $a\equiv b\hspace{2}(\rm{mod}\hspace{2}\frac{m}{g})$
(3.6)
　特に， $c$ と $m$ が互いに素であるとき
$ac\equiv bc\hspace{2}(\rm{mod}\hspace{2}m)$ ならば $a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$

(3.6)は，合同式の両辺をmと互いに素な数で割ってもよいことを示している．

（証明）
$ac\equiv bc\hspace{2}(\rm{mod}\hspace{2}m)$ ならば $ac-bc=km$ となる整数 $k$ が存在する．
$c$ と $m$ の最大公約数を $g$ とすると
$c=c\apos g$
$m=m\apos g$
　　（ $c\apos,\hspace{3}m\apos$ は互いに素）
とおける．このとき
$ac-bc=km$
より
$(a-b)c\apos g=km\apos g$
$(a-b)c\apos=km\apos$
$c\apos,\hspace{3}m\apos$ は互いに素だから， $a-b$ は $m\apos$ で割り切れる．
よって
$ac\equiv bc\hspace{2}(\rm{mod}\hspace{2}m)$ ならば $a\equiv b\hspace{2}(\rm{mod}\hspace{2}\frac{m}{g})$
　特に， $c$ と $m$ が互いに素ならば $g=1$ だから
$a\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$

(4.1) ［バシェの定理］
　 $a,\hspace{3}b$ は整数， $m$ は正の整数とする．

合同方程式 $ax\equiv b\hspace{2}(\rm{mod}\hspace{2}m)$

の解 $x$ について
1)　 $a$ と $m$ が互いに素のとき，解はただ１つ存在する．
2)　 $a,\hspace{2}m$ の最大公約数が $g\hspace{2}(\ne 1)$ で， $b$ が $g$ で割り切れるとき， $g$ 個の非合同解が存在する．
3)　 $a,\hspace{2}m$ の最大公約数が $g\hspace{2}(\ne 1)$ で， $b$ が $g$ で割り切れないとき，解は存在しない．

【例題1.1】
$5x\equiv 3\hspace{2}(\rm{mod}\hspace{2}7)$ を解いてください．

（解答）
$5\times 3=15=7\times 2+ 1$
だから
$5\times 3\equiv 1\hspace{2}(\rm{mod}\hspace{2}7)$
両辺に3を掛けると
$5\times 9\equiv 3\hspace{2}(\rm{mod}\hspace{2}7)$
したがって， $x\equiv 9\equiv 2\hspace{2}(\rm{mod}\hspace{2}7)$ は1つの解になる．
(4.1)により，解はただ1つであるから，
$x\equiv 2\hspace{2}(\rm{mod}\hspace{2}7)$ …（答）

単純計算で検算してみる
$\rm{mod}\hspace{2}7$ で分類すると，整数は次の７種類に分かれる．
$x=7n,\hspace{3}7n+ 1,\hspace{3}7n+ 2,\hspace{3}7n+ 3,\hspace{3}7n+ 4,\hspace{3}7n+ 5,\hspace{3}7n+ 6$
各々 $5x$ を求めると
$5x=35n\equiv 0\hspace{3}(\rm{mod}\hspace{2}7)$
$5x=35n+ 5\equiv 5\hspace{3}(\rm{mod}\hspace{2}7)$
$5x=35n+ 10\equiv 3\hspace{3}(\rm{mod}\hspace{2}7)\hspace{3}\leftarrow\circ$
$5x=35n+ 15\equiv 1\hspace{3}(\rm{mod}\hspace{2}7)$
$5x=35n+ 20\equiv 6\hspace{3}(\rm{mod}\hspace{2}7)$
$5x=35n+ 25\equiv 4\hspace{3}(\rm{mod}\hspace{2}7)$
$5x=35n+ 30\equiv 2\hspace{3}(\rm{mod}\hspace{2}7)$
以上のように， $x=7n+ 2$ の場合だけ，合同式を満たす．

【例題1.2】
$17x\equiv 11\hspace{2}(\rm{mod}\hspace{2}13)$ を解いてください．

（解答）
$17\times 3=51=13\times 4-1$
$17\times 3\equiv -1\hspace{10}(\rm{mod}\hspace{5}13)$
$17\times(-3)\equiv 1\hspace{10}(\rm{mod}\hspace{5}13)$
$17\times(-33)\equiv 11\hspace{10}(\rm{mod}\hspace{5}13)$
$x=-33\equiv 6\hspace{10}(\rm{mod}\hspace{5}13)$ …（答）

検算
$x\equiv 6\hspace{10}(\rm{mod}\hspace{5}13)$
ならば
$17x\equiv 102=13\times 7+ 11\hspace{10}(\rm{mod}\hspace{5}13)$
$17x\equiv 11\hspace{10}(\rm{mod}\hspace{5}13)$

【例題2.1】
$15x\equiv 6\hspace{5}(\rm{mod}\hspace{5}21)$ を解いてください．

（解答）
15と21の最大公約数は $g=3$
6は $g=3$ の倍数になっているから解は存在する（3個ある）
$15x\equiv 6\hspace{5}(\rm{mod}\hspace{5}21)$
の各数を3で割ると
$5x\equiv 2\hspace{5}(\rm{mod}\hspace{5}7)$
$-5=-7+ 2$
だから
$5\times (-1)\equiv 2\hspace{5}(\rm{mod}\hspace{5}7)$
1つの解は
$x\equiv -1\equiv 6\hspace{5}(\rm{mod}\hspace{5}7)$
元の問題の解は
$x\equiv 6,\hspace{3}13,\hspace{3}20\hspace{5}(\rm{mod}\hspace{5}21)$

検算
$15\times 6=90=21\times 4+ 6\equiv 6\hspace{5}(\rm{mod}\hspace{5}21)$
$15\times 13=195=21\times 9+ 6\equiv 6\hspace{5}(\rm{mod}\hspace{5}21)$
$15\times 20=300=21\times 14+ 6\equiv 6\hspace{5}(\rm{mod}\hspace{5}21)$

【例題2.2】
$35x\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$ を解いてください．

（解答）
35と20の最大公約数は $g=5$
15は $g=5$ の倍数になっているから解は存在する（5個ある）
$35x\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$
の各数を5で割ると
$7x\equiv 3\hspace{5}(\rm{mod}\hspace{5}4)$
$7=4+ 3$
だから
$7\times 1\equiv 3\hspace{5}(\rm{mod}\hspace{5}4)$
1つの解は
$x\equiv 1\hspace{5}(\rm{mod}\hspace{5}4)$
元の問題の解は
$x\equiv 1,\hspace{3}5,\hspace{3}9,\hspace{3}13,\hspace{3}17\hspace{5}(\rm{mod}\hspace{5}20)$

検算
$35\times 1=35=20+ 15\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$
$35\times 5=175=20\times 8+ 15\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$
$35\times 9=315=20\times 15+ 15\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$
$35\times 13=455=20\times 22+ 15\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$
$35\times 17=595=20\times 29+ 15\equiv 15\hspace{5}(\rm{mod}\hspace{5}20)$

【例題3.1】
$7x+ 5y=3$ となる整数 $x,\hspace{2}y$ を求めてください．

（解答）
$\rm{mod}\hspace{5}5$ で
$7x\equiv 3\hspace{5}(\rm{mod}\hspace{5}5)$
$7\times 4=28=5\times 5+ 3$
$7\times 4\equiv 3\hspace{5}(\rm{mod}\hspace{5}5)$
$x\equiv 4\hspace{5}(\rm{mod}\hspace{5}5)$
$x=5t+ 4$ （ $t$ は整数）
これを元の問題に戻すと
$7(5t+ 4)+ 5y=3$
$5y=-35t-25$
$y=-7t-5$
$\{\begin{matrix}x=5t+ 4\\y=-7t-5\end{matrix}$ （ $t$ は整数）

（別解）
$\rm{mod}\hspace{5}7$ で
$5y\equiv 3\hspace{5}(\rm{mod}\hspace{5}7)$
$5\times 2=10=7+ 3$
$5\times 2\equiv 3\hspace{5}(\rm{mod}\hspace{5}7)$
$y\equiv 2\hspace{5}(\rm{mod}\hspace{5}7)$
$y=7s+ 2$ （ $s$ は整数）
これを元の問題に戻すと
$7x+ 5(7s+ 2)=3$
$7x=-35s-7$
$x=-5s-1$
$\{\begin{matrix}x=-5s-1\\y=7s+ 2\end{matrix}$ （ $s$ は整数）

【例題3.2】
$11x-19y=13$ となる整数 $x,\hspace{2}y$ を求めてください．

（解答）
$\rm{mod}\hspace{5}11$ で
問題から
$-19y\equiv 13\hspace{5}(\rm{mod}\hspace{5}11)$ …(1)
他方で，自明なこととして
$22y\equiv 0\hspace{5}(\rm{mod}\hspace{5}11)$ …(2)
(1)+(2)
$3y\equiv 13\equiv 2\hspace{5}(\rm{mod}\hspace{5}11)$ …(3)
ところで
$3\times(-3)=-9=-11+ 2$
だから
$3\times(-3)\equiv 2\hspace{5}(\rm{mod}\hspace{5}11)$
1つの解は
$y\equiv -3\equiv 8\hspace{5}(\rm{mod}\hspace{5}11)$
したがって
$y=11t+ 8$ （ $s$ は整数）
これを元の問題に戻すと
$11x-19(11t+ 8)=13$
$11x=19\times 11t+ 165$
$x=19t+ 15$
$\{\begin{matrix}x=19t+ 15\\y=11t+ 8\end{matrix}$ （ $t$ は整数）…（答）

（別解）
$\rm{mod}\hspace{5}19$ で
問題から
$11x\equiv 13\hspace{5}(\rm{mod}\hspace{5}19)$ …(1)
他方で，自明なこととして
$19x\equiv 0\hspace{5}(\rm{mod}\hspace{5}19)$ …(2)
(2)−(1)
$8x\equiv -13\equiv 6\hspace{5}(\rm{mod}\hspace{5}19)$ …(3)
(1)−(3)
$3x\equiv 7\hspace{5}(\rm{mod}\hspace{5}19)$ …(4)
ところで
$3\times(-4)=-12=-19+ 7$
だから
$3\times(-4)\equiv 7\hspace{5}(\rm{mod}\hspace{5}19)$
1つの解は
$x\equiv -4\equiv 15\hspace{5}(\rm{mod}\hspace{5}19)$
したがって
$x=19s+ 15$ （ $s$ は整数）
これを元の問題に戻すと
$11(19s+ 15)-19y=13$
$19y=11\times 19s+ 152$
$y=11s+ 8$
$\{\begin{matrix}x=19s+ 15\\y=11s+ 8\end{matrix}$ （ $s$ は整数）…（答）

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

　 $m_1,\hspace{2}m_2,\hspace{2}m_3,\hspace{2}\cdots$ が互いに素であるとき，連立１次合同式
$\{\begin{matrix}x\equiv a_1\hspace{5}(\rm{mod}\hspace{5}m_1)\\x\equiv a_2\hspace{5}(\rm{mod}\hspace{5}m_2)\\ \cdots\\ \cdots \end{matrix}$
は $m=m_1\cdot m_2\cdot m_3\cdots$ を法としてただ1つの解を持つ．

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

（解答）
$\{\begin{matrix}x\equiv 1\hspace{5}(\rm{mod}\hspace{5}7)\cdots (1)\\x\equiv 2\hspace{5}(\rm{mod}\hspace{5}5)\cdots (2)\end{matrix}$
(1)より $x=7s+ 1$ （ $s$ は整数）とおける．
これを(2)に代入すると
$7s+ 1\equiv 2\hspace{5}(\rm{mod}\hspace{5}5)$
$7s\equiv 1\hspace{5}(\rm{mod}\hspace{5}5)$
ここで
$5s\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$
だから，差を取ると
$2s\equiv 1\hspace{5}(\rm{mod}\hspace{5}5)$
$2\times 3=6=5+ 1\equiv 1\hspace{5}(\rm{mod}\hspace{5}5)$
だから
$s\equiv 3\hspace{5}(\rm{mod}\hspace{5}5)$
$s=5t+ 3$
結局
$x=7(5t+ 3)+ 1=35t+ 22$ （ $t$ は整数）…（答）

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

（解答）
$\{\begin{matrix}x\equiv 2\hspace{5}(\rm{mod}\hspace{5}5)\cdots (1)\\x\equiv 3\hspace{5}(\rm{mod}\hspace{5}7)\cdots (2)\\x\equiv 4\hspace{5}(\rm{mod}\hspace{5}11)\cdots (3)\end{matrix}$
(1)より $x=5s+ 2$ （ $s$ は整数）とおける．
これを(2)に代入すると
$5s+ 2\equiv 3\hspace{5}(\rm{mod}\hspace{5}7)$
$5s\equiv 1\hspace{5}(\rm{mod}\hspace{5}7)$ …(2’)
ところで
$7s\equiv 0\hspace{5}(\rm{mod}\hspace{5}7)$
だから，(2’)との差を取ると
$2s\equiv -1\equiv 6\hspace{5}(\rm{mod}\hspace{5}7)$
ここで
$2\times 3=6\hspace{5}(\rm{mod}\hspace{5}7)$
だから
$s\equiv 3\hspace{5}(\rm{mod}\hspace{5}7)$
$s=7t+ 3$ （ $t$ は整数）とおける．
$x=5(7t+ 3)+ 2=35t+ 17$ （ $t$ は整数）…(4)
これを(3)に代入
$35t+ 17\equiv 4\hspace{5}(\rm{mod}\hspace{5}11)$
$35t\equiv -13\equiv -2\equiv 9\hspace{5}(\rm{mod}\hspace{5}11)$
ところで
$33t\equiv 0\hspace{5}(\rm{mod}\hspace{5}11)$
だから，差を取ると
$2t\equiv 9\hspace{5}(\rm{mod}\hspace{5}11)$
ここで
$2\times 10=20=11+ 9$
だから
$2\times 10\equiv 9\hspace{5}(\rm{mod}\hspace{5}11)$
$t\equiv 10\hspace{5}(\rm{mod}\hspace{5}11)$
$t=11w+ 10$ （ $w$ は整数）…(5)
(5)を(4)に代入する
$x=35(11w+ 10)+ 17=385w+ 367$ （ $w$ は整数）…（答）

ｎ次合同式（ｎ次合同方程式）
$a_0x^n+ a_1x^{n-1}+\cdots+ a_n\equiv 0\hspace{5}(\rm{mod}\hspace{5}m)$
を解くための解の公式のようなものはないが，次の例のように気長に計算すれば，いずれは解が求まる．

【例題5.1】
$2x^2+ 3\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$ となる整数 $x$ を求めてください．

（解答）
$\rm{mod}\hspace{5}5$ で整数は次のいずれかの形に書ける．
$5t,\hspace{3}5t\pm 1,\hspace{3}5t\pm 2$
各々題意を満たすかどうか調べてみると
$2(5t)^2+ 3\equiv 3\hspace{5}(\rm{mod}\hspace{5}5)$
$2(5t\pm 1)^2+ 3\equiv 5\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$
$2(5t\pm 2)^2+ 3\equiv 11\equiv 1\hspace{5}(\rm{mod}\hspace{5}5)$
したがって， $x=5t\pm 1$
すなわち解は次の２通りある．
$x\equiv 1\hspace{5}(\rm{mod}\hspace{5}5)$
$x\equiv 4\hspace{5}(\rm{mod}\hspace{5}5)$

※この問題が，もし $2x^2\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$ となっていれば解は1通り， $2x^2+ 1\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$ となっていれば解はなし， $2x^2+ 2\equiv 0\hspace{5}(\rm{mod}\hspace{5}5)$ となっていれば解は2通りある．
　一般に， $\rm{mod}\hspace{5}m$ のｎ次合同式の解は $m$ 通り以下であるとは言えるが，具体的に何通りになるのかは問題ごとに異なる．

【例題5.2】
$x^2+ 2\equiv 0\hspace{5}(\rm{mod}\hspace{5}11)$ となる整数 $x$ を求めてください．

（解答）
$x^2\equiv -2\hspace{5}(\rm{mod}\hspace{5}11)$
$x^2\equiv 9\hspace{5}(\rm{mod}\hspace{5}11)$
$x\equiv 3\hspace{5}(\rm{mod}\hspace{5}11)$ は1つの解

$x\equiv a\hspace{5}(\rm{mod}\hspace{5}m)$ が $x^2\equiv b\hspace{5}(\rm{mod}\hspace{5}m)$ の１つの解であるとき， $x\equiv m-a\hspace{5}(\rm{mod}\hspace{5}m)$ も $x^2\equiv b\hspace{5}(\rm{mod}\hspace{5}m)$ の解になる．
（∵） $a^2\equiv b\hspace{5}(\rm{mod}\hspace{5}m)$ ならば $(m-a)^2\equiv m^2-2am+ a^2\hspace{5}(\rm{mod}\hspace{5}m)$
により
$(m-a)^2\equiv b\hspace{5}(\rm{mod}\hspace{5}m)$
となるから

$x\equiv 8\hspace{5}(\rm{mod}\hspace{5}11)$ は解
したがって， $x\equiv 3,\hspace{2}8\hspace{5}(\rm{mod}\hspace{5}11)$ …（答）

　 $\rm{mod}\hspace{5}m$ の合同方程式が与えられたとき，上記の【例題9, 10】のように $m$ の剰余類で分類すれば解けるが， $m$ が大きな値の場合には，分類が煩雑になるため，この方法だけで解くことは容易でない．

●==目次に戻る