武蔵野個別指導塾の特徴

高校数学A 互除法で最大公約数が変わらない理由—共通約数の集合を除法の式で比べる｜武蔵野個別指導塾

公開 2026.11.12更新 2026.11.12武蔵野個別指導塾の特徴高校数学A 整数の性質を掘り下げる

除法の前後で共通約数が一致することを双方向に証明し、余りが0になるまでに計算が終わる理由を確かめます。

よくあるのは、余りを順に出す手順を覚えた高校生が、なぜ途中で数を取り替えても最大公約数が変わらないのか説明できずに止まる場面です。計算が合っていても、最後の数を答えにする理由が見えなければ、途中の式が正しいか自分で判断しにくくなります。除法の式を差と和の両側から読み、共通約数そのものを比べてみましょう。

要点（結論から）

除法の式を差と和に読み替え、共通約数の包含を両方向に示します。
余りが正なら前の除数より小さく、有限回で0になります。
最後の非零の余りと0の最大公約数は、その非零の数です。

何を比べれば理由になるか

出方の1つは、正整数2個と除法の式が与えられ、取り替える前後の最大公約数が等しい理由を述べる問題です。答えの数値を出すだけでなく、共通約数が残り、しかも新しい共通約数が増えないことを示します。もう1つは、余りを繰り返して最後の非零の余りが答えになる理由を問う問題です。こちらは各段階の等しさに加えて、操作が止まる理由と、最後の0の扱いが必要です。

どちらも、まず入力が正整数であることを確かめます。大きい方を a、小さい方を b とすれば a ≥ b > 0 で、商 q と余り r を用いて a = bq + r、0 ≤ r < b と書けます。a と b が等しい場合も余りは0です。最初から小さい方が左にあれば、順番を入れ替えても共通約数の条件は変わりません。

数学Aの「数学と人間の活動」では、整数の約数や倍数とともにユークリッドの互除法を扱います。ここではその中でも、除法によって共通約数が保存される根拠に焦点を当て、一次不定方程式の解を求める操作には進みません。

余りを差として、元の数を和として見る

正整数 d が整数 u を割るとは、ある整数 k を使って u = dk と書けることです。2数の正の共通約数は、両方を割る正整数です。最大公約数はその中で最大の数です。正整数 b の正の約数は有限個で、1は共通約数ですから、正整数 a、b の最大公約数は存在します。

図1のように、a = bq + r を2通りに読みます。左から右へ行くときは r = a − bq、右から左へ戻るときは a = bq + r を使います。矢印の両方を示すことで、片方にしかない共通約数がないと結論できます。

図1の上段で d が a と b を割るとします。整数 s、t を使って a = ds、b = dt と書けるので、次が成り立ちます。

r = a - bq
  = ds - dtq
  = d(s - tq)

s − tq は整数です。よって d は r も割り、b と r の共通約数です。ここで「a と b を割るなら r も割る」だけでは、取り替えた後に別の共通約数が増える可能性をまだ除いていません。

反対に d が b と r を割るとします。b = du、r = dv と整数 u、v を用いて表すと、次のようになります。

a = bq + r
  = duq + dv
  = d(uq + v)

したがって d は a も割ります。b と r の正の共通約数は、a と b の正の共通約数でもあります。両方の包含が成り立つので、正の共通約数の集合は一致します。集合が同じなら最大の要素も同じですから、gcd(a, b) = gcd(b, r) です。ここで gcd は正の最大公約数を表します。

r = 0 の場合も、この双方向の議論は使えます。0 = d・0 なので、どの正整数 d も0を割ります。したがって b と0の正の共通約数は b の正の約数と一致し、gcd(b, 0) = b です。0自体を正の約数に含めるのではありません。

基本例題：同じ約数の集合をたどる

正整数 203 と 77 について、除法の式を使って最大公約数を整数で求め、共通約数の集合が変わらない理由を説明してください。

まず各行の商と余りを確かめます。除数は正で、余りはそれぞれ除数より小さく非負です。

203 = 77・2 + 49
77 = 49・1 + 28
49 = 28・1 + 21
28 = 21・1 + 7
21 = 7・3 + 0

図2のように、第1行では 203 と 77 の正の共通約数と、77 と 49 の正の共通約数が一致します。例えば前者の共通約数 d は 49 = 203 − 77・2 も割ります。逆に 77 と 49 を割る d は 203 = 77・2 + 49 も割ります。どちらか一方の説明で止めず、同じ集合に戻れることを確認します。

