확장 유클리드 호제법(Extended Euclidean Algorithm)

확장 유클리드 호제법

양의 정수 $a$, $b$, $c$가 주어질 때 다음 선형 디오판토스 방정식(linear Diophantine equation)을 만족하는 정수 $x$, $y$를 구해봅시다.

\[ ax+by=c \]

만약 $c$가 $a$와 $b$의 최대공약수 $\mathrm{gcd}(a,b)$의 배수가 아니라면 좌변은 최대공약수의 배수이지만 우변은 최대공약수의 배수가 아니므로 모순입니다. 따라서 $c$는 무조건 $a$와 $b$의 최대공약수로 나누어 떨어져야 합니다.

먼저 $c$가 $\mathrm{gcd}(a,b)$인 경우를 생각합시다. $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$이라 하면 $a=bq+r$이고, 이를 위 방정식에 대입하면

\[ (bq+r)x+by=b(qx+y)+rx=\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r) \]

즉, $a$와 $b$가 주어졌을 때 방정식의 해는 $b$와 $r$이 주어졌을 때 방정식의 해를 이용해서 구할 수 있습니다. 이걸 재귀적으로 계속 반복하면 유클리드 호제법과 마찬가지로 결국에는 $b$가 0이 될 것이고, 그때 $a$는 $\mathrm{gcd}(a,b)$, $x$는 1, $y$는 0이 되겠죠. 이 알고리즘을 확장 유클리드 호제법이라고 합니다.

유클리드 호제법 코드에 조금만 추가하면 쉽게 구할 수 있습니다.

예시로 1914와 899를 넣으면 최대공약수 29와 $1914x+899y=29$를 만족하는 정수 8, -17이 나옵니다. $c$가 $\mathrm{gcd}(a,b)$의 배수일 때에는 확장 유클리드 호제법으로 구한 $x$와 $y$를 정수배하면 됩니다.

선형 디오판토스 방정식의 일반해

선형 디오판토스 방정식의 해는 유일하지 않습니다. 두 해 $x_1$, $y_1$과 $x_2$, $y_2$를 생각하면 $ax_1+by_1=ax_2+by_2=c$이므로 $a(x_2-x_1)=b(y_1-y_2)$가 됩니다. $b(y_1-y_2)$이 $a$의 배수가 되려면 $y_1-y_2$가 $a/\mathrm{gcd}(a,b)$의 배수여야 하기 때문에 적당한 정수 $k$에 대해\[ y_2 = y_1-k\frac{a}{\mathrm{gcd}(a,b)} \]마찬가지로\[ x_2 = x_1+k\frac{b}{\mathrm{gcd}(a,b)} \]이것이 선형 디오판토스 방정식의 일반해가 됩니다.

모듈로 연산에서 곱셈에 대한 역원 구하기

법 $m$에 대한 모듈로 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의합니다.\[ ax \equiv 1 \pmod{m} \]모듈로 연산의 정의에 의해 $ax-1=-my$를 만족하는 정수 $y$가 존재해야 하고, 다시 말해\[ ax+my=1 \]을 만족하는 정수 $x$와 $y$가 존재한다는 말이 됩니다. 위에서 살펴본대로 $a$와 $m$의 최대공약수가 1(즉, 서로소)이면 해가 존재하고, 그렇지 않으면 $a^{-1}$은 존재하지 않습니다.

응용

BOJ 14565:: 역원(Inverse)

https://www.acmicpc.net/problem/14565

$n$과 $a$가 주어질 때 법 $n$에 대한 모듈로 연산에서 덧셈과 곱셈에 대한 역원을 구하는 문제입니다. 덧셈에 대한 역원은 당연히 $n-a$고, 곱셈에 대한 역원은 확장 유클리드 호제법으로 구할 수 있습니다. 계산 결과로 나온 최대공약수가 1이 아니면 곱셈에 대한 역원이 없음에 주의합시다.

BOJ 3955:: 캔디 분배

