1.模运算基本性质
基本概念：
若整数 \(a,b\) 除以 \(p\) 的余数相等，则称 \(a,b\) 在模 \(p\) 意义下同余，记作 \(a \equiv b \pmod{p}\) 或者 \(a \bmod p=b \bmod p\)。
模运算的定义：
\[a \bmod p=\begin{cases}a-p\lfloor \dfrac{a}{p}\rfloor &a\geq 0\\-(-a \bmod p) & a<0\end{cases} \]性质：
-
\((a+b) \bmod p =(a \bmod p+b \bmod p)\bmod p\)。
-
\(ab \bmod p=(a\bmod p)(b \bmod p)\bmod p\)。
-
对于任意正整数 \(k\)，有 $a \bmod p=(a \bmod kp)\bmod p $。
- Proof：考虑将 \(n\) 用 \(p,kp\) 表示，可得 \(n=xp+r_1=ykp+r_2\ (0\leq r_1<p,0\leq r_2 <kp)\)。继续将 \(r_2\) 用 \(p\) 表示，可得 \(r_2=zp+r_3\ (0\leq r_3<p)\)。命题得证。
-
若 \(k\mid a\)，则有 \(\dfrac{a}{k} \bmod p=\dfrac{a \bmod kp}{k}\)。
- 由模运算的定义可得：\[\dfrac{a\bmod kp}{k}=\dfrac{1}{k}(a-kp\lfloor \dfrac{a}{kp}\rfloor)=\dfrac{a}{k}-p\lfloor\dfrac{a}{kp}\rfloor=\dfrac{a}{k}\bmod p \]
2.逆元
分数取模
对于 \(\dfrac{a}{b}\) 这样一个分数，对它进行模运算就会比较复杂。易得 \(\dfrac{a}{b}=a \cdot \dfrac{1}{b}\)。设 \(\dfrac{1}{b}\equiv x\pmod{p}\)，则有 \(xb \equiv 1 \pmod{p}\)。找到这样一个最小的 \(x\)，就会有 \(ax \equiv \dfrac{a}{b} \pmod{p}\)。\(x\) 就是下面提到的乘法逆元。
乘法逆元
设 \(a\) 为整数，\(x\) 为正整数，若
\[ax\equiv 1\pmod{p} \]则称 \(x\) 为 \(a\) 在模 \(p\) 意义下的乘法逆元。
性质：当且仅当 \(a\perp p\) 时，\(a\) 在模 \(p\) 意义下的乘法逆元才存在。
- Proof：设 \(ax\equiv 1 \pmod{p}\)。假设 \(\gcd(a,p)=d>1\)，则有 \(ax=k_1d,p=k_2d\)。由模运算的定义得：\[ax\bmod p=(k_1d) \bmod (k_2d)=k_1d-k_2d\lfloor \dfrac{k_1d}{k_2d}\rfloor=d(k_1-\lfloor\dfrac{k_1d}{k_2d}\rfloor) \]由于 \(d>1\)，则 \(ax \bmod p\) 不可能等于 \(1\) ，假设不成立。
费马小定理
若 \(p\) 为质数，且 \(a\perp p\)，则有：
\[a^{p-1}\equiv 1 \pmod{p} \]Proof：
设数列 \(S_1=\{1,2,3\dots,p-1\}\)，将 \(S_1\) 乘 \(a\) 得 \(S_2=\{a,2a,3a\dots,(p-1)a\}\)。
将两个数列同时 \(\bmod p\) 可得 \(S_1=\{1,2,3\dots,p-1\},S_2=\{a \bmod p,2a \bmod p,3a \bmod p\dots,(p-1)a \bmod p\}\)。
设 \(a \bmod p=x\)，则 \(2a \bmod p=2x \bmod p\)。由于 \(p\) 为质数，\(2x \bmod p \ne x\Rightarrow a\bmod p \ne 2a \bmod p\)。
类似地，可得 \(3x \bmod p \ne x,3x \bmod p \ne 2x \bmod p\Rightarrow3a \bmod p\ne a \bmod p,3a \bmod p \ne 2a \bmod p\)。
以此类推，\(S_2\) 的元素间两两不等，且没有 \(0\) 出现，所以 \(S_1,S_2\) 在模 \(p\) 意义下都是 \(1\sim p-1\) 的排列。
设 \(S_1,S_2\) 中所有元素的连乘分别为 \(X,Y\)，则有：
\[\begin{aligned}X&\equiv Y \pmod{p}\\(p-1)!&\equiv a^{p-1}\cdot (p-1)! \pmod{p}\\a^{p-1}&\equiv 1\pmod{p}\end{aligned} \]由此可得，\(a\) 在模 \(p\) 意义下的乘法逆元 \(x\) 即为 \(a^{p-2}\)。
标签：pmod,dfrac,bmod,kp,ax,同余,equiv From： https://www.cnblogs.com/XP3301Pipi/p/18287553