大学入試数学 合同式の約分条件—共通因子がある場合の解の取りこぼしを直す｜武蔵野個別指導塾

係数と法の最大公約数を使い、解なしの判定から元の法での候補の復元までたどる合同式の約分条件。

よくあるのは、高校生が演習の解き直しで合同式を等式のように割る場面です。両辺を同じ数で割れたように見えても、法をそのままにすると、元の条件を満たす整数が消えることがあります。余りの条件は、差が法の倍数であるという条件です。差だけでなく、その倍数の基準も一緒に見直すと、どの候補を戻すべきかが見えてきます。

何を求める問題か

一次合同式では、整数 x について ax ≡ b （mod m）を満たすものを調べます。ここで a、b は整数、法 m は正整数です。答え方には、元の法 m における余りをすべて列挙する形と、整数全体の一般形を書く形があります。問題が余りを尋ねるなら、約分後の小さい法での余りだけを答えて終わりにはできません。

まず見るのは、係数 a と法 m の最大公約数です。これを d とすると、b が d の倍数でない場合は解がありません。b が d の倍数なら、係数、右辺、法をそれぞれ d で割った条件に移れます。縮んだ法で解いてから、元の法に戻すことが次の仕事です。

別の型として、誤った約分の一行を示され、その理由と正しい解を問われることもあります。その場合は「割ってはいけない」とだけ書かず、元の式を満たす具体的な整数が誤った式で失われることを示すと、誤りの内容が明確になります。解が存在しない場合も、候補を探し続ける前に整除の矛盾で止められます。

差の倍数から法を縮める

整数 u、v と正整数 m について、u ≡ v （mod m）とは、u − v が m の倍数であるという意味です。したがって ax ≡ b （mod m）は、ある整数 k を用いて次のように書けます。

ax - b = mk

この等式が、約分の根拠です。a と m の最大公約数を d とすると、ax と mk はともに d の倍数です。よって b も d の倍数でなければなりません。これは解があるための必要条件です。例えば右辺が d の倍数でなければ、どの整数 x を代入しても差が m の倍数になることはありません。

b も d の倍数であるとき、a = da₁、b = db₁、m = dm₁ と書きます。d は正なので 0 ではありません。元の等式を d で割ると、次の同値な条件になります。

da₁x - db₁ = dm₁k
a₁x - b₁ = m₁k
a₁x ≡ b₁ （mod m₁）

逆向きも確認できます。最後の合同式から整数 k が取れ、その等式の両辺を d 倍すれば元の式に戻ります。したがって、法も割った変形は必要条件にとどまらず、元の式と同値です。a₁ と m₁ の最大公約数は 1 です。共通の正の約数がさらにあれば、a と m に d より大きな公約数が生じるからです。

図1のように、最初の判定で進む道を分けます。右辺が割れない場合は解なしです。割れる場合は小さい法で解いた後、元の法の範囲へ候補を戻します。

図1の分岐は計算手順だけでなく、候補を失わないための論理です。法を割った後の条件で x ≡ r （mod m₁）なら、整数全体の解は x = r + m₁t、t は整数です。元の法 m = dm₁ で見れば、t の余り 0、1、…、d − 1 に対応する d 個の余りがあります。

r, r + m₁, …, r + (d - 1)m₁

ただし r は 0 以上 m₁ 未満に選びます。このとき上の数はすべて 0 以上 m 未満で、互いに異なります。t を d で割った余りに分ければ、それ以外の整数もこのどれかと m を法として合同です。これで復元に漏れがない理由と、重複しない理由の両方が示せます。m₁ = 1 の場合も同じで、縮んだ条件はすべての整数が満たし、元の法では d 個の余りが残ります。

基本例題：縮めた法から戻す

【例題1・標準】整数 x が 6x ≡ 8 （mod 14）を満たすとき、x を 14 で割った余りをすべて求めてください。

6 と 14 の最大公約数は 2 で、8 は 2 の倍数です。差の等式を使い、法も含めて 2 で割ります。

6x - 8 = 14k　（k は整数）
3x - 4 = 7k
3x ≡ 4 （mod 7）

3 と 7 は互いに素です。ここでは両辺を 5 倍すると係数が 15 となり、15 ≡ 1 （mod 7）です。合同式を同じ整数倍できることは、差が 7 の倍数ならその 5 倍も 7 の倍数であることから従います。

15x ≡ 20 （mod 7）
x ≡ 6 （mod 7）