同じ理由を各行に使うと、最大公約数は次のようにつながります。

gcd(203, 77) = gcd(77, 49)
             = gcd(49, 28)
             = gcd(28, 21)
             = gcd(21, 7)
             = gcd(7, 0)
             = 7

答えは 7 です。元の条件へ戻すと 203 = 7・29、77 = 7・11 なので、7は確かに両方を割ります。両方を割る正整数は上の集合の一致によって7と0の共通約数でもあるため、7より大きくなれません。この最後の説明が、単に7が共通約数だと確かめることと異なります。

各行の復元も有効です。例えば第2行の 49・1 + 28 は77に戻ります。余りが除数以上なら商を調整し直す必要があり、その行をそのまま次へ引き継いではいけません。計算結果と余りの範囲の両方を見ます。

標準例題：余りが0になるところで止める

正整数 259 と 111 の最大公約数を整数で求め、最後の非零の余りが答えになることを説明してください。

259 = 111・2 + 37
111 = 37・3 + 0

各行で共通約数の集合が一致するため、次のように移れます。

gcd(259, 111) = gcd(111, 37)
              = gcd(37, 0)
              = 37

答えは 37 です。最後の非零の余り37が次の行の除数となり、余り0が出ています。0を割る数として次の除法を行うのではなく、37と0の共通約数が37の約数と同じだと考えます。

元の数に戻すと 259 = 37・7、111 = 37・3 です。37が共通約数であることに加え、共通約数の集合が37の約数の集合まで変わらず続くので、それより大きい共通約数もありません。余り0を見つけた行の直前にある非零の値を読む理由が、ここで明らかになります。

余りが必ず0に到達することも確認します。正の余りが出る間、次の余りはその前の正の余りより小さい非負整数です。正整数が無限に小さくなり続けることはできません。もし0が出ないまま続くなら、最初の正の余りより小さい正整数を重複なく無限に並べることになり矛盾します。よって有限回で0に至ります。商が毎回1でなくても、この大小関係は変わりません。

発展例題：文字を含む数でも集合を比べる

n を0以上の整数とします。正整数 35n + 19 と 21n + 12 の最大公約数を、n に応じて整数で求めてください。

2数は n ≥ 0 で正です。大きい方を小さい方で割るとき、まず商を固定できるか確かめます。

(35n + 19) - (21n + 12) = 14n + 7
(21n + 12) - (14n + 7) = 7n + 5

14n + 7 は正で、21n + 12 より小さいので、最初の商は1です。次も 7n + 5 は正で、14n + 7 より小さいため商は1です。続けると、n によって商の見かけが変わる場所に注意が必要です。

(14n + 7) - 2(7n + 5) = -3
(14n + 7) - (7n + 5) = 7n + 2
(7n + 5) - (7n + 2) = 3

n ≥ 1 なら 7n + 2 は正で 7n + 5 より小さく、3も 7n + 2 より小さいので、これらは除法の余りとして使えます。n = 0 では 7n + 2 = 2 となり、3を余りとする除法の範囲を満たしません。ただし最大公約数を保存する差の議論自体は使えます。b と r が正でなくても、整数の和と差を割るという双方向の議論は成り立つからです。

この差の操作で、正の共通約数の集合について次が成り立ちます。

gcd(35n + 19, 21n + 12) = gcd(21n + 12, 14n + 7)
                           = gcd(14n + 7, 7n + 5)
                           = gcd(7n + 5, 3)

最後の等式は、14n + 7 = 2(7n + 5) − 3 によります。共通約数が負の数を割るとは、その負の数がその約数の整数倍になることです。符号を変えても割り切れる関係は変わりません。

7n + 5 を3で割った余りは n + 2 を3で割った余りと同じです。n を3で割った余りが0、1、2のとき、それぞれ 7n + 5 の余りは2、0、1です。したがって答えは、n を3で割った余りが1なら 3、それ以外なら 1 です。元の2数の共通約数が3を割ることは上の式で保証され、余り0の場合は両方が3で割り切れることも逆向きの関係から確認できます。

最初から「常に同じ数」と決めてしまうと、この場合分けを見落とします。実際には値は一定ではありません。一定だと予想した場合も、余りによる場合分けでその予想を点検できます。n = 0 なら19と12で最大公約数は1、n = 1 なら54と33で最大公約数は3となり、元の数でも確かめられます。

