大学入試数学 同時余り条件の整合性—共通因子に着目して解の存在を見極める｜武蔵野個別指導塾

互いに素でない2つの法について、余りの差と共通因子から解の有無を調べ、一般解を元の条件へ戻し、見極める同時余り条件の整合性。

よくあるのは、高校生が演習の解き直しで二つの余りを独立に決められると思う場面です。ある数を一方の正整数で割った余りと、もう一方で割った余りは、法に共通する因子があれば連動します。最初の条件に合う数を延々と並べる前に、共通部分で矛盾がないかを見ましょう。矛盾がなければ、今度は実際に数を作り、同じ条件を満たす整数を漏れなく表します。

2つの条件を同時に読むには

整数 x を正整数 m で割った余りが a、正整数 n で割った余りが b であるとします。余りとして与える数はそれぞれ 0 以上、除数未満です。このとき、ある整数 s, t を使って x = a + ms、x = b + nt と書けます。負の x についても商を負に取れるので、この書き方で扱えます。

問われ方には、条件を満たす整数が存在するかの判定、存在するときの一般解、範囲を付けた最小の数や個数の決定があります。最初に見るのは除数の最大公約数と余りの差です。余りがそれぞれ適切な範囲にあるかも、計算に入る前に確かめます。例えば余りが除数以上と指定されていれば、普通の割り算の余りという条件自体が成立しません。

2つの式から x を消すと ms − nt = b − a です。左辺は m と n の共通の約数で割り切れます。したがって右辺も割り切れなければ、整数 s, t は存在しません。この必要条件を先に調べるだけで、探す必要のない場合を排除できます。

共通因子が一致を要求する理由

正整数 d を m と n の最大公約数とします。整数 u と v が法 d について合同であるとは、差 u − v が d の倍数であることです。この関係を u ≡ v（mod d）と書きます。差が倍数という定義から、両辺に同じ整数を加えても差は変わらず、両辺に整数を掛けると差もその整数倍になります。

m と n はともに d の倍数なので、x = a + ms なら x ≡ a（mod d）です。同様に x ≡ b（mod d）です。よって a − b は d の倍数でなければなりません。図1のように、それぞれの条件は共通の法 d で見た余りを指定します。指定が食い違えば、1つの x が両方を満たすことはありません。

逆に、a − b が d の倍数なら、整数の範囲では実際に解が存在します。その理由も一次式で確認できます。m = dM、n = dN とすると M と N は互いに素です。b − a = dc と書けるとき、必要な式は Ms − Nt = c になります。互除法を逆にたどれば、整数 p, q で Mp + Nq = 1 と表せます。両辺を c 倍し、s = pc、t = -qc と取れば式を満たします。したがって x = a + ms が構成でき、もう一方の式にも一致します。

この議論には範囲の確認が必要です。整数解の存在と、正の整数解の存在は同じではないように見えますが、解に m と n の公倍数を繰り返し足せば正にできます。一方、指定された狭い区間内に解があるかどうかは別問題です。整合するだけで区間内に必ず解があるとは言えません。

さらに、1つ解 x₀ が得られた後の全解は、x = x₀ + Lk（k は整数）です。ここで L は m と n の最小公倍数です。実際、別の解との差は m と n の両方の倍数なので L の倍数です。逆に L の倍数を足せば両方の余りは変わりません。これで必要性と十分性がそろいます。互いに素でない法を単純に掛けた mn も公倍数ですが、一般に最小ではなく、周期として使うと解を取りこぼします。

候補を作る順序は入れ替えても構いません。一方の法を使って整数の式に直し、他方に代入すれば、どちらから始めても同じ解の集合に到達します。ただし途中に現れる商の文字は、最初に選んだ割り算によって異なります。文字の値だけを比べず、最後に x の形に戻して比較してください。共通因子での判定は、解を探す前の矛盾検査として、どちらの順序でも利用できます。

基本例題：共通の余りから一歩ずつ進める

【例題1・標準】整数 x を 6 で割ると 1 余り、8 で割ると 5 余ります。このような整数を一般解で表し、正のもののうち最小の値を求めてください。

まず最大公約数は 2、余りの差は 4 です。4 は 2 の倍数なので矛盾はありません。ここから実際の解を作ります。最初の条件を x = 1 + 6s（s は整数）と置き、次の条件へ代入します。

