NO.1 一些含义与定义
1.含义
在 \(\bmod p\) 的意义下，\(1\) 个数如果有乘法逆元 \(x\)，那么除以 \(a\) 相当于乘 \(x\)。
2.为什么要有乘法逆元
当我们求 \((a/b) \bmod p\) 的值，除法却不满足模运算的分配律，如 \(a\) 很大，可能会溢出，\(b\) 很大，可能会爆精度，乘法逆元就可以解决此问题。
3.定义
有 \(\mathbb Z^+a,n\)，如果 \(ax \equiv 1 \pmod n\)，则称 \(x\) 的最小正整数解为 \(a \bmod m\) 的乘法逆元。
4.证明
设 \(k\) 为 \(b\) 关于 \(\bmod p\) 的乘法逆元，那么 \((a/b) \bmod p=(ak) \bmod p\)，且 \(gcd(b,p)=1\)
\(∵k\) 为 \(b\) 关于 \(p\) 的乘法逆元
\(∴k/b \equiv 1 \pmod p\)
\(∴bk=px+1\)
\(∴k= \displaystyle \frac{px+1}{b}\)
\(∴ak \bmod p =(a \displaystyle \frac{px+1}{b}) \bmod p=(apx/b+a/b)\bmod p\)
\(∴((p(ax)/b) \bmod p+(a/b) \bmod p) \bmod p=(a/b) \bmod p\)
得证
鸽鸽 \(ing\)
标签：未完结,bmod,逆元,ax,px,乘法 From： https://www.cnblogs.com/firephonenix/p/16654505.html