solution

Nghịch đảo modular với modulo bất kỳ

Khi modulo $n$ không nhất thiết là số nguyên tố, ta tìm nghịch đảo của $a$ qua Euclid mở rộng: nếu $\gcd(a,n)=1$ thì từ $ax+ny=1$ ta có $a^{-1}\equiv x\pmod n$.

Cho $a$, $n$. In $a^{-1}\bmod n$ trong $[0,n)$. Nếu $\gcd(a,n)\ne 1$ thì in $-1$.

Ví dụ

$5^{-1}\bmod 12 = 5$ vì $5\cdot5=25\equiv1\pmod{12}$.