深入浅出乘法逆元

2019-04-13 22:06发布

站内文章 / 模拟电子
16305 0 1747
class="markdown_views prism-atom-one-light">

浅析乘法逆元

1.模的运算律

先来一波模运算律表： 运算律 内容 交换律 (a+b)%p=(b+a)%p
(a×b)%p=(b×a)%p 结合律 ((a+b)%p+c)%p=(a+(b+c)%p)%p
((a×b)%p×c)%p=(a×(b×c)%p)%p 分配率 ((a+b)%p×c)%p=((a×c)%p+(b×c)%p)%p
(a×b)%p=(a%p×b%p)%p
(a+b)%p=(a%p+b%p)%p
(a−b)%p=(a%p−b%p)%p

2.定义

有的时候我们需要对一个数取模，这很简单。但是在取模的过程中出现了除数，那么取模就没这么简单了：
72%4=3%4=3注意：7%42=32=1是错误的
但万一是7100002%4计算机可无法先计算7100002再(mod4)，因为数字太大了。
这个时候我们就需要用到乘法逆元了,事实上:7100002=(7∗3)10000。我们运用模的运算律可以通过边乘边取模即可得到答案，其中3是7在(mod4)意义下的逆元。
关于逆元的严格定义如下：
若整数b,m互质,并且b∣a，则存在整数x，使得a/b≡a∗x(modm)，则称x为b的模m乘法逆元，记为b−1(modm)

3.求解

3.1费马小定理1

因为a/b≡a∗b−1≡a/b∗b∗b−1(modm)，所以b∗b−1≡1(modm)2
如果m是质数(此时我们用符号p代替m)并且b

热门文章