2025.02.13

ユークリッドの互除法とは？計算の仕方や証明をわかりやすく解説！

最大公約数を求めるときに使えるユークリッドの互除法ですが、なぜこの方法で最大公約数が求められるのかを理解していない人も多いのではないでしょうか。

ユークリッドの互除法がなぜそうなるのかを理解しておくと、誤った操作をしないで済むようになります。

本記事ではユークリッドの互除法の計算の仕方や証明をわかりやすく解説します。

最大公約数を求める方法はほかにも3つほどあります。こちらの記事で詳しく解説していますので、合わせて参考にしてください。
最大公約数とは？最大公約数の簡単な求め方を1から解説！

ユークリッドの互除法とは？

ユークリッドの互除法は最大公約数を求めるときに使う方法で、大きな数同士の最大公約数を簡単に求めることができます。

ユークリッドの互除法で最大公約数を求めることができるのは、以下の性質が成り立つからです。

ただし、$gcd(A,B)$は$A$と$B$の最大公約数を表します。

これがなぜ便利かというと、$q$, $r$が正の自然数ならば$A>B$, $A>r$が成り立つので、$A$と$B$の最大公約数を求めるより、それより小さい数である$B$と$r$の最大公約数を求めるほうが簡単になるからです。

加えて、この操作を繰り返していき、$r$が$0$になったときの「割る数」が、最終的に$A$と$B$の最大公約数になります。

では、実際の例を用いてユークリッドの互除法の操作を確認してみましょう。

$1386$と$1848$の最大公約数を求めていきます。

大きい数字を$A$と置き、小さい数字を$B$とし、$r$が$0$以上、$q$が最大になるように計算します。
$1848=1386×1+462$

次に$B$と余りの$r$を使って同様に式をたてます。
$1386=462×3+0$
余りが0になりました。

なのでBの部分である$462$が$1386$と$1848$の最大公約数であることがわかりました。

実際に$1386=3×462$で$1848=4×462$なので、これ以上大きな公約数が無いことがわかります。

ユークリッドの互除法の証明

ユークリッドの互除法でなぜ最大公約数が求められるのかを解説します。

ユークリッドの互除法の中での1ステップである以下の性質を証明すれば帰納的に証明ができることになります。

2つの自然数$A, B$について$A$を$B$で割ったときの商を$q$余りを$r$とすると
$A$と$B$の最大公約数$=B$と$r$の最大公約数

それでは証明をしていきます。

2つの自然数$A,B(A>B)$において、最大公約数を$gcd(A,B)$とすると互いに素な自然数$A', B'$を用いて
$A=gcd(A,B)A'$
$B=gcd(A,B)B'$
と表せる。

このときユークリッドの互除法の定義から
$A=Bq+r$　…①
$r=A-Bq$
$r=gcd(A,B)(A'-B'q)$
なので$r$も同じ公約数$gcd(A,B)$を持つことがわかる。

ここで$B, r$は公約数に$gcd(A,B)$を持つので、最大公約数$gcd(B,r)$はこの公約数以上となり、
$gcd(B, r)\ge gcd(A,B)$…②
である。

また、$B,r$において、最大公約数$gcd(B,r)$と互いに素な自然数$B'', r''$を用いて
$B=gcd(B,r)B''$
$r=gcd(B,r)r''$
と表せる。

①を$gcd(B,r)$を用いて式変形すると
$A=gcd(B,r)(B''q+r'')$
と表せ、$A$も同じ公約数$gcd(B, r)$を持つことがわかる。

$A,B$は公約数に$gcd(B, r)$を持つので、最大公約数$gcd(A, B)$はこの公約数以上となり、
$gcd(A, B)\ge gcd(B,r)$…③
である。

②③により
$gcd(A,B)=gcd(B,r)$
が証明された。

最大公約数を求める応用問題

長方形を敷き詰める正方形の1辺とは？

