유클리드 호제법 증명
알고리즘
두 정수 $a \ge b$ 에 대해 $\text{gcd}(a,b)$ 는 다음과 같이 구할 수 있다.
의사코드
알고리즘: 유클리드 호제법 | ||
---|---|---|
In | 정수 $a, b$ 가 주어진다. | |
1. | $r_{0} \gets a$ | |
2. | $r_{1} \gets b$ | |
3. | while $r_{i+1} \ne 0$ | |
4. | 다음이 성립하도록 $q_i$ 와 새로운 $r_{i+1}$를 계속 구한다.$$r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1})$$ | |
5. | $i \gets i+1$ | |
6. | end while | |
Out | $a$ 와 $b$ 의 최대공약수 $\gcd (a,b)$ 를 얻는다. |
정리
$ 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 $ 번 안에 답을 구할 수 있다.
설명
이른바 유클리드 호제법euclidean Algorithm으로 알려진 이 알고리즘은 최대공약수를 매우 효율적으로 구할 수 있게 해준다. 일일이 소인수분해를 하지 않고도 답을 내기 때문에 숫자가 커질수록 더욱 빛을 발한다.
위에서 정리된 알고리즘은는 순수하게 유클리드의 방식을 그대로 옮겨놓은 것일 뿐, 코드는 더 쉽게 짤 수 있다.
증명 1
$$ \begin{align*} a = r_{0} =& b \cdot q_1 + r_1 \\ b = r_{1} =& r_2 \cdot q_2 + r_3 \\ &\vdots \\ r_i =& r_{i+1} \cdot q_{i+1} + r_{i+2} \\ &\vdots \\ r_{t-1} =& r_t \cdot q_t \end{align*} $$ 이라고 하자. 주어진 조건인 $$ 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. ↩︎