확장 유클리드 호제법(Extended Euclidean Algorithm)은 유클리드 호제법의 확장으로 두 정수 $(a,b)$가 주어질 때 $\gcd(a,b)$를 구하고, 또한 정수해를 가지는 방정식 $ax + by = c$의 해 $(x, y)$를 구해주는 알고리즘이다.
베주 항등식의 세 번째 명제에 의해서 $ax + by$는 반드시 $\gcd(a,b)$의 배수이고, 따라서 $c$가 $\gcd(a, b)$의 배수가 아니라면 부정방정식 $ax + by = c$를 만족하는 정수해 $(x, y)$는 존재하지 않는다.
$c = \gcd(a,b)$라고 가정할 때, 해 $(x,y)$는 유클리드 호제법의 과정을 따라가면서 구해낼 수 있다. $a,b$에 대해 유클리드 호제법을 돌리는 과정을 식으로 표현하면 다음과 같이 나타낼 수 있다.
$$
a = bq_0 + r_1\\
b = r_1q_1 + r_2\\
r_1 = r_2q_2 + r_3\\
...\\
r_{i-1} = r_iq_i + r_{i+1}
$$
유클리드 호제법은 다음 나머지가 $0$일 때, 즉 $r_{i+1} = 0$일 때 종료된다. 또한 위 식에서 $r_{i+1} = r_{i-1} - r_iq_i$임을 알아낼 수 있다. $r_{i+1} = 0$이면 유클리드 호제법은 $\gcd(a,b) = r_i$를 반환하므로 $c = r_i$이다.
$c$를 $ax + by$의 꼴로 나타내기 위해서 $r_0 = a, r_1 = b$라고 했을 때 $r_0 = 1 \times a + 0 \times b$, $r_1 = 0 \times a + 1 \times b$가 된다. 임의의 i에 대해 $r_i$를 $na + mb$의 꼴로 나타내었을 때 $a$의 계수를 $s_i$, $b$의 계수를 $t_i$라 하면 $r_i = s_ia + t_ib$로 쓸 수 있다.
$r_i = s_ia + t_ib$와 $r_{i+1} = r_{i-1} - r_iq_i$라는 식을 이용해서 다음의 점화식을 유도해낼 수 있다.
$$
s_{i+1} = s_{i-1} - s_iq_i\\
t_{i+1} = t_{i-1} - t_iq_i
$$
따라서 $r_{i+1}$일 때 $\gcd(a, b) = r_i$이므로 $(s_i, t_i)$가 $ax + by = \gcd(a, b)$의 정수해 $(x, y)$가 된다. $c$가 $n \cdot \gcd(a, b)$라면 구한 $s_i, t_i$에 각각 $n$배를 해 주면 된다. 이를 구현한 코드는 다음과 같다.
tuple<ll, ll, ll> egcd(ll a, ll b) {
ll r0 = a, r1 = b;
ll s0 = 1, s1 = 0, t0 = 0, t1 = 1;
ll tmp = 0, q = 0;
while (r1) {
q = r0 / r1, tmp = r0;
r0 = r1, r1 = tmp - r1 * q;
tmp = s0, s0 = s1, s1 = tmp - s1 * q;
tmp = t0, t0 = t1, t1 = tmp - t1 * q;
}
return make_tuple(r0, s0, t0);
}
호제법과 모듈러 역원
덧셈과 곱셈에서는 모듈러 연산에 다음 분배법칙이 성립한다.
$$
(a + b) \bmod M = {(a \bmod M) + (b \bmod M)} \bmod M\\
ab \bmod M = (a \bmod M)(b \bmod M) \bmod M
$$
하지만 이는 나눗셈에서는 성립하지 않는다. 따라서 정수 $a$의 나눗셈의 결과를 알려면 $\bmod M$에 대한 $a$의 곱셈 역원 $a^{-1}$을 대신 곱해줌으로서 계산할 수 있다. 이때 $a^{-1}$은 $a \times a^{-1} \equiv 1 \pmod M$를 만족하는 값으로, $a^{-1} \equiv x \pmod M$을 만족하는 $x$의 값이다.
$ax \equiv 1 \pmod M$라는 식을 변형하면 임의의 정수 $y$에 대해 $ax = M\cdot y + 1$로 바꾸어 쓸 수 있다. 또한 $x,y$는 음수여도 상관 없기 때문에 다시 $ax + M\cdot y = 1$로 바꾸어 쓸 수 있고, 이제 확장 유클리드 호제법을 이용하여 $x$를 구하면 된다. 결과가 음수라면 $(x + M) \bmod M$으로 양수로 만들 수 있다.
식에서도 알 수 있지만 우변이 $1$이기 때문에 $\gcd(a, M) \neq 1$이면, 즉 $a$와 $M$이 서로소가 아니면 $\bmod M$에 대한 $a$의 곱셈 역원 $a^{-1}$은 존재하지 않는다.
ll modinv(ll a, ll M) {
if (gcd(a, M) != 1) return -1;
ll ret = (get<1>(egcd(a, M)) + M) % M;
return ret;
}