合同方程式の解き方 | わかりやすい解法と注意点
" 合同方程式の解き方 “を、わかりやすい具体例で知ったときに、使い方の注意点も押さえておくことが大切になります。
いつでも通常の方程式と同じように使えるというわけではないので、割り算をするときには注意です。
そのため、割り算ができないときや二乗があるときについても解説をしています。
では、具体例を使って、合同方程式を解いてみます。
合同方程式の解き方 :わかりやすい例
まずは、シンプルな例を用いて、合同方程式を解いてみます。この例は、割り算ができるタイプのものです。
この解き方を知っていると、整数分野での解くスピードも上がり、役に立つことが多いです。
【具体例】
5a ≡ 10 (mod 12)
a に当てはまる数は整数という設定です。この a に当てはまる整数は、どういった整数になるのかという問題です。
合同方程式の意味は、「5a を 12 で割ったときの余りが 10 となるとき、a としてどのような整数が考えられるか」ということになります。
ここで、a の係数の 5 と、割る数 12（法が 12）ということに注目します。
5 と 12 の最大公約数が 1 となっています。
このときは、係数の 5 で割り算ができます。
普通の方程式を解くときに両辺を 5 で割る感覚で計算をすることができます。
5a ≡ 10 (mod 12) より、
a ≡ 10 ÷ 5 (mod 12)
つまり、a ≡ 2 (mod 12)
これは、整数 a を 12 で割ったときの余りが 2 ということなので、除法の原理（検算）より、小学校の算数で学習したように、
a = 12 × 整数 + 2 という割ら割る数と割る数と余りについての等式が得られます。
※ ユークリッド整域というブログ記事で、大学数学として除法の定理を証明しています。
高校の数学では、12 に掛ける整数部分を文字で表示し、a = 12k + 2 (k は整数) と一般的な形で表します。
これで、はじめに与えられた合同方程式が解けました。
a は 12 で割ると余りが 2 となる整数ということです。
この割り算ができるタイプについて、もう少し応用的な練習問題を扱ってみます。
練習問題
12x – 17y = 2 を満たす整数の組 (x, y) を求めてください。
一次不定方程式の内容は、大学で学習する環論の良い具体例になってくれます。
※ リンク先では、環論についての内容へ踏み込んでいます。
12 と 17 という二つの係数に注目して、小さい方の 12 を法として合同関係を考えます。
-17 を 12 で割ったときの余りを先に求めておいてから、合同式で表すことにします。
-17 = 12 × (-2) + 7 より、
-17 ≡ 7 (mod 12)
12 ≡ 0 (mod 12) と合わせて考えると、
12x – 17y = 2 から、
7y ≡ 2 (mod 12) … ★
ここで、
14 を 12 で割った余りが 2 なので、
2 ≡ 14 (mod 12) … ■
★と■に推移律を適用して、
7y ≡ 14 (mod 12)
ここで、7 と 12 の最大公約数が 1 なので、
y ≡ 2 (mod 12) です。
これで、
x = 17k + 3, y = 12k + 2 （ただし k は整数）とパラメータ k を用いて表すことができました。
この解法は、7 と 12 の最大公約数が 1 なので、途中で割り算ができたことが効いています。
しかし、合同方程式を解くときに、いつでも割り算ができるとは限りません。
大学受験の問題などでも、割り算ができないところを突いて出題されたことが、今までにありました。
そこで、割り算ができないタイプの合同方程式も合わせて理解しておくことが必要になります。
合同方程式の解き方 :割り算ができないタイプ
今度は、割り算ができないタイプについての合同方程式について解説します。
2a ≡ 4 (mod 6) を満たす整数 a はどんな整数ですか。
a の係数 2 と、割る数である法 6 の最大公約数が 1 ではありません。
このときには、割り算ができないのが合同方程式の難しいところです。
このときには、起こり得る余りについて、場合分けをして考えるのが一般的です。
場合分け発生
2a ≡ 4 (mod 6) について、整数 a を 6 で割ったときの余りは、0, 1, 2, 3, 4, 5 の 6 通りあります。
これらの全可能性について、議論をします。
【a ≡ 0 (mod 6) のとき】
このときは、合同式の性質から、
2a ≡ 0 (mod 6) となり、2a を 6 で割った余りが 4 であるということに矛盾します。
※ 2a ≡ 4 (mod 6) という設定でした。
まず、矛盾が生じる場合を除きます。
【a ≡ 1 (mod 6) のとき】
2a ≡ 2 (mod 6) となり、矛盾です。
【a ≡ 2 (mod 6) のとき】
2a ≡ 4となって、確かに余りが 4 です。
【a ≡ 3 (mod 6) のとき】
2a ≡ 6 ≡ 0 (mod 6) となり、矛盾です。
【a ≡ 4 (mod 6) のとき】
2a ≡ 8 ≡ 2 (mod 6) となり、矛盾です。
【a ≡ 5 (mod 6) のとき】
2a ≡ 10 ≡ 4 (mod 6) なので、余りが 4 となっています。
では、これらの考察を最後にまとめます。
これが答え
a ≡ 2 (mod 6) と a ≡ 5 (mod 6) の場合が、答えです。与えられた合同式を満たしています。
場合分けした合同式を、パラメータを用いて表すと次のようになります。
a は、a = 6k + 2 （k は整数）もしくは a = 6t + 5 （t は整数）という形です。
割り算できないときは、数学の論理を使って、起こり得るすべての場合について考察することになります。
ちなみに、逆は明らかです。
a = 6k + 2 （k は整数）であるとき、
2a = 12k + 4 ≡ 4 (mod 6) で、確かに 6 で 2a を割ったときの余りが 4 となっています。
※ a = 6t + 5 （t は整数）の場合についても同様です。
2a = 12t + 10 ≡ 4 (mod 6) です。
※ フェルマーの小定理の証明を理解するのにも、今回のブログで述べている余りについての内容は、大切になります。
ここからは、合同方程式に二乗が使われているものについて考察をしてみます。
合同方程式の解き方 :二乗を解消する
二乗が絡んでくると、因数分解をして一次の合同式に帰着できないかと考えます。
もちろん、起こり得る場合について、場合分けをするという意識は常に必要です。
しかし、場合分けも考えると大変なので、シンプルな例のものを扱うことにします。
a2 – a – 2 ≡ 0 (mod 5) を満たす整数 a はどんな整数ですか。
問題によっては、難しい因数分解が決め手になるものもあります。
しかし、学習し始めのときは、公式を使って、すぐに因数分解できるレベルのもので親しむと良いかと思います。
a2 – a – 2 = (a + 1)(a – 2) と因数分解できるので、(a + 1)(a – 2) ≡ 0 (mod 5) です。
素因数分解の考え方より、
a + 1 が 5 の倍数か、または、a – 2 が 5 の倍数となっています。
よって、
a + 1 ≡ 0 (mod 5) または
a – 2 ≡ 0 (mod 5) となっています。
この「または」という論理の発想が大切になります。
a = 5k – 1 （k は整数) または a = 5t + 2 （t は整数）ということになります。
ちなみに、パラメータを使って表すときに、
a = 5k – 1 （k は整数）ということと、
a = 5h + 4 （h は整数）ということは同じ内容になっています。
{5k – 1 | k は整数}
= {5h + 4 | h は整数} となっています。
k が整数全体を動くので、
(k + 1) も整数全体を動き、
{5k – 1 | k は整数}
= {5(k + 1) -1 | k は整数}
= |5k + 4 | k は整数}
最後の集合の k を h と他の文字にしても、表している集合は同じものです。
{5k + 4 | k は整数} の k を h にしたものが、
{5h + 4 | h は整数} です。
現れる整数たちが、同じということを集合の発想で考えて等しいということを見抜くのも大切になります。
合同式の考え方で整数の証明問題を考えることは、良いトレーニングになるので、
7の倍数判定法という記事で、3 や 11 の倍数判定法の証明を解説しています。
また、合同式の内容には、場合分けの発想が大切になります。二乗はありませんが、場合分けに焦点を当てて、素数問題について考察をしてみます。
同じ観点の発想
p, 2p + 1, 4p + 1 がすべて素数となるような素数 p をすべて求めてください。
起こり得る場合をすべて場合分ける発想が大切になります。
また、はじめに小さい整数の例で様子を観察するという姿勢も良いかと思います。
p = 2 のとき、
4p + 1 = 8 + 1 = 9 となり、素数でないので矛盾です。
p = 3 のとき、
2p + 1 = 6 + 1 = 7 で素数です。
4p + 1 = 12 + 1 = 13 で素数です。
したがって、p = 3 は求める素数のうちの一つであることが分かりました。
ここで、p ≧ 4 というときを考えます。
この 4 以上の素数 p は、3 で割ったときの余りは 1 か 2 ということになります。
※ 4 以上の整数で 3 で割り切れる整数は素数ではありません。
p ≡ 1 (mod 3) のとき、
2p + 1 ≡ 2 + 1 ≡ 0 (mod 3)
よって、p ≧ 4 のとき、
2p + 1 は 3 で割り切れるので、素数ではありません。
p ≡ 2 (mod 3) のとき、
4p + 1 ≡ 1×2 + 1 ≡ 0 (mod 3)
よって、p ≧ 4 のとき、
4p + 1 は 3 で割り切れるので、素数ではありません。
以上より、
p, 2p + 1, 4p + 1 がすべて素数となるのは、
p = 3 のときのみということが分かりました。
「p = 3 のみ」というのが答えです。
素数について、扱いましたが、
素数判定法（エラトステネスのふるい）というブログ記事で、素数かどうかについての簡単な判定法を解説しています。
ガウス記号を使った判定法を改造して、中学一年のレベルの計算で三桁くらいの整数について素数かどうかを判定するという内容のブログ記事です。
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。