예제로 알아보는 확장 유클리드 알고리즘

 

 

유클리드 알고리즘

이 글을 이해하기 위해서는 유클리드 알고리즘을 먼저 이해해야 합니다. 다음 동영상을 참고하시기 바랍니다.

 

 

 

 

확장 유클리드 알고리즘

$x, y$ 에 대한 부정방정식 $ax+by=c$ 는 $c$ 의 값이 ${\rm gcd}(a, b)$ 의 배수일 때만 정수해를 갖는다고 알려져 있다. 즉, $ax+by=c$ 가 정수해를 갖는 $c$의 최솟값이 ${\rm gcd}(a, b)$ 가 되는 것이다. 따라서 확장 유클리드 알고리즘은 말 그대로 유클리드 알고리즘을 확장하여 $a, b$ 의 최대공약수 뿐만 아니라, $ax+by={\rm gcd}(a, b)$를 만족하는 정수해 $x, y$ 도 구하는 알고리즘이라고 생각하면 된다.

 

$240$ 과 $46$ 의 최대공약수를 $c={\rm gcd}(240, 46)$ 라고 할 때 부정방정식 $240x+46y=c$ 의 정수해 및 $c$ 를 구해보자.

 

먼저 유클리드 알고리즘을 적용하도록 하자.

 

 

1.  $240=46 \times 5+10$ 이므로 $$10=240 \times 1+46 \times (-5) \label{a}\tag{i}$$
2.  $46=10 \times 4 + 6$ 이므로 $$\begin{split} 6 &= 46 - 10 \times 4 \\ &= 46 - (\ref{a}) \times 4 \\ &= 46 -240 \times 4 + 46 \times 20 \\ &= 240 \times (-4) + 46 \times 21 \end{split} \label{b} \tag{ii}$$
3. $10=6 \times 1 + 4$ 이므로 $$\begin{split} 4 &= 10 - 6 \times 1 \\ &=(\ref{a}) - (\ref{b}) \times 1 \\ &= 240 \times 1 - 46 \times 5 -240 \times (-4) -46 \times 21 \\&= 240 \times 5 + 46 \times (-26) \end{split} \label{c} \tag{iii}$$
4. $6=4 \times 1 +2$ 이므로 $$ \begin{split} 2 &= 6 - 4 \times 1 \\ &= (\ref{b}) - (\ref{c}) \times 1 \\ &= 240 \times (-4) + 46 \times 21 - 240 \times 5 + 46 \times 26 \\&= 240 \times (-9) +46 \times 47 \end{split} \label{d} \tag{iv} $$
5. $4=2 \times 2 + 0$ 이므로 끝낸다.

 

 

결국 $240$ 과 $46$ 의 최대공약수는 $2$ 이고, $240x+46y=2$ 를 만족하는 정수해는 $x=-9, \; y=47$ 이 된다.

위의 연산 과정을 이해했다면 알고리즘을 프로그래밍에 적용시키는 것은 어려운 일이 아니다.

$$r_0 = a, \; r_1 = b$$

$$s_0=1, \; s_1 = 0$$

$$t_0=0, \; t_1 = 1$$

을 초기값으로 시작한다. 즉, 위의 예제에서는 $r_0=240, \; r_1 = 46$ 이 되어 

$$240 = s_0 \times r_0 + t_0 \times r_1$$

$$46 = s_1 \times r_0 + t_1 \times r_1$$ 

이 되는 것이다.

이제 다음의 식들로 $r, \; s, \; t$ 값들을 업데이트 한다.

$$r_{i+1} = r_{i-1} - q_i r_i $$

$$ s_{i+1} = s_{i-1} - q_i s_i$$

$$ t_{i+1} = t_{i-1} - q_i t_i$$

이때, $q_i$ 와 $r_{i+1}$ 은 각각 $r_{i-1}$ 을 $r_i$ 로 나눈 몫과 나머지가 된다.

이 연산과정은 $r_{k+1}=0$ 이 되면 멈추게 되고, ${\rm gcd}(a, b)=r_k$, 부정방정식 $ ax+by=r_k$ 의 정수해는 $x=s_k, \; y=t_k$ 가 되는 것이다.

 

파이썬을 이용하여 $r_k, \; s_k , \; t_k$ 을 반환하는 함수를 만들어 보면 다음과 같을 것이다.

 

def exeu(a, b):
    r = [a, b]
    s = [1, 0]
    t = [0, 1]
    while r[-1] != 0:
        q = int(r[-2] / r[-1])
        r.append(r[-2] - q * r[-1])
        s.append(s[-2] - q * s[-1])
        t.append(t[-2] - q * t[-1])
    return (r[-2], s[-2], t[-2])