ユークリッドの互除法が何をしているのか｜数A整数

互除法は「割って余りを取る」を繰り返すだけ。手順は簡単です。だから作業としてはできる。

けれどなぜそれで最大公約数が出るのかを聞かれると答えられない——これでは応用が効きません。理由はたった1行で説明できます。

結論：公約数の集まりが変わらないから

を で割った商を 、余りを とします。

このとき と の公約数と と の公約数は、まったく同じ顔ぶれになります。

片方向： の公約数は の公約数

が と を割り切るなら

の右辺はどちらも の倍数なので、 も で割り切れます。

逆方向： の公約数は の公約数

が と を割り切るなら

の右辺はどちらも の倍数なので、 も で割り切れます。

だから最大公約数も同じ

公約数の集まりが完全に一致するので、その中の最大のものも当然一致します。

（ と の最大公約数）（ と の最大公約数）

これが互除法のすべてです。数を小さく取り替えても答えが変わらないから、小さくなるまで繰り返せばよい。

やってみる：1071 と 1029

割られる数	割る数	商	余り
1071	1029	1	42
1029	42	24	21
42	21	2	0

余りが0になったときの割る数21が答えです。

【検算】素因数分解で確かめます。

共通する部分は 。一致 ○

【検算2】21で両方を割ってみます。

商の51と49が互いに素（、）なので、21はこれ以上大きくできません ○

なぜ必ず終わるのか

余りは割る数より必ず小さいので、毎回小さくなります。

0以上の整数が減り続けることはできないので、いつか必ず0に到達します。無限に続くことはありません。

【検算】余りの列が減っているか確認するのは、計算ミスの発見にも使えます。余りが増えていたら、どこかで割り算を間違えています。

もう1つ：1155 と 1001

最大公約数は77です。

【検算】素因数分解すると

共通部分は 。一致 ○

最小公倍数もすぐ出る

（最小公倍数）

【検算】素因数分解から直接。 ○

素因数分解より速い理由

1071と1029くらいなら素因数分解もできます。ところが桁が増えると素因数分解は急に難しくなる。

一方、互除法は割り算を数回するだけ。数が大きくなっても手間はほとんど増えません。

方法	やること	大きい数では
素因数分解	素数で割り続ける	とても大変
互除法	余りを取り続ける	数回で終わる

「共通部分を探す」から「数を小さくする」への発想の転換——これが互除法の価値です。

逆にたどると不定方程式が解ける

を満たす整数 を1組求めよ。

互除法の式を下から順に、余りについて解いて代入します。

2つ目の42に、1つ目を代入すると

したがって

【検算】実際に代入します。

一致 ○

互除法は最大公約数を出すだけの道具ではありません。途中の式が、そのまま不定方程式の解になります。

互いに素かどうかの判定

最大公約数が1なら互いに素です。

最大公約数は1。91と30は互いに素です。

【検算】、。共通の素因数なし ○

余りに1が出た時点で、互いに素が確定します（次は必ず割り切れるため）。

学校の授業では、なぜここが飛ばされやすいのか

1. 手順が簡単すぎて、作業として完結してしまうから

互除法は割り算を繰り返すだけ。手順を示せばすぐできるようになります。

そのため「できる」状態に短時間で到達し、そこで先に進みやすい。「なぜ公約数が変わらないのか」という1行の説明に時間を配分する必要性が感じられにくい構成になっています。

2. 整数の性質が数Aの終盤に置かれているから

場合の数・確率・図形の性質と続いた最後に整数の性質が来ます。

その中でも互除法は約数と倍数の後半。年度末に近い時期に扱われやすく、丁寧な導入より手順の習得が優先されやすい位置にあります。

3. 応用（不定方程式）が別の項目として続くから

互除法の直後に一次不定方程式が来ます。そちらは解法が複雑なので、授業の重心がそちらに移りやすい。

結果として互除法は「不定方程式を解くための前段階」として通過され、それ自体が何をしているかを考える場面が確保されにくくなります。

「数を小さく取り替えても答えが変わらない」——この一文だけ持っておけば、逆にたどる操作の意味も自然に分かります。

【検算】3つの方法

1. 素因数分解で確かめる

数が小さければこれが最も確実です。共通の素因数をすべてかけたものが最大公約数。

【検算】、 → ○

2. 商が互いに素になっているか

求めた最大公約数 で両方を割ったとき、商どうしが互いに素でなければ はまだ大きくできます。

【検算】、。、 で互いに素 ○

3. 余りが減り続けているか

余りは必ず割る数より小さい。増えていたら計算ミスです。

【検算】 ○、 ○

よくあるミス

ミス1：商を答えてしまう

答えは最後の割る数（＝0になる直前の余り）です。

ミス2：余りが0になる前にやめる

0が出るまで続けます。途中の余りは答えではありません。

ミス3：割る順序を逆にする

大きい数を小さい数で割ります。逆にすると商が0になり、次で入れ替わるだけなので結果は同じですが、1回無駄になります。

ミス4：余りが割る数以上になっている

余りは必ず割る数より小さい。割り算のやり直しです。

ミス5：不定方程式で代入の向きを間違える

下の式から上へ、余りを順に置き換えていきます。

練習問題

1. 互除法で1071と1029の最大公約数を求めなさい（各段階の余りも書くこと）。
2. 互除法で1155と1001の最大公約数を求めなさい。
3. 91と30が互いに素であることを互除法で示しなさい。
4. 1の答えを素因数分解で検算しなさい。
5. 1155と1001の最小公倍数を求めなさい。
6. を満たす整数の組を1つ求めなさい。
7. 互除法で12と18の最大公約数を求めなさい。

解答

1. 余りは順に 42、21、0。最大公約数は21
2. 余りは順に 154、77、0。最大公約数は77
3. 、 より最大公約数は1。よって互いに素
4. 、。共通は 21 ○
5. 15015。検算： ○
6. より 。検算： ○
7. 、 より6。検算：、 → ○

まとめ

• 互除法は「数を小さく取り替える」操作
• 成り立つ理由は のとき、 の公約数と の公約数が同じだから
• 余りは必ず減るので、有限回で0になる
• 答えは余りが0になる直前の割る数
• 素因数分解より速い（大きい数ほど差が出る）
• 逆にたどると不定方程式の解が作れる
• 検算は素因数分解／商が互いに素か／余りが減っているか

互除法は「難しい問題を、同じ形の小さい問題に置き換える」という考え方の代表例です。この発想は数Bの漸化式—— を で表して小さくしていく——とまったく同じ構造をしています。手順ではなく、置き換えても答えが変わらない理由のほうを覚えてください。そちらは一生使えます。