유클리드 호제법 증명
Proof of Euclidean Algorithm
알고리즘
두 정수 $a \ge b$ 에 대해 $\text{gcd}(a,b)$ 는 다음과 같이 구할 수 있다.
Step 1. 초기화
$r_i, i=1,2,3,\cdots$ 에 대해 $a=r_0, b=r_1$ 이라고 두자.
Step 2. 반복법
$$ r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1}) $$ 이 성립하도록 $q_i$ 와 새로운 $r_{i+1}$를 계속 구한다.
Step 3. $r_{i+1}=0$ 일 때까지 반복하면 $r_i=\text{gcd}(a,b)$ 이다.
설명
이른바 유클리드 호제법Euclidean Algorithm으로 알려진 이 알고리즘은 최대공약수를 매우 효율적으로 구할 수 있게 해준다. 일일이 소인수분해를 하지 않고도 답을 내기 때문에 숫자가 커질수록 더욱 빛을 발한다.
위에서 정리된 알고리즘은는 순수하게 유클리드의 방식을 그대로 옮겨놓은 것일 뿐, 코드는 더 쉽게 짤 수 있다.
정리 1
$ r_i<r_{i+1}$ 에 대해 점화식 $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$ 을 만족시키는 $a: = r_{-1}$ 와 $b:=r_{0}$ 를 정의하자. $r_{n+1} = 0$ 을 만족시키는 $n$ 에 대해 $a,b$ 의 최소공배수는 다음과 같다. $$ r_{n} = \gcd (a,b) $$ 이 알고리즘은 많아도 $ 2 \log _2 (b) + 1 $ 번 안에 답을 구할 수 있다.
증명
$$ a = b \cdot q_1 + r_1 \\ b = r_2 \cdot q_2 + r_2 \\ r_1 = r_3 \cdot q_3 + r_3 \\ \vdots \\ r_i = r_{i+1} \cdot q_{i+1} + r_{i+2} \\ \vdots \\ r_{t-1} = r_t \cdot q_t $$
주어진 조건인
$$ r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1}) $$
에서 $r_{i-1}$ 와 $ r_i$ 의 약수는 $r_{i+1}$ 의 약수이기도 함을 알 수 있다. 따라서
$$ \text{gcd}( r_{i-1} , r_i )=\text{gcd}( r_i , r_{i+1} ) $$
한편 $r_{t-1} = r_t \cdot q_t \qquad , (r_{t+1}=0)$ 를 생각해보면
$$ \text{gcd}( r_{t-1} , r_t )=\text{gcd}( r_t \cdot q_t , r_t ) = r_t $$
이제 소요 시간, 즉 소요되는 횟수를 구해보자. 그에 앞서 $\displaystyle r_{i+2} < {1 \over 2} r_i $ 임을 보여야한다.
- $r_{i+1} \le {1 \over 2} r_i$ 일 경우 $$ r_{i+2} < r_{i+1} \le {1 \over 2} r_i $$
- $r_{i+1} > {1 \over 2} r_i $ 일 경우 $$ r_i = r_{i+1} \cdot 1 + r_{i+2} $$
이므로 $$ r_{i+2} = r_i - r_{i+1} < r_i - {1 \over 2} r_i \le {1 \over 2} r_i $$ 다. 정리하면 $$ r_{i+2} < {1 \over 2} r_i $$ 이고, 위 부등식에 의해 $$ \begin{align*} b =& r_1 \\ &>& 2 \cdot r_3 \\ &>& 2^2 \cdot r_5 \\ &>& \cdots \\ &>& 2^k \cdot r_{2k+1} \end{align*} $$ 이다. 정리하면 $$ b > 2^k \cdot r_{2k+1} $$ 한편 $2^k \ge b$ 이므로 $r_{2k+1} < 1$ 이어야하고, 그 말은 곧 $$ r_{2k+1} = 0 $$ 이다. 또한 $t+1 \le 2k +1$ 이므로 $$ t \le 2k $$ 다시 말해 알고리즘을 끝내는데 걸리는 총 횟수는 $t$ 보다 작거나 같고, $$ t \le 2k = 2(k-1) + 2 < 2 \log _2 (b) + 2 $$ 이므로 소요되는 횟수는 많아도 다음과 같다. $$ 2 \log _2 (b) + 1 $$
■
구현
아래는 유클리드 호제법을 R 코드로 작성한 것이다. 첫번째는 알고리즘을 그대로 옮겨놓은 버전이고, 아랫쪽은 쓸모없는 부분을 쳐내고 깔끔하게 정리한 버전이다.
gcd<-function(a,b)
{
if (b>a) {i=b; b=a; a=i;}
i=2
r=numeric(0)
r[1]=b
r[2]=a%%b
while(r[i]!=0)
{
r[i+1]=r[i-1]%%r[i]
i=i+1
}
return(r[i-1])
}
gcd <- function(a, b) {
if (b>a) {i=b; b=a; a=i;}
while(b) {
temp = b
b = a %% b
a = temp
}
return(a)
}
-
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p34. ↩︎