片道の証明と、誤った余りを直す

誤答として「a と b の共通約数は r も割る。よって最大公約数は変わらない」と書いたとします。この文は正しい方向を1つ示していますが、b と r の共通約数が a も割るという逆方向が欠けています。集合の一方が他方に含まれることだけでは、最大の要素が等しいと決められません。

図3のように、戻る矢印に a = bq + r を添えて修正します。d が b と r を割れば、それらの整数倍の和である a も割ります。これで両方の集合が一致し、最大公約数も一致すると言えます。

別の失敗は、負の差をそのまま除法の余りと呼ぶことです。発展例題の -3 は、共通約数を比べるための差として使えますが、正の除数に対する余りの範囲 0 ≤ r < b を満たしません。除法の行として進めるなら商を選び直します。集合の一致と、余りが小さくなることによる停止は別々に確かめます。

また、最後の行で0を最大公約数にするのも誤りです。0は正の約数ではなく、最後の非零の除数の正の約数をすべて割る対象です。最後の行を元の掛け算と足し算に戻し、どの数が割る側かを指で追ってください。

練習問題

次の数はすべて自作の条件です。最大公約数は正の整数で答え、説明を求める問題では割り切れる方向を明示してください。

正整数 187 と 68 の最大公約数を求め、各除法の式を書いてください。
正整数 143 と 65 について、143 と 65 の正の共通約数と、65 と余りの正の共通約数が一致することを説明してください。
正整数 155 と 93 の最大公約数を求め、最後の0が答えでない理由を述べてください。
正整数 a、b が a = 4b + 23、b > 23 を満たすとき、a と b の正の共通約数の集合が b と23のものと一致することを証明してください。
n を0以上の整数とします。8n + 5 と 5n + 3 の最大公約数を求め、n = 0 の場合も含めて説明してください。

解答と考え方

1

187 = 68・2 + 51
68 = 51・1 + 17
51 = 17・3 + 0

余りは各除数より小さい非負整数です。共通約数の集合を各行で引き継ぐと、gcd(187, 68) = gcd(17, 0) = 17 です。187 = 17・11、68 = 17・4 と元へ戻り、どちらも割り切れます。17より大きな共通約数がないことは、最後の集合が17の約数の集合であることから従います。

2

143 = 65・2 + 13
13 = 143 - 65・2

143 と65を割る正整数は差の13も割ります。逆に65と13を割る正整数は 65・2 + 13、つまり143も割ります。したがって両方の正の共通約数の集合は一致します。13は65の約数なので、その集合は13の正の約数である1と13です。元の143も13・11に戻り、両方の条件を満たします。

3

155 = 93・1 + 62
93 = 62・1 + 31
62 = 31・2 + 0

共通約数の集合を順に移すと、最大公約数は gcd(31, 0) = 31 です。0は正の約数ではありません。31 = 31・1、0 = 31・0 である一方、31を割る正整数は31以下なので、31が最大です。元の数も 155 = 31・5、93 = 31・3 と戻ります。

4

仮定 b > 23 > 0 により、23は b を除数とする除法の余りの範囲に入ります。正整数 d が a と b を割るなら、23 = a − 4b も割ります。反対に d が b と23を割るなら、a = 4b + 23 も割ります。したがって共通約数の集合は一致します。

この証明は、具体的な b の約数を並べる必要がありません。例えば b = 29 なら a = 139 となり、差 139 − 4・29 は23に戻ります。これは式の確認例であり、すべての b に対する証明は上の双方向の議論です。

5

(8n + 5) - (5n + 3) = 3n + 2
(5n + 3) - (3n + 2) = 2n + 1
(3n + 2) - (2n + 1) = n + 1
(2n + 1) - (n + 1) = n
(n + 1) - n = 1

n ≥ 1 なら各差は正です。ただし、除法の余りとして使うには、その直前の小さい数より小さいことも必要です。最後は n + 1 = n・1 + 1 ですが n = 1 のとき余り1は除数1と等しいため、この行は除法の行ではありません。それでも差による共通約数の集合の一致は成立します。n = 0 のときも同じ差の式は整数の式として成立します。

よって元の2数の共通約数は1を割り、正の共通約数は1です。答えは1です。n = 0 では5と3、n = 1 では13と8となり、それぞれ元の数で1が共通約数です。一般の結論は個別の検算ではなく、上の差を両方向に戻せることによります。