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

a₁,a₂ をa₁ > a₂ となる自然数とするとき,

a₁ ÷ a₂ = d₁ 余り a₃
a₂ ÷ a₃ = d₂ 余り a₄
a₃ ÷ a₄ = d₃ 余り a₅
：
：

と, a₃,a₄,a₅,… を決めていくと,どこかで割り算が割り切れる。

そのとき,割った数が a₁ と a₂ の最大公約数である(ので,この方法を使ってa₁ と a₂ の最大公約数を求めることができる.)

このようにして,最大公約数を求める方法である.

この方法は次の３つの補題の結果により正当性が確かめられる.

補題1. a_n ÷ a_n+1 = d_n 余り a_n+2 のとき,a_n と a_n+1 の最大公約数は a_n+1 と a_n+2 の最大公約数と等しい.

補題2. a_n が a_n+1 で割り切れるとき,a_n と a_n+1 の最大公約数は a_n+1

補題3. 互助法のように次々と割っていくと,必ずどこかで割り切れる.

補題3.より必ず a_n が a_n+1 で割り切れて,わり算が終わりになるが,そのとき補題2.より a_n と a_n+1 の最大公約数は a_n+1, 補題1.を帰納的に使うと, a_n+1 は a₁ と a₂ の最大公約数である.