ユークリッド互除法とは?──最大公約数を効率的に求める方法を知りたい

ユークリッド互除法の使い方を確認しよう

ユークリッド互除法は、紀元前から知られる古典的なアルゴリズムで、現代でも数学やコンピュータサイエンスで広く使われています。大きな数の最大公約数を簡単に求められる優れた方法です。

ここでは、ユークリッド互除法の使い方と原理をまとめました。

ひと目でわかる"ユークリッド互除法の手順早見表"

基本原理

ユークリッド互除法の原理:

a=bq+rのとき、𝗀𝖼𝖽(a, b)=𝗀𝖼𝖽(b, r)

つまり、大きい数と小さい数の最大公約数は、小さい数と余りの最大公約数と同じ

ユークリッド互除法の計算手順

例題1: 84と36の最大公約数を求めよ

解答・解説

【ステップ1】84 を 36で割る

84=36×2+12

商: 2、余り: 12

【ステップ2】36 を 12 で割る

36=12×3+0

商: 3、余り: 0

【ステップ3】余りが 0 になったので終了

最後の「割る数」は 12

答:𝗀𝖼𝖽(84, 36)=12

例題2: 252 と 198 の最大公約数を求めよ

解答・解説

【計算の流れ】例題1と同様に計算する

252=198×1+54

198=54×3+36

54=36×1+18

36=18×2+0

答:𝗀𝖼𝖽(252, 198)=18

ポイント:複数回の割り算が必要でも、手順は同じです。余りが 0 になるまで続けます。

大きな数での計算

なぜ大きな数でも簡単か

ユークリッド互除法の最大の利点は、素因数分解が困難な大きな数でも、割り算だけで最大公約数が求まることです。

例題: 1071 と 1029 の最大公約数を求めよ

解答・解説

1071=1029×1+42

1029=42×24+21

42=21×2+0

答:𝗀𝖼𝖽(1071, 1029)=21

素因数分解との比較:

素因数分解なら 1071=3²×7×17 と複雑ですが、ユークリッド互除法なら3ステップで終わります。

応用問題

最小公倍数を求める

最大公約数がわかれば、最小公倍数も簡単に求められます。

公式:

例:84 と 36 の最小公倍数

𝗀𝖼𝖽(84, 36)=12 (すでに求めた)

答:252

3つ以上の数の最大公約数

3つ以上の数の最大公約数は、2つずつ順番に求めます。

𝗀𝖼𝖽(a, b, c)=𝗀𝖼𝖽(𝗀𝖼𝖽(a, b), c)

例: 𝗀𝖼𝖽(120, 84, 48) を求める

①まず 𝗀𝖼𝖽(120, 84)=12

②次に 𝗀𝖼𝖽(12, 48)=12

答:12

計算のコツと注意点

余りが 1 になったら

余りが1になった時点で、最大公約数は1 (互いに素) と確定します。

例:𝗀𝖼𝖽(17, 5)

17=5×3+2

5=2×2+1 ← 余りが1

余りが 1 になった時点で、17 と 5 は互いに素とわかります。

勉強の進め方と練習方法のアドバイス

• 手順を確実に覚える: 「割る→余りを出す→次は前の余りで割る→余り 0 で終了」という流れを体で覚えましょう。
• 最後は割る数が答え: 余りではなく「割る数」が最大公約数です。これを間違えないように注意しましょう。
• 表形式で整理: 計算が複雑になりそうなときは、表を使って整理すると間違いにくくなります。
• 検算を習慣に: 各ステップで a=bq+r を確認する習慣をつけましょう。
• 大きな数で練習: 100 以上の数でも練習すると、手順への理解が深まります。

練習は、たとえば「入門問題2題→標準問題3題→実戦問題2題→仕上げの小テスト10問」といった順で進めると、理解が深まるはずです。

間違えた問題は、原因別に整理します (余りの計算ミス/商と余りの混同/最後の答えを間違えるなど) 。翌日に同じタイプの問題を1問だけ解き直すことで、ミスの再発を防げます。

ユークリッド互除法と関連するその他の重要知識

ユークリッド互除法ができるようになると、整数問題の理解が一気に深まります。ここでは、次のステップとして押さえておきたい重要な知識を確認していきましょう。

• 拡張ユークリッド互除法: 𝗀𝖼𝖽(a, b)=ax+by の形で表す発展的な手法です。1 次不定方程式の解法に使います。
• 互いに素: 𝗀𝖼𝖽(a, b)=1 のとき、a と b は互いに素といいます。重要な性質があります。
• 1次不定方程式: ax+by=c の整数解を求める問題で、ユークリッド互除法が活躍します。

まとめ｜ユークリッド互除法のポイント

ここまでの内容を振り返り、押さえておくべきユークリッド互除法のポイントを整理しましょう。

ユークリッド互除法は最大公約数を効率的に求める方法

手順(4ステップ):

1. 1. 大きい数を小さい数で割り、余りを求める
2. 2. 元の小さい数を、今求めた余りで割る
3. 3. 余りが 0 になるまで繰り返す
4. 4. 余りが 0 になったときの「割る数」が最大公約数

利点:

• 大きな数でも簡単に計算できる
• 素因数分解が不要
• 計算が単純 (割り算と余りだけ)

主な応用:

• 最小公倍数:
• 分数の約分
• 1 次不定方程式の解法

よくある間違いと対策:

• 余りが答えと思う → 割る数が答え
• 計算途中で止める → 余り 0 まで続ける
• 余りの計算ミス → 検算を習慣に

ユークリッド互除法をマスターして、整数問題を得意にしよう!

ユークリッド互除法の理解は、高校数学の中でもつまずきやすい重要テーマです。しかし、

• 「手順がよくわからない」
• 「どれが答えかわからない」
• 「計算でミスをしてしまう」

といった壁に直面する高校生は多いです。そんなときに役立つのが進研ゼミのAI質問機能（お試し無料）。

AI質問の特徴

問題を撮影するだけ！
勉強中にわからない数学の問題を撮影すると、すぐにヒントや解き方を丁寧に解説してくれます。

考え方や途中過程まで、ステップごとに解説
答えだけでなく、解答に至るまでのステップをわかりやすく提示。追加解説まで丁寧に説明してくれます。

AI質問機能を活用することで、定期テストや入試の対策に向けて、理解の“穴”をすぐに埋めることに役立ちます。「進研ゼミ」は以下より無料で体験いただけます（スマートフォン／タブレットからアプリをダウンロード）。