Euclidean Algorithm

주어진 두 수의 최대공약수는 보통 소인수분해를 하여 구한다. 그러나 숫자가 커져가면 소인수분해가 힘들어지고, 최대공약수를 구하는 것 또한 만만찮은 작업이 된다. 이때 직접 소인수분해를 하지 않고도 최대공약수를 제시해주는 방법이 Euclidean Algorithm, 즉 유클리드 호제법이다. 기본적으로 알고리즘이므로 일련의 과정을 제시하고, 이 과정을 따라가면 반드시 최대공약수를 구할 수 있다. 

Euclidean Algorithm

    주어진 두 정수 $a, b$에 대해 gcd($|a|, |b|$) = gcd($a, b$)이므로 편의상 $a \geq b > 0$이라 가정해도 문제가 되지 않는다. Division Algorithm에 의해 $$a = q_1b + r_1 (0 \leq r_1 < b)$$ 를 만족하는 $q_1, r_1$은 유일하게 존재한다. 만일 $r_1 = 0$이라면 자명하게 gcd($a, b$) = b이고, $r_1 \neq 0$이라면 다시 Division Algorithm을 적용하여 $$b = q_2r_1 + r_2 (0 \leq r_2 < r_1)$$ 를 얻는다. 동일하게 $r_2 = 0$이라면 gcd($a, b$) = $r_1$이고, $r_2 \neq 0$이라면 다시 Division Algorithm을 적용한다.

    이와 같은 작업을 $n$번 시행했다고 하자. 이때 다음을 얻는다. $$\begin{align*} a =& \,\,q_1b + r_1 (0 < r_1 < b) \\ b =& \,\,q_2r_1 + r_2 (0 < r_2 < r_1) \\ r_1 =& \,\,q_3r_2 + r_3 (0 < r_3 < r_2) \\ \vdots \\ r_{n-2} =& \,\,q_nr_{n-1} + r_n (0 < r_n < r_{n-1}) \\ r_{n-1} =& \,\,q_{n+1}r_n + 0 \end{align*}$$ 이때 다음의 Lemma에 의해서 gcd($a, b$) = $r_n$임이 성립한다. 따라서 유클리드 호제법은 Division Algorithm을 $n$번 적용해서 최대공약수를 구하는 방법이다. 

Lemma

Lemma. If $a = qb + r$, then gcd($a, b$) = gcd($b, r$).

Proof. Let gcd($a, b$) = $d$. Then $\exists m, n \in \mathbb{Z}$ such that $a = md, b = nd$. Note that $a = qb + r = qnd + r = md \Longrightarrow r = (m - qn)d \Longrightarrow d \,|\, r$. 
By theorem 3, $d = ax + by$ for some $x, y \in \mathbb{Z}$. Then $d = ax + by = (qb + r)x + by = rx + b(qx + y)$. If $c \,|\, b$ and $c \,|\, r$, then $c \,|\, b(qx + y) + rx = d$. Thus $c \leq d \Longrightarrow$ gcd($b, r$) = $d$ = gcd($a, b$). $\blacksquare$