1 + 6s ≡ 5（mod 8）
6s ≡ 4（mod 8）
3s ≡ 2（mod 4）

最後の行では、6s − 4 が 8 の倍数という式を 2 で割っています。法も 8 から 4 に変わります。3s ≡ 2（mod 4）の両辺に 3 を掛け、9 を 4 で割ると 1 余ることを使えば s ≡ 2（mod 4）です。逆向きにも各変形が成立するので、s = 2 + 4k（k は整数）と表せます。

x = 1 + 6(2 + 4k)
  = 13 + 24k

図2のように 13 は両方の条件に入り、次の解までの間隔は 6 と 8 の最小公倍数 24 です。実際に 13 = 6・2 + 1、13 = 8・1 + 5 です。24 を足し引きしても余りは同じです。k = 0 で 13、k が負なら 13 + 24k は正でないので、最小の正の解は 13 です。

別の見方として、6 で割ると 1 余る数を 1, 7, 13, 19 と並べ、8 での余りを順に確認しても 13 を発見できます。ただし並べるだけでは負の解を含む一般解の証明になりません。発見した値との差が 6 と 8 の両方の倍数であることを示せば、一覧を一般解につなげられます。

矛盾と追加条件をどう処理するか

【例題2・やや難】整数 x が 12 で割ると 3 余り、18 で割ると 8 余ることはあるか、理由を付けて答えてください。

12 と 18 の最大公約数は 6 です。条件を満たすと仮定すると、整数 s, t を用いて次のようになります。

x = 3 + 12s
x = 8 + 18t
12s - 18t = 5
6(2s - 3t) = 5

左辺は 6 の倍数ですが、右辺 5 は 6 の倍数ではありません。したがって、そのような整数 x は存在しません。片方の条件を満たす数をどれほど遠くまで探しても、もう片方とは出会いません。有限個を試して見つからなかったことではなく、共通因子による矛盾が不可能性の根拠です。

余りを直接 6 で割っても、3 は 3 余り、8 は 2 余ります。同じ x が 6 で割って 3 と 2 の両方を余りに持つことはできません。こちらも同じ矛盾を別の形で述べています。なお余りの数が違うこと自体は矛盾ではありません。共通因子で見た余りが違うことが矛盾の理由です。

【例題3・難】整数 x を 8 で割ると 3 余り、14 で割ると 9 余ります。さらに 0 以上 150 以下という条件を満たす整数をすべて求めてください。

最大公約数は 2、余りの差 6 は 2 の倍数です。まず x = 3 + 8s として、もう一方へ代入します。

3 + 8s ≡ 9（mod 14）
8s ≡ 6（mod 14）
4s ≡ 3（mod 7）

4・2 = 8 ≡ 1（mod 7）なので、両辺を 2 倍すると s ≡ 6（mod 7）です。逆に s ≡ 6 なら 4s ≡ 24 ≡ 3（mod 7）ですから、同値に戻せます。よって s = 6 + 7k と置けます。

x = 3 + 8(6 + 7k)
  = 51 + 56k

区間へ戻すと、0 ≦ 51 + 56k ≦ 150 です。k = -1 では x = -5、k = 2 では x = 163 ですから、整数 k は 0, 1 に限られます。求める値は 51, 107 です。51 = 8・6 + 3 = 14・3 + 9、107 = 8・13 + 3 = 14・7 + 9 なので、両方とも元の余りを満たします。56 が両方の法の最小公倍数であることも、一般解の間隔と一致します。

範囲を最後に使うと、整数全体での整合性と区間に入るかを混同しません。例えば範囲が 0 以上 50 以下なら、一般解は存在しても範囲内の答えはありません。逆に範囲の端が解そのものであれば、その端を含む不等号かどうかを確認します。

誤答はどこで枝を失うか

例題1で 6s ≡ 4（mod 8）から 3s ≡ 2（mod 8）とする誤りを考えます。図3のように、共通因子 2 で割るときは差が何の倍数かを表す法も 2 で割ります。誤った式は s ≡ 6（mod 8）となり、s = 2 を除いてしまいます。すると正しい解 x = 13 が消えます。

修正の根拠は、6s − 4 = 8h（h は整数）と書くことです。両辺を 2 で割れば 3s − 2 = 4h なので、法は 4 です。逆に後者から前者へ 2 倍で戻れるため、解の集合は変わりません。法を変えずに割れる場合もありますが、それには割る数と法が互いに素であるなどの根拠が必要です。無条件の約分はできません。

