📂정수론

유클리드 호제법 증명

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

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

정리 ¹

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