유클리드 호제법 (Euclid's Algorithm)

목차로 돌아가기

 

유클리드 호제법은 두 수의 최대 공약수를 찾기 위한 알고리즘으로 알려져 있습니다. 정수 $a$와 $b$가 주어졌을 때 (최대공약수 정리 1)을 여러 번 이용하면 $a$와 $b$의 최대공약수를 찾을 수 있는 방법을 설명해드리겠습니다.

 

정리 1 정수 $a$와 $b$가 있을 때, 다음을 만족하는 정수 $q,r$ 를 고려하자. 여기서 $|a|>|b|$가 성립한다고 가정하자.

• $a =bq + r$
• $0 \leq r < |b|$

이는 (최대공약수 정리 1)에 의해서 존재한다. 그러면

\[ \mathrm{gcd}(a,b) = \mathrm{gcd}(b,r) \]

이 성립한다. 

 

증명

다음을 증명하면 이는 쉽게 증명됩니다. $d$가 $a$와 $b$의 공약수이다는 $d$가 $b$와 $r$의 공약수다와 동치다. $d$가 $a,b$의 공약수라고 합시다. 그러면 $d|a-bq = r$이 성립합니다. 반대로 $d$가 $b$와 $r$의 공약수일 경욱 $d|bq+r=a$가 성립합니다. 이로 인해서 $a$와 $b$의 공약수의 집합과 $b$와 $r$의 공약수의 집합이 동일함으로

\[ \mathrm{gcd}(a,b) = \mathrm{gcd}(b,r) \]

이 성립합니다.

 

참조 2 $a$를 정수라고 합시다. 그러면 $\mathrm{gcd}(a,0) = |a|$가 됩니다. $|a|$가 정리 1의 증명에 나온 정의를 성립한다는 것은 어렵지 않게 보여줄 수 있습니다.

 

정리 3(유클리드 호제법) 정수 $a$와 $b$가 있다고 하자. 여기서 $|a|>|b|$가 성립한다고 가정하자. $a=r_{-1}$ 그리고 $b=r_0$이라고 하자. (최대공약수 정리 1)을 여러번 사용하면 다음을 만족하는 정수 $q_i$와 $r_i$가 존재한다.

\[ r_{k-1} = r_kq_k+r_{k+1} \]

이를 조금 길게 쓰면 이렇게 된다

\[ \begin{array}{lcl} a & = & bq_0 +r_1 \\ b & = & r_1q_1 + r_2 \\ r_1 & = & r_2q_2 +r_3 \\ & \vdots & \end{array} \]

$k$가 $r_k=0$이 되는 가장 작은 정수라고 할 때, $\mathrm{gcd}(a,b) = |r_{k-1}|$이 성립된다.

 

증명

정리 1에 의해서 우리는 $|r_{k-1}| > |r_k|$이 성립함을 알 수 있습니다. 즉 $|r_k|$는 음수가 아닌 정수이기 때문에 무한히 줄일 수 없습니다. 즉 어느 순간에는 $r_k=0$이 되는 $k$가 존재하게 됩니다. 맨 처음 $0$되는 수를 $k$라고 합시다. 그러면 정리 1을 여러번 쓰게 되면

\[ (a,b) = (b,r_0) = \cdots (r_{k-1}, r_k) = (r_{k-1},0) = |r_{k-1}| \]

이 성립하기 때문에 증명이 완성됩니다.