乘法逆元我觉得其本质:就是数论里的倒数。
由上图你会发现:其取模的运算不满足除法的分配律,那么如何求除法的模运算呢?
在我们普通的数学中:
要求a / b可以转化为a x b-1其中b x b-1 = 1,其中b-1称为b的倒数。
那么同理,在数论我们可不可以用上面的那种方法来求b的类似于倒数的数,来将其转换为乘法呢?
答案:是肯定的,不过在数论里称为乘法的逆元。
有的小伙伴可能初学,不太懂上面的专业术语,故这里解释一下。
上面定义的解释:上面的那个三条线的符号是同余,意思就是说a乘于x取模和1取模是同余的都是1,即余数是相同的。
例子:
2 x 3≡1(mod 5 )即2 x 3对5取模和1对5取模是同余的都是1。其中3就是2的乘法逆元。
实战:
你会发现:我们运用乘法逆元,将其除法变成了一个乘法。这是十分的方便的,尤其是涉及到高精度或者其它的一些情况。
那么,问题来了。如何求一个数的乘法逆元呢?
求乘法逆元的方法有很多,这里先介绍通过运用费马小定理来求逆元。
ap-1≡1(mod p )等价于a x ap-2≡1(mod p )故a的乘法逆元就是ap-2
注意:乘法逆元不一定是存在的。
a存在乘法逆元的充要条件是a与模数p互质。当模数p为质数时,ap−2即为a的乘法逆元。
练习题:876.快速幂求逆元