■簡単な合同方程式の解き方■
高校の数学Aの教科書では,通常,整式の合同や合同式には触れない.発展学習として,軽く触れている教科書,参考書はある.
【合同の定義】
は整数,は正の整数とする. がで割り切れるとき,「とはを法(modulus)として合同である」といい と書く. |
「とはを法として合同である」とは「とをで割った余りが等しい」と言うこともできる.
(証明)
とおくと だから がで割り切れる |
【合同式の基本的性質】
(1.1) 反射律
(証明)だから,とはを法として合同であると言える.
(1.2) 対称律
(証明)ならば ならばだから成り立つ.
(1.3) 推移律
(証明)かつ ならば ならば だから成り立つ |
【合同式の四則計算(1)】
かつならば
(証明)(2.1) (2.2) (2.3) かつならば (2.1) だから,が成り立つ. (2.2) だから,が成り立つ. (2.3) だから,が成り立つ. ※初歩的な注意であるが,商については,成り立たない. |
【合同式の四則計算(2)】
のとき,を整数,を正の整数とすると
(証明)(3.1) 両辺に同じ数を足してもよい (3.2) 両辺から同じ数を引いてもよい (3.3) 両辺に同じ数を掛けてもよい (3.4) 両辺を何乗かしてもよい のとき (3.1) だから が成り立つ (3.2) だから が成り立つ (3.3) だから が成り立つ (3.4) だから が成り立つ |
のとき,を整数,との最大公約数をとすると
(3.5) ならば (3.6) 特に,とが互いに素であるとき ならば
(3.6)は,合同式の両辺をmと互いに素な数で割ってもよいことを示している.
(証明)ならばとなる整数が存在する. との最大公約数をとすると (は互いに素) とおける.このとき より は互いに素だから,はで割り切れる. よって ならば 特に,とが互いに素ならばだから
(4.1) [バシェの定理]
は整数,は正の整数とする. 合同方程式
の解について1) とが互いに素のとき,解はただ1つ存在する. 2) の最大公約数がで,がで割り切れるとき,個の非合同解が存在する. 3) の最大公約数がで,がで割り切れないとき,解は存在しない. |
【例題1.1】
(解答)を解いてください. だから 両辺に3を掛けると したがって,は1つの解になる. (4.1)により,解はただ1つであるから, …(答)
単純計算で検算してみる
で分類すると,整数は次の7種類に分かれる. 各々を求めると 以上のように,の場合だけ,合同式を満たす. |
【例題1.2】
(解答)を解いてください. …(答)
検算
ならば |
【例題2.1】
(解答)を解いてください. 15と21の最大公約数は 6はの倍数になっているから解は存在する(3個ある) の各数を3で割ると だから 1つの解は 元の問題の解は
検算
|
【例題2.2】
(解答)を解いてください. 35と20の最大公約数は 15はの倍数になっているから解は存在する(5個ある) の各数を5で割ると だから 1つの解は 元の問題の解は
検算
|
【例題3.1】
(解答)となる整数を求めてください. で (は整数) これを元の問題に戻すと (は整数) (別解) で (は整数) これを元の問題に戻すと (は整数) |
【例題3.2】
(解答)となる整数を求めてください. で 問題から …(1) 他方で,自明なこととして …(2) (1)+(2) …(3) ところで だから 1つの解は したがって (は整数) これを元の問題に戻すと (は整数)…(答) (別解) で 問題から …(1) 他方で,自明なこととして …(2) (2)−(1) …(3) (1)−(3) …(4) ところで だから 1つの解は したがって (は整数) これを元の問題に戻すと (は整数)…(答) |
次の定理は「中国剰余定理」と呼ばれる.このページでは,定理の証明は省略するが,この定理によって存在と一意性が示される連立1次合同式の解き方を考えてみる.
が互いに素であるとき,連立1次合同式
はを法としてただ1つの解を持つ.
【例題4.1】
(解答)7で割ると1余り,5で割ると2余る整数をすべて求めてください. (1)より(は整数)とおける. これを(2)に代入すると ここで だから,差を取ると だから 結局 (は整数)…(答) (算数で攻める・・・) (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)より(は整数)とおける. これを(2)に代入すると …(2’) ところで だから,(2’)との差を取ると ここで だから (は整数)とおける. (は整数)…(4) これを(3)に代入 ところで だから,差を取ると ここで だから (は整数)…(5) (5)を(4)に代入する (は整数)…(答) (算数で攻める・・・) (1)(2)から,35で割ったときの余りは17 つまり,385で割ったときの余りは, 17,52,8/7,122,157,192,227,262,297,332,367 このうちで,11で割ると4余るのは367 x=385t+367(tは整数)・・・(答) |
n次合同式(n次合同方程式) を解くための解の公式のようなものはないが,次の例のように気長に計算すれば,いずれは解が求まる.
【例題5.1】
(解答)となる整数を求めてください. で整数は次のいずれかの形に書ける. 各々題意を満たすかどうか調べてみると したがって, すなわち解は次の2通りある. ※この問題が,もしとなっていれば解は1通り,となっていれば解はなし,となっていれば解は2通りある. 一般に,のn次合同式の解は通り以下であるとは言えるが,具体的に何通りになるのかは問題ごとに異なる. |
【例題5.2】
(解答)となる整数を求めてください. は1つの解
がの1つの解であるとき,もの解になる.
は解(∵)ならば により となるから したがって,…(答) の合同方程式が与えられたとき,上記の【例題9, 10】のようにの剰余類で分類すれば解けるが,が大きな値の場合には,分類が煩雑になるため,この方法だけで解くことは容易でない. |