📂정수론

유클리드 호제법 증명

Proof of Euclidean Algorithm

알고리즘

정리

$ 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}으로 알려진 이 알고리즘은 최대공약수를 매우 효율적으로 구할 수 있게 해준다. 일일이 소인수분해를 하지 않고도 답을 내기 때문에 숫자가 커질수록 더욱 빛을 발한다.

위에서 정리된 알고리즘은는 순수하게 유클리드의 방식을 그대로 옮겨놓은 것일 뿐, 코드는 더 쉽게 짤 수 있다.

증명 ¹

$$ \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)
}