확장 유클리드 알고리즘¶

유클리드 알고리즘은 두 음이 아닌 정수 $a$와 $b$의 최대공약수(GCD)만 계산하지만, 확장 버전은 GCD를 $a$와 $b$로 나타내는 방법, 즉 다음을 만족하는 계수 $x$와 $y$도 함께 찾습니다:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

베주 항등식에 의해 이러한 표현을 항상 찾을 수 있다는 점에 유의해야 합니다. 예를 들어, $\gcd(55, 80) = 5$이므로 $5$를 항 $55$와 $80$의 선형 결합으로 나타낼 수 있습니다: $55 \cdot 3 + 80 \cdot (-2) = 5$

이 문제의 더 일반적인 형태는 선형 디오판토스 방정식에 관한 글에서 다룹니다. 그 글은 이 알고리즘을 바탕으로 합니다.

알고리즘¶

이 절에서는 $a$와 $b$의 GCD를 $g$로 표기하겠습니다.

원래 알고리즘에서 바뀌는 부분은 매우 간단합니다. 알고리즘을 떠올려 보면, 알고리즘이 $b = 0$이고 $a = g$인 상태로 끝난다는 것을 알 수 있습니다. 이 매개변수들에 대해서는 계수를 쉽게 찾을 수 있으며, 바로 $g \cdot 1 + 0 \cdot 0 = g$입니다.

이 계수 $(x, y) = (1, 0)$에서 시작하여 재귀 호출을 거슬러 올라갈 수 있습니다. 우리가 할 일은 $(a, b)$에서 $(b, a \bmod b)$로 전이하는 동안 계수 $x$와 $y$가 어떻게 변하는지 알아내는 것뿐입니다.

$(b, a \bmod b)$에 대한 계수 $(x_1, y_1)$을 찾았다고 가정합시다:

$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

그리고 $(a, b)$에 대한 쌍 $(x, y)$를 찾고자 합니다:

$$ a \cdot x + b \cdot y = g$$

$a \bmod b$는 다음과 같이 나타낼 수 있습니다:

$$ a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$

이 식을 $(x_1, y_1)$의 계수 방정식에 대입하면 다음을 얻습니다:

$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$

그리고 항을 재배열하면 다음과 같습니다:

$$g = a \cdot y_1 + b \cdot \left( x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$

$x$와 $y$의 값을 구했습니다:

$$\begin{cases} x = y_1 \\ y = x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \end{cases} $$

구현¶

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

위의 재귀 함수는 GCD를 반환하고, 계수의 값을 x와 y에 저장합니다(이 둘은 함수에 참조로 전달됩니다).

이 확장 유클리드 알고리즘 구현은 음의 정수에 대해서도 올바른 결과를 냅니다.

반복 버전¶

확장 유클리드 알고리즘을 반복적인 방식으로 작성하는 것도 가능합니다. 재귀를 피하기 때문에, 이 코드는 재귀 버전보다 조금 더 빠르게 실행됩니다.

int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

변수 a1과 b1을 자세히 살펴보면, 이들이 일반 유클리드 알고리즘의 반복 버전에서와 정확히 같은 값을 가진다는 것을 알 수 있습니다. 따라서 이 알고리즘은 적어도 올바른 GCD는 계산합니다.

이 알고리즘이 왜 올바른 계수를 계산하는지 알아보기 위해, 다음 불변식들이 어느 시점에서나(while 루프가 시작되기 전과 각 반복이 끝날 때) 성립한다는 점을 생각해 보십시오:

$$x \cdot a + y \cdot b = a_1$$

$$x_1 \cdot a + y_1 \cdot b = b_1$$

한 반복이 끝날 때의 값을 프라임($'$)으로 표기하고, $q = \frac{a_1}{b_1}$이라고 가정합시다. 유클리드 알고리즘으로부터 다음을 얻습니다:

$$a_1' = b_1$$

$$b_1' = a_1 - q \cdot b_1$$

첫 번째 불변식이 성립하려면 다음이 참이어야 합니다:

$$x' \cdot a + y' \cdot b = a_1' = b_1$$

$$x' \cdot a + y' \cdot b = x_1 \cdot a + y_1 \cdot b$$

마찬가지로 두 번째 불변식에 대해서는 다음이 성립해야 합니다:

$$x_1' \cdot a + y_1' \cdot b = a_1 - q \cdot b_1$$

$$x_1' \cdot a + y_1' \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$$

$a$와 $b$의 계수를 비교하면 각 변수에 대한 갱신 방정식을 유도할 수 있으며, 이를 통해 알고리즘 전체에 걸쳐 불변이 유지되도록 보장합니다.

마지막에는 $a_1$에 GCD가 담겨 있음을 알고 있으므로, $x \cdot a + y \cdot b = g$가 성립합니다. 즉, 필요한 계수를 찾은 것입니다.

코드를 더 최적화하여 변수 $a_1$과 $b_1$을 코드에서 제거하고 $a$와 $b$를 그대로 재사용할 수도 있습니다. 그러나 그렇게 하면 불변식을 근거로 논증할 수 없게 됩니다.

확장 유클리드 알고리즘¶

알고리즘¶

구현¶

반복 버전¶

연습 문제¶