Modular Inverse

Modular inverse란, 어떠한 M에 대해서, 곱셈에 대한 역원을 구하는 것이다.

M이 소수이고, \(1 \leq x < M \)인 \(x\)가 있다고 하자.

\(xy \equiv 1 \pmod M \)인 \(y\)를 찾을 수 있을까?

Fermat's little theorem에 의해, \({x}^{M-1} \equiv 1 \pmod M\)이므로 \(y=x^{M-2}\)일 때 성립함을 쉽게 알 수 있다.

이는 combination 연산에 이용할 수 있다.

\( \dbinom {n}{r} = \dfrac {n!} {r!(n-r)!} \equiv (n!) \cdot (r!)^{M-2} \cdot ((n-r)!)^{M-2} \)