유클리드 알고리즘을 이용하여 우리는 최대공약수 등을 간단히 구할 수 있었다. 이번엔 확장 유클리드 알고리즘에 대해 알아보자.
기본 유클리드 호제법을 확장하여 임의의 수 $X$, $Y$에 대해, $aX + bY = gcd(X,Y)$ 를 만족하는 (a,b)의 쌍을 찾을 수 있다. 이 때, $gcd(X,Y) = 1$ 인 경우 두 수는 서로소가 되므로 a는 modular multiplicative inverse 가 된다. 이를 이용하여 풀 수 있는 문제는 하단 STEPS 바에 있는 빨간색 +버튼을 눌러 확인할 수 있다.
알고리즘 구현법도 간단하다. 먼저 4개의 변수를 아래와 같이 초기화를 해준다.
step | U | V |
1 | 1 | 0 |
2 | 0 | 1 |
$X, Y$ 에 대해 각 스텝에서 X / Y 의 몫과 나머지를 각각 $S_i, R_i$ 라고 할 때, 몫이 0이 될 때까지
$$U_i = U_{i-2} - U_{i-1} * R_i$$
$$V_i = V_{i-2} - V_{i-1} * R_i$$
를 반복해준다. 계산이 종료된 시점의 마지막 U, V 값이 (X, Y)의 특수해가 된다. 만약 존재할 수 있는 모든 해를 구하는 경우에는, 특수해를 기준으로 디오판토스 방정식의 해를 구한뒤, $gcd(X,Y)$ 개수만큼의 해를 출력하면 된다.