1. Introduction
호제법은 유클리드의 저서 원론에 적혀있는, 인류 최초의 알고리즘이다. 두 수의 최대공약수를 구하는 방법으로, 정의는 다음과 같다.
두 양의 정수 $a, b (a > b)$에 대하여 $gcd(a, b) = gcd(b, (a\bmod b))$이다.
2. Proof
$gcd(a, b)=G$라 하자. 그럼 적당한 서로소인 정수 $A, B$에 대해 $a=GA, b=GB$가 성립한다. 이를 $a=bq+r$에 대입하면, $GA=GBq+r$이고, $r=G(A−Bq)$이다. 여기서 $G$는 $b$와 $r$의 공약수임을 알 수 있다 ($b=GB, r=G(A−Bq)$).
만약 $B$와 $A−Bq$ ($b$와 $r$에서 $G$를 제외한 남은 부분)가 서로소이기만 하면, 즉 $gcd(B, A−Bq)=1$이면 $gcd(b, r)=G$이므로 증명이 끝난다.
이제 $B$와 $A−Bq$가 서로소임을 보이자.
$gcd(B, A−Bq)=m$ (단, $m\neq 1$)이라고 하면, 적당한 서로소인 정수 $k, l$에 대해 $B=mk, A-Bq=ml$이 성립한다. 한편, $A=ml+Bq=ml+mkq=m(l+kq)$이다. 즉, $m$은 $A$와 $B$의 공약수임을 알 수 있다. 그런데 $A$, $B$는 서로소이므로, $m=1$이다. 이는 곧 $B$와 $A-Bq$가 서로소임을 의미한다.
3. Practice
231과 1210의 최대공약수를 알아보자.
유클리드 호제법에 따라$$\begin{matrix}
gcd(231, 1210) &=& gcd(231, (1210 \bmod 231)) &=& gcd (231, 55) \\
&=& gcd (55, (231 \bmod 55)) &=& gcd (55, 11) \\
&=& gcd (11, (55 \bmod 11)) &=& gcd (11, 0) \\
&=&11 \end{matrix}$$
