유클리드 호제법 (유클리드 알고리즘 / Euclidean Algorithm) 은 다음과 같습니다.
두 양의 정수 $a$, $b$ ($a \geq b$), $a = bq + r$ ($0 \leq r < b$)인 정수 $q$, $r$에 대하여 $$ \gcd(a, b) = \gcd(b, r) $$ 이다. ($\gcd(a, 0) = a$)$\gcd(a, b)$는 최대공약수 입니다.
$g_{1} = \gcd(a, b)$, $g_{2} = \gcd(b, r)$이라 하면, 최대공약수의 성질에 의해 $g_{1} \mid a$, $g_{1} \mid b$이다.
$a = bq + r$에서, $a$도 $g_{1}$의 배수, $bq$도 $g_{1}$의 배수 ($b$가 $g_{1}$의 배수이므로) 이다. 따라서 $r$도 $g_{1}$의 배수이다. (-> $g_{1} | r$)
$g_{1}$은 $b$, $r$의 공약수이고, $g_{2}$는 $b$, $r$의 공약수 중 최대이므로 $g_{1} \leq g_{2}$이다.