https://www.acmicpc.net/problem/3955

$KX+1=CY$를 만족하는 양의 정수 $X$와 $Y$가 존재하는지 판별하는 문제입니다. 다르게 말하자면 $KX+CY=1$을 만족하는 음의 정수 $X$와 양의 정수 $Y$가 존재하는지 판별하는 문제가 됩니다. 일단 $K$와 $C$가 서로소인지 확인합시다. 그 다음 확장 유클리드 호제법으로 구한 해를 $X_0$와 $Y_0$라고 하면 위에서 말했듯이 일반해는

\[ X = X_0 + tC, \quad Y = Y_0 – tK \]

가 됩니다($t$는 정수). $X$는 음의 정수, $Y$는 양의 정수이고 문제 조건에서 사탕 봉지가 $10^9$개를 넘지 않는다고 했으므로,

\[ X_0 + tC < 0, \quad 0 < Y_0 – tK \le 10^9 \]

\[ \therefore \frac{Y_0 – 10^9}{K} \le t < \min\left(-\frac{X_0}{C}, \frac{Y_0}{K}\right) \]

이를 만족하는 정수 $t$가 존재하면 $Y$를 출력하면 되고, 아니면 불가능한 경우입니다.

BOJ 9267:: A + B

icpc.me/9267

처음에 $a$와 $b$의 값을 각각 $a_0$, $b_0$라 하면 두 명령을 적용해서 만들 수 있는 수는 모두 $a_0x + b_0y$ 꼴로 나타낼 수 있습니다($x$와 $y$는 음이 아닌 정수). 그런데 $s$가 저 꼴이라고 항상 되는 게 아닙니다. 예를 들어 $6a_0+10b_0$ 같은 수는 두 명령을 어떻게 써도 만들 수 없습니다. 그렇다면 $x$와 $y$는 어떤 조건을 만족해야 할까요?

처음에 $a_0$와 $b_0$로 시작해서 만들 수 있는 수들은 모두 처음에 $a_0+b_0$와 $b_0$로 시작해서 만들 수 있거나 $a_0$와 $a_0+b_0$로 시작해서 만들 수 있는 수입니다. 만약 $a_0$와 $b_0$에서 시작해서 $6a_0+10b_0$를 만들 수 있다면

\[6a_0+10b_0=6(a_0+b_0)+4b_0\]

이므로 $a_0+b_0$와 $b_0$에서 시작해서 $6(a_0+b_0)+4b_0$를 만들 수 있다는 뜻이고, 같은 명령들을 $a_0$와 $b_0$에서 시작하는 경우에 적용하면 $6a_0+4b_0$를 만들 수 있다는 뜻이 됩니다. 그럼 다시

\[6a_0+4b_0=2a_0+4(a_0+b_0)\]

이므로 $a_0$와 $a_0+b_0$에서 시작해 $2a_0+4(a_0+b_0)$를 만들 수 있고, 똑같이 $a_0$와 $b_0$에서 시작해 $2a_0+4b_0$를 만들 수 있습니다. 계속해서 한 번 더 적용하면 $2a_0+2b_0$를 만들 수 있고, 또 적용하면 $2a_0$(또는 $2b_0$)를 만들 수 있다는 결론이 나오는데 이건 불가능하죠. 따라서 $6a_0+10b_0$는 만들 수 없음이 증명됩니다. 아하! 유클리드 호제법이네요.

$a_0x+b_0y$를 만들 수 있으면 위 과정에 의해 $\gcd(x, y)a_0$나 $\gcd(x, y)b_0$ 또한 만들 수 있어야 하므로 $\gcd(x, y)=1$이어야 합니다. 결론적으로 이 문제는

\[a_0x+b_0y=s, \quad \gcd(x,y)=1\]

을 만족하는 음이 아닌 정수 $x$와 $y$가 존재하는지 묻는 문제가 되고, 이는 확장 유클리드 호제법으로 쉽게 풀 수 있습니다.