확장 유클리드 알고리즘

$ax + by = \gcd(a, b)$ 에서 정수해 $x$, $y$값을 빠르게 찾을 수 있는 알고리즘 이는 다음과 같은 과정을 통해 재귀적으로 구현할 수 있다.

$ax + by = \gcd(a, b)$

$a = bq + r$ (단, $q = \left \lfloor \frac{a}{b} \right \rfloor$, $r = a \mod b$)

$ax + by = (bq + r)x + by = b(qx + y) + rx = \gcd(a, b) = \gcd(b, r)$

$\Rightarrow bx’ + ry’ = \gcd(b, r)$

$\Rightarrow qx + y = x’, x = y’$

$\Rightarrow x = y’, y = x’ - \left \lfloor \frac{a}{b} \right \rfloor x = x’ - \left \lfloor \frac{a}{b} \right \rfloor y’$

결국 $b = 0$이 될 것이므로 재귀함수는 $a + 0 = \gcd(a, b) = a$ 일 때를 재귀 종료조건으로 한다.

auto egcd(int a, int b){
  if(b == 0) return {a, 1, 0};
  auto t = egcd(b, a % b);
  return {t.g, t.y, t.x - (a / b) * t.y};
}

나눗셈의 역원

어떤 값 $a$의 나눗셈 역원을 $x$라 하면 다음을 만족한다.

이는 임의의 정수 $y$에 대해 $ax + My = 1$ 과 같음을 알 수 있고 $\gcd(a, M) = 1$일때 확장 유클리드 알고리즘을 통해 $x$의 값을 구할 수 있다. 이때, $x$의 값이 $[0, M)$에 속하지 않을 수 있으므로 $x = (x + M) \mod M$ 으로 가공해준다.