확장 유클리드 알고리즘 설명

이 포스트는 독자가 두 정수의 최대공약수를 구하는 유클리드를 알고 있다는 가정하에 쓰여졌습니다.

베주 항등식(Bezout's Identity)

먼저, 확장 유클리드 알고리즘을 이해하기 위해서는 베주 항등식이 무엇인지 정리하고 머리에 넣어둘 필요가 있다. 다음과 같은 식을 생각하자.

$$
ax+by=c \; (a,b는 정수)
$$

위 식이 정수해 $(x,y)$를 가지기 위해서는 $c$가 $GCD(a,b)$의 정수배여야만 한다는 것이 베주 항등식의 내용이다. 이는 확장 유클리드 알고리즘을 사용하게 되는 여러가지 곳에서 자주 나오게 되는 내용이니 기억해둘 필요가 있다. 증명은 사실 나도 안봤다.

확장 유클리드 알고리즘(Extended Euclid Algorithm)

유클리드 알고리즘은 $a,b$가 주어졌을 때, $a,b$의 최대공약수 $g=GCD(a,b)$를 구하는 알고리즘이었고, 아래와 같은 특성을 이용하여서 코드도 매우 간단하게 쓸 수 있다.

$$
g=GCD(a,b)=GCD(b,r), \quad a=bq+r
$$

이제 확장 유클리드 알고리즘(xGCD)를 살펴보자. 먼저, 이 알고리즘은 과연 어떠한 일을 하는 것인가? 아래와 같은 식을 생각하자.

$$
ax+by=g, \; g=GCD(a,b)
$$

위에서 봤던 베주 항등식과 같은 꼴이며, 우변이 $a,b$의 최대공약수이기 때문에 위 식은 언제나 $a,b$가 주어졌을 때 정수해 $(x,y)$를 가진다. 여기서 xGCD가 하는 일은 $a$와 $b$가 계수이며 우변이 최대공약수인 베주 항등식이 주어졌을 때, 정수해 $(x,y)$와 $GCD(a,b)$를 찾아주는 것이다. 알고리즘이 어떻게 해를 찾는지를 알아보기 위해서 식을 조금 바꿔쓰자. $a$를 $b$로 나누면, $a=bq+r$과 같이 표현할 수 있다. 이를 위 식에 대입하자.

$$
\begin{aligned}
(bq+r)x + by = g \\
b(qx+y) + rx = g \\
bx' + ry' = g
\end{aligned}
$$

대입한 결과에 $qx+y=x', \; x=y'$라고 놓으면 대입한 결과는 다시 베주 항등식의 꼴이 된다. xGCD가 하는 일은 베주 항등식의 계수가 주어졌을 때, 정수해와 최대공약수를 찾아준다고 하였다. 이제까지의 내용을 정리하자.

$xGCD(a,b)$는 베주항등식의 계수 $a,b$가 주어졌을 때, 정수해와 최대공약수를 찾아주는 알고리즘이며, $xGCD(a,b)$는 $xGCD(b,r)$를 알면 구할 수 있다. 그리고 이는 최대공약수를 구하는 유클리드 알고리즘과 형태가 매우 비슷하기 때문에 확장 유클리드 알고리즘이라고 불린다.

원래의 유클리드 알고리즘과 마찬가지로 언제 재귀가 끝나고, 이미 구한 값들을 어떻게 사용하는지 보자. 참고하기 위해 아래는 유클리드 알고리즘의 코드이다.

int gcd(int a, int b) {    // a >= b
    if(b == 0) return a;
    return gcd(b, a%b);
}

 

재귀가 끝나는 조건은 원래의 유클리드 알고리즘과 동일하다. $b$가 0일 경우에 종료한다. 베주 항등식에서 $b$에 0을 넣어보자.

$ax+0 \cdot y = g$로 $x$에 1을 넣으면, $a$가 찾고 있던 최대공약수이고, 이때의 정수해는 $(1,0)$이 된다.

base case를 정의했으니 이제 $xGCD(b,r)$을 통해 구한 $x',y'$를 이용해서 $x,y$를 구하자. $qx+y=x', \; x=y'$였고, $a=bq+r$이었으므로 $x,y$는 아래와 같다.

$$
\begin{aligned}
x &= y' \\
y &= x' - qy' \\
q &= a / b
\end{aligned}
$$

이걸로 실제 작성한 $xGCD$의 코드는 아래와 같다.

pair<int,pair<int,int>> xGCD(int a, int b) {    // it returns {g, {x,y}}, ax+by=g
    if(b == 0) return {a,{1,0}};
    pair<int,pair<int,int>> ret = xGCD(b, a%b);
    int g, x, y;
    g = ret.first;
    tie(x,y) = ret.second;
    return {g,{y,x-(a/b)*y}};   
}

추가로, 일반해는 아래와 같이 쓸 수 있다.

$$
\begin{aligned}
g,x_0,y_0 &= xGCD(a,b) \\
x &= x_0 + k \frac{b}{g} \\
y &= y_0 - k \frac{a}{g}
\end{aligned}
$$