逆向きも、x − 6 が 7 の倍数なら 3x − 4 = 3(x − 6) + 14 が 7 の倍数と見れば確かめられます。したがって x = 6 + 7t、t は整数です。14 で割った余りは 6、13 です。

図2のように、7 を法とする同じ余りが、14 未満では 2 か所に現れます。図の 6 と 13 を元の条件に戻すと、6・6 − 8 = 28、6・13 − 8 = 70 で、ともに 14 の倍数です。これらに 14 の倍数を加えても差には 14 の倍数が加わるので、各余りに属する整数はすべて元の式を満たします。

図2の 2 個は偶然ではありません。元の法を縮めた比が 14/7 = 2 だからです。小さい法での代表を 1 個見つけることと、元の法での余りを 1 個しか持たないことは別の主張です。問題文が一般形を求めるなら x = 6 + 7t と書くことで両方の余りを含められますが、余りを列挙する問いには 6 と 13 を明記します。

右辺が割れないときと条件付きの復元

【例題2・やや難】整数 x が 15x ≡ 7 （mod 21）を満たすことがあるか、理由を付けて答えてください。

15 と 21 の最大公約数は 3 です。解があると仮定すると、ある整数 k について次が成り立ちます。

15x - 7 = 21k
7 = 15x - 21k
7 = 3(5x - 7k)

右辺は 3 の倍数ですが、7 は 3 の倍数ではありません。矛盾するので解はありません。ここで 15 と 21 だけを 3 で割って右辺をそのまま置くことには、差の等式からの根拠がありません。また、右辺を分数にする計算は整数の倍数という元の条件をそのまま表しません。存在しない候補を無理に作る前に、右辺の整除性を確かめます。

【例題3・難】整数 x について 12x ≡ 18 （mod 30）を満たし、さらに 0 ≦ x < 50 であるものをすべて求めてください。

12 と 30 の最大公約数は 6 であり、18 は 6 の倍数です。法を含む 3 つの数を 6 で割ります。

12x - 18 = 30k　（k は整数）
2x - 3 = 5k
2x ≡ 3 （mod 5）

両辺を 3 倍すると、6 ≡ 1 （mod 5）より次を得ます。

6x ≡ 9 （mod 5）
x ≡ 4 （mod 5）
x = 4 + 5t　（t は整数）

逆に x = 4 + 5t なら、2x − 3 = 5 + 10t は 5 の倍数なので、この一般形は縮んだ条件と同値です。範囲を代入して t を絞ります。

0 ≦ 4 + 5t < 50
-4 ≦ 5t < 46
-4/5 ≦ t < 46/5
0 ≦ t ≦ 9　（t は整数）

よって答えは 4、9、14、19、24、29、34、39、44、49 です。最小の t と最大の t を含め、その外の整数は範囲を外れるので漏れはありません。元の式に戻すと、x = 4 + 5t に対し 12x − 18 = 30 + 60t となり、どの候補も 30 の倍数を与えます。

別の見方では、まず元の法 30 での余りを 4、9、14、19、24、29 と復元し、次に範囲内の数を拾います。ただし 30 で割った余りだけを挙げて 34 以降を忘れると、区間内の整数を求める問いには答え切れません。逆に、最初から x = 4 + 5t を範囲に代入すれば、負の t も含めて境界を判断できます。元の法の余りを問うのか、指定区間の整数を問うのかで最後の整理を選びます。

法を残した約分はどこで破綻するか

次の誤答を考えます。

6x ≡ 8 （mod 14）
3x ≡ 4 （mod 14）

両辺だけを 2 で割り、法を 14 のままにしています。しかし元の式は 6x − 8 = 14k という意味なので、2 で割った差は 7k です。7 の倍数であることは、14 の倍数であることを意味しません。図3のように、元の式に戻る道を差の等式で確かめると、法を 7 に変える必要が見えます。

図3の正しい条件は 3x ≡ 4 （mod 7）です。例えば x = 13 は元の条件を満たしますが、3・13 − 4 = 35 は 14 の倍数ではないため、誤った条件から落ちます。一方、誤った条件を満たす整数は元の条件も満たします。つまりこの誤りは余計な解を加えるのではなく、元の解を一部失う形で現れます。