2辺の長さが924, 110の長方形の枠に正方形のタイルを隙間なく敷き詰めたい。この正方形のタイルをできるだけ大きくするとき1辺の長さはいくらになるか。

この問題は924と110の最大公約数を求める問題に帰着できます。

なぜなら隙間なく正方形のタイルを敷き詰めるためには1辺の長さの整数倍が924にも110にもならなければならないため、正方形のタイルの1辺の長さは924と110の公約数である必要があります。

その中でもできるだけ大きくするということで最大公約数になります。

よってユークリッドの互除法を用いて計算すると、
$924 = 110 × 8 + 44$
$110 = 44 × 2 + 22$
$44 = 22 × 2 + 0$
よって22が最大公約数となり、正方形のタイルの1辺の長さは22と求まります。

不定方程式の解

$8x+11y=1$を満たす整数$(x, y)$の組を1組求めよ。

これもユークリッドの互除法を使って求めることができます。

8と11においてユークリッドの互除法を用いて計算していくと
$11 = 8×1+3$　…①
$8 = 3×2+2$　…②
$3 = 2×1+1$　…③
となり、不定方程式の右辺である1が余りとして出てきました。

③式を変形した
$3-2=1$　…③’
の左辺を8と11のみを使った式で表すことで不定方程式の解を求めるというアプローチです。

③’に①②を変形した
$3=11-8$　…①’
$2=8-3×2$　…②’
を代入すると
$(11-8)-(8-3×2)=1$

さらに3の部分に①’を代入し、不定方程式の形に整えると
$11-8-8+(11-8)×2=1$
$8×(-4)+11×3=1$

よって$x=-4, y=3$とわかります。

ユークリッド互除法を使った練習問題

1.486と1134の最大公約数を求めよ

解答はこちら

2.$6x-34y=2$の整数解を1つ求めよ

解答はこちら

まとめ

いかがでしたでしょうか。本記事では、ユークリッドの互除法の計算方法や証明方法から、ユークリッドの互除法を用いた問題の解き方を解説しました。

ユークリッドの互除法はとても効率的に最大公約数を求められる方法であり、原理を理解しておくとさまざまな問題に応用することができます。

ユークリッドの互除法は初めて見ると理解しづらい部分があるかもしれませんが、練習問題を繰り返し解いて理解を深めていきましょう。

教室数・生徒数No.1の個別指導塾！

明光義塾では、勉強の進め方や、勉強計画の立て方など、学習の質を高めるための豊富なノウハウを持っています。お子さまの抱える課題に向き合いながら、目標に向かって効率的な勉強を行えるようサポートできます。

お子さまの現状の課題を知りたい方、お子さまの更なる成長をお考えの方は、ぜひ一度お近くの明光義塾までお気軽にご相談ください。

近くの教室を探す

明光プラスで読みたい記事のテーマを募集

明光プラスでは読者の方のご期待に沿えるように読みたい記事のテーマを募集しています。ぜひ下のリンクからアンケートにお答えください。

読みたい記事のテーマをリクエストする

あわせて読みたい記事

最大公約数とは？最大公約数の簡単な求め方を1から解説！

2025.02.13

最大公約数は小学5年生で最初に学習しますが、高校数学の数学Aでも扱います。一見、単純に見える最大公約数ですが、数学Aの整数問題では素因数分解やユークリッドの互除法といったものを用いて求める必要があ...
ルートや平方根について概念や計算方法を1からやさしく解説！

2025.01.30

中学3年生から出てくるルート(√)や平方根は、幅広く使われるため大学受験でも必須の知識です。しっかりと理解しておきたいところですが、なかなか理解できず計算が難しいと感じる方も多いのではないでしょうか...
積分とは○○です！積分を最初からやさしく解説し、覚えるべき公式を紹介！

2025.01.22

高校数学の教育課程で避けては通れない積分。微分と同様に苦手に感じていたり、つまずいたりしてしまう方も多いのではないでしょうか。そこで本記事では、積分とは一体何なのかをわかりやすくかみ砕いて紹介し、...