もう1つの誤りは、最大公約数が余りの差を割ることだけを書いて、具体的な解を求めずに終えることです。存在判定だけなら十分性を示すことで完成しますが、一般解を問う問題では候補の構成と周期まで必要です。また、最小公倍数を差の周期として使う説明がなければ、見つけた1つ以外を尽くしたことにはなりません。

手を動かす5問

次の各問で、余りは正の除数による 0 以上、除数未満の余りとします。一般解の文字は整数を動くものとします。

1. 【標準】整数 x を 4 で割ると 2 余り、10 で割ると 6 余るとき、一般解と最小の正の解を求めてください。
2. 【標準】整数 x を 9 で割ると 2 余り、15 で割ると 4 余ることはあるか、理由を付けて答えてください。
3. 【やや難】整数 x を 10 で割ると 7 余り、16 で割ると 13 余るとき、0 以上 100 以下の解をすべて求めてください。
4. 【やや難】整数 x を 6 で割ると 5 余り、15 で割ると r 余るとします。0 ≦ r < 15 の整数 r のうち、条件を満たす x が存在するものをすべて求めてください。
5. 【難】整数 x を 12 で割ると 5 余り、20 で割ると 13 余るとします。-100 以上 100 以下の解をすべて求めてください。

5問の答えと確認

1. 最大公約数は 2 で、余りの差 4 はその倍数です。x = 2 + 4s を代入すると 4s ≡ 4（mod 10）、つまり 2s ≡ 2（mod 5）です。よって s ≡ 1（mod 5）となり、x = 6 + 20k です。6 = 4・1 + 2 = 10・0 + 6 であり、20 は両方の倍数です。差の議論から他の解もこの形に限られ、最小の正の解は 6 です。

2. 存在しません。共通因子 3 で見ると、9 での余り 2 は 3 での余り 2 を要求し、15 での余り 4 は 3 での余り 1 を要求します。同じ整数には両立しません。式では 9s − 15t = 2 となり、左辺が 3 の倍数であることに矛盾します。

3. x = 7 + 10s を代入すると 10s ≡ 6（mod 16）、5s ≡ 3（mod 8）です。5・5 ≡ 1（mod 8）より s ≡ 7（mod 8）、したがって x = 77 + 80k です。範囲内では k = 0 のみなので 77 です。77 = 10・7 + 7 = 16・4 + 13 と元の条件へ戻せます。隣の解は -3 と 157 で、ともに範囲外です。

4. 最大公約数は 3 ですから、r − 5 が 3 の倍数であることが必要です。範囲内の候補は 2, 5, 8, 11, 14 です。逆にそれぞれ x = 17, 5, 23, 11, 29 を取れば、いずれも 6 で割ると 5 余り、15 での余りも順に指定値になります。したがってこの5個がすべてです。候補を並べるだけでなく、各候補に対する存在も確認しています。

5. x = 5 + 12s と置くと 12s ≡ 8（mod 20）、3s ≡ 2（mod 5）です。3・2 ≡ 1（mod 5）より s ≡ 4（mod 5）で、x = 53 + 60k です。範囲に入る k は -2, -1, 0 なので、答えは -67, -7, 53 です。例えば -67 = 12・(-6) + 5 = 20・(-4) + 13 です。他の2つも 60 の倍数だけ離れており、両方の余りが変わりません。隣の -127 と 113 は範囲外です。

答案に残す要点

• 除数が正で、指定された余りがその除数未満か確かめます。
• 最大公約数が余りの差を割らなければ、整数解はありません。
• 割る場合は一次式から1つの解を作り、元の両条件に戻します。
• 全解の差は最小公倍数の倍数であり、その倍数を足しても条件を保ちます。
• 区間の有無や端の等号は一般解を得た後に調べます。

立ち止まる箇所を見つける

手が止まったら、2つの余りを同じ法で比較できる形に直せるかを確かめます。個別指導で答案を見るなら、まず「x = a + ms と x = b + nt から何が言えるか」を尋ね、差の式に整数の商が残っているかを見ます。次に、得た候補を両方の割り算に戻し、解がない場合は共通因子による矛盾を言葉にできるかを確認します。存在する場合と存在しない場合を同じ式から判定できれば、余りの整合性は答案の根拠になります。