この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。

万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。

信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。

履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。

翻訳後、{{翻訳告知|en|Euclidean algorithm|…}}をノートに追加することもできます。

Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

252と105のためのユークリッドの互除法のアニメーション。
クロスバーは、最大公約数（GCD）である21の倍数を表す。
それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。
残りの数は、GCD。

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]。
例

(問題) 1071 と 1029 の最大公約数を求める。

1071 を 1029 で割った余りは 42

1029 を 42 で割った余りは 21

42 を 21 で割った余りは 0

よって、最大公約数は21である。
証明

a, b は自然数で a ≠ 0 とする。b を a で割った商を q、剰余を r とするとb = qa + r

今、d0 を a と r の両方を割り切る自然数とする。

このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + r は b に等しい。したがって、d0 は a とb を割り切る。すなわち a と r の公約数はすべてb と aの公約数である。

逆に、d1 を b と a の両方を割り切る自然数とする。

d1 は qa を割り切るから差 b - qa を割り切るが、b - qa は r に等しい。したがって、d1 は a とrを割り切る。言い換えると b と a の公約数はすべてa と r の公約数である。

したがって、b と a の公約数全体の集合は a と r の公約数全体の集合に等しく、特に b と a の最大公約数は a と r の最大公約数でなければならない。
手続き的記述ユークリッドの互除法の仕組みは、この図のように最大公約数を求める対象の２つの整数を幅と高さに設定した長方形内での赤色の斜めの直線の描画過程によっても表現できる。 赤色の斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、かつ、その辺に対して45度の差を持たせて開始する。 描画範囲の辺の途中に当たれば、その内部へ直角反射するように角度を変える。 赤色の斜めの直線が反射後に描画範囲の向かいの辺と異なる辺の途中に当たる場合、描画範囲の長辺の長さを短辺の長さで割ると余りが生じる状態となっており、直前の反射地点を足掛かりに描画範囲を垂直に区切ってその範囲を絞りこむ。 （区切られて出来た小さいほうの範囲を以後の描画範囲とする） （除数および被除数の変更に相当） 赤色の斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となり、最後にして最小の描画範囲の短辺の長さが最大公約数となる。

手続き的に記述すると、次のようになる。
入力を m, n (m ≧ n) とする。

n = 0 なら、 m を出力してアルゴリズムを終了する。

m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。
拡張された互除法

整数 m, n の最大公約数 (英: Greatest Common Divisor) を gcd(m,n) と表すときに、（拡張された）ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。上の例の場合、m = 1071, n = 1029 のとき、1071 = 1 × 1029 + 421029 = 24 × 42 + 2142 = 2 × 21

であるから、gcd(1071, 1029) = 21 であり、21 = 1029 − 24 × 42 = 1029 − 24 × (1071 − 1 × 1029)= −24 × 1071 + 25 × 1029

となるので、x = −24, y = 25 である。

特に、m, n が互いに素（最大公約数が 1）である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。