模逆元

一句话理解

模逆元：a*x≡1 (mod m)。

为什么要学

除法变乘法。

讲解

存在条件 gcd(a,m)=1。可用扩欧或费马（m 质数）。

例子

2 在模 5 下逆元是 3，因为 6≡1。

常见错误

• m 不与 a 互质还求逆。
• 费马用在非质数模。