共通因子 c が係数、右辺、法を割るなら、c が正であるとして ca ≡ cb （mod cm）と a ≡ b （mod m）は同値です。法を cm のまま a ≡ b と書くのとは異なります。係数と法が互いに素の場合は、係数を消しても法を保てますが、その根拠も必要です。係数と法が互いに素なら、係数の倍数が法で割り切れるとき、残りの因子が法で割り切れるためです。共通因子がある場面に、この性質を条件を外して使わないようにします。

練習：判定から答えの形まで

各問の x は整数です。余りは 0 以上、指定された法未満の整数で答えてください。

1. 【標準】4x ≡ 10 （mod 18）を満たす x の 18 での余りをすべて求めてください。
2. 【標準】8x ≡ 6 （mod 20）を満たす整数が存在するか、理由を付けて答えてください。
3. 【やや難】9x ≡ 12 （mod 15）を満たす整数 x の一般形を、整数 t を用いて表してください。
4. 【やや難】14x ≡ 21 （mod 35）を満たし、-10 ≦ x < 20 である整数をすべて求めてください。
5. 【難】整数 b に対し、10x ≡ b （mod 25）が整数解を持つための b の条件を求め、その条件の下で 25 を法とする相異なる解の個数を答えてください。

解答と考え方

1. 最大公約数は 2 で、10 はその倍数です。法も 2 で割ります。

4x ≡ 10 （mod 18）
2x ≡ 5 （mod 9）
10x ≡ 25 （mod 9）
x ≡ 7 （mod 9）

逆に x = 7 + 9t なら 2x − 5 = 9 + 18t です。したがって元の法での余りは 7、16 です。元の差はそれぞれ 18、54 となり、どちらも 18 の倍数です。2 個以外の余りは、小さい法での条件を満たしません。

2. 8 と 20 の最大公約数は 4 ですが、6 は 4 の倍数ではありません。もし 8x − 6 = 20k なら 6 = 8x − 20k = 4(2x − 5k) となり矛盾します。したがって解はありません。右辺が最大公約数で割れない場合は、候補を復元する段階には進みません。

3. 9、12、15 を 3 で割ると、3x ≡ 4 （mod 5）です。両辺を 2 倍して 6x ≡ 8 （mod 5）、すなわち x ≡ 3 （mod 5）を得ます。逆に x = 3 + 5t なら 9x − 12 = 15 + 45t です。よって一般形は x = 3 + 5t、t は整数です。この形は元の差が 15 の倍数となる整数を漏れなく表します。

4. 最大公約数 7 で割ると 2x ≡ 3 （mod 5）です。3 倍して x ≡ 4 （mod 5）、すなわち x = 4 + 5t です。元の差は 14(4 + 5t) − 21 = 35 + 70t なので、この形は十分でもあります。

-10 ≦ 4 + 5t < 20
-14 ≦ 5t < 16
-14/5 ≦ t < 16/5
-2 ≦ t ≦ 3　（t は整数）

したがって答えは -6、-1、4、9、14、19 です。負の端では t = -3 が範囲外であることにも注意します。

5. 最大公約数は 5 なので、解があるなら b は 5 の倍数です。逆に b = 5c、c は整数とすると、元の条件は 2x ≡ c （mod 5）と同値です。2・3 = 6 ≡ 1 （mod 5）より x ≡ 3c （mod 5）を得ます。逆にこの条件なら 2x − c は 5 の倍数なので、元の合同式を満たします。よって条件は b が 5 の倍数であることです。法 5 で 1 種類の余りが、法 25 では 5 種類に分かれるため、相異なる解は 5 個です。b が 5 の倍数でなければ解は 0 個です。

手元に残す判断

• 差が法の倍数という定義へ戻ります。
• 係数と法の最大公約数が右辺を割らなければ解はありません。
• 割れるときは右辺と係数だけでなく法も割ります。
• 小さい法の解を、問いに応じて元の法または区間へ戻します。
• 最後に元の差が元の法の倍数となることを確かめます。

答案のどこで止まったかを見分ける

候補が足りないときは、約分後に書いた法と、問題が求める法を並べてみます。両者が違えば、小さい法の 1 つの余りに元の法の何個の余りが対応するかを整数の範囲で数えます。解なしの判断に迷うときは、差の等式から右辺が共通因子の倍数になる行を書き出します。

個別指導で答案を見直す場合も、正答の数字だけでなく、法を縮める前後の同値性と、復元した候補が元の条件に戻る行を確認します。約分の一行に法の変化を添えれば、失われた候補まで追跡できます。