확장 유클리드 알고리즘

단순히 $\gcd$를 구하는 것만이라면 유클리드 알고리즘의 동작 원리를 알 필요조차 없습니다. 컴파일러에 이미 내장되어 있기 때문입니다.

확장 유클리드 알고리즘은 $g = \gcd(a, b)$뿐만 아니라 다음을 만족하는 정수 계수 $x$와 $y$도 찾습니다.

해는 무한히 많다는 점에 주목하십시오. 해 $(x, y)$가 있을 때 $x$를 $b$만큼 늘리고 $y$를 $a$만큼 줄여도 등식은 변하지 않습니다.

#기본 아이디어

알고리즘 역시 재귀적입니다. $\gcd(b, a \bmod b)$를 재귀적으로 계산할 때 필요한 계수 $x’$와 $y’$를 이미 구했다고 합시다. 다시 말해, 쌍 $(b, a \bmod b)$에 대한 해 $(x’, y’)$가 있습니다:

이를 원래의 식과 비교하면, 원래의 $x$와 $y$로 $a$와 $b$의 계수를 취하면 된다는 것을 알 수 있습니다.

#구현

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

이 재귀 함수는 여전히 $\gcd(a, b)$ 값을 반환하지만, 그와 더불어 참조로 전달된 변수 $x$와 $y$에 구하려는 계수를 기록합니다.

#응용

이 알고리즘의 변형이 흥미로운 이유는 이를 이용하여 모듈러 역원, 즉 $a \cdot a^{1} \equiv 1$을 만족하는 원소 $a^{-1}$을 구할 수 있기 때문입니다. 이는 다음 식의 정수해를 구하는 것과 같습니다: