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の個別指導塾！

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

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

近くの教室を探す

あわせて読みたい記事

微分とは？微分は○○です！定義・公式・使い方を解説

2025.07.07

高校数学の教育課程で避けては通れない微分。苦手に感じていたり、つまずいたりしてしまう方も多いのではないでしょうか。本記事では、微分とは何かという定義から、基本公式・実際の使い方・例題・応用までを、...
三角関数（sin, cos, tan）入門！公式をわかりやすく覚える方法を紹介！

2025.06.26

三角関数では$\sin$(サイン),$\cos$(コサイン),$\tan$(タンジェント)や$\theta$(シータ)といった聞きなれない呪文のような言葉が多く出てくるのに加え、覚える公式が多いため...
三角比(sin, cos, tan)とは？覚え方と三角比の表も紹介！

2025.06.20

三角比ではsin(サイン),cos(コサイン),tan(タンジェント)やθ(シータ)といった聞きなれない呪文のような言葉がでてくるうえに、覚えることも多いため苦手意識を持っている方も多いのではないで...