被 ymh 的数学课干爆了
模运算
整数意义下的模运算
对于 \(n_1,n_2\)，我们称其在模 \(p\) 意义下相等当且仅当对于 \(n_1=k_1p+r_1\)，\(n_2=k_2p+r_2\)，其中 \(k_1,k_2,r_1,r_2\) 为整数，\(0\le r_1,r_2<p\)，满足 \(r_1=r_2\)。整数在模 \(p\) 意义下的结果指的是最小与其相等的自然数。
有理数意义下的模运算
当运算对象为整数时，运算规则应与整数意义下的模运算相同。
可以肯定，满足上面要求的有理数意义下的模运算是存在的，只不过无法写出其的定义。
实数意义下的模运算
与有理数意义下同理。
模运算与除法
不难发现，加减乘在模运算下都有十分良好的性质。下面研究除法下的性质。
如果我们能求出 \(ax\equiv 1\) 的整数解，就可以说明 \(a^{-1}\equiv x\) 了。
剩余系
类似线性基的定义，模 \(p\) 意义下的完全剩余系是一个大小为 \(p\) 的集合，对于集合中任意两个数 \(r_1,r_2\) 都不满足 \(r_1\equiv r_2(\bmod p)\)。
既约剩余系（简化剩余系）是完全剩余系的一个子集，对于其中任意 \(r_1\)，满足 \((p,r1)=1\)。
性质
若 \(\{r_0,r_1,\cdots,r_{p-1}\}\) 是 \(p\) 的一个完全剩余系，则对于 \((a,p)=1\)，满足 \(\{ar_0,ar_1,\cdots,ar_{p-1}\}\) 是 \(p\) 的一个完全剩余系。
既约剩余系有着完全一致的性质。
威尔逊定理
对于质数 \(p\)，满足 \((p-1)!\equiv -1(\bmod p)\)。该定理可逆。
证明待补。
费马小定理
对于质数 \(p\) 和 \((a,p)=1\)，满足 \(a^{p-1}\equiv 1(\bmod p)\)。
证明
构造 \(p\) 的一个不完全剩余系 \(A=\{1,2,\cdots,p-1\}\)，相应的得到 \(B=\{a,2a,\cdots,(p-1)a\}\)，这也是 \(p\) 的一个不完全剩余系。
得到 \(\prod A\equiv\prod B\)。即 \((p-1)!\equiv a^{p-1}(p-1)!\)，根据威尔逊定理，\(1\equiv a^{p-1}\)。
得证。
考虑费马小定理的两个限制，\(p\) 是质数保证了使用威尔逊定理的正确性，\((a,p)=1\) 保证构造完全剩余系的正确性。
欧拉函数
欧拉函数 \(\varphi(m)=\sum\limits_{i=1}^m[(i,m)=1]\)。
性质
case1
欧拉函数是积性函数。
证明：剩余系的复合
称 \(Z_m\) 为模 \(m\) 的完全剩余系，\(Z^{*}_m\) 为模 \(m\) 的既约剩余系。
####### 完全剩余系的复合
对于 \((m_1,m_2)=1\)，令 \(m=m_1m_2\)，则 \(Z_m=m_2Z_{m1}+m_1Z_{m2}\)，即对于每一对数 \((x,y)\) 满足 \(x\in Z_{m1}\) 且 \(y\in Z_{m2}\)，都有 \(m_1x+m_2y\in Z_m\)。同时该条件可逆。
证明待补。
####### 既约剩余系的复合
内容与完全剩余系的复合完全一致。
考虑和欧拉函数的关联，显然 \(\varphi(m)\) 就是 \(m\) 的既约剩余系的大小。因此本条结论等价于欧拉函数是积性函数。
######## 证明
令 \(m\) 的既约剩余系 \(M\) 是 \(Z_m\) 的一个子集。要求证明 \(Z^{*}_m=M\)。
分别证明充分性和必要性即可。
case2
\(n=\sum\limits_{d|n}\varphi(d)\)。
证明等学会酷炫反演魔术后再来证。
case3
令 \(p\) 是将 \(n\) 唯一分解后的质数集合，则 \(\varphi(n)=n\times\prod\limits_{i=1}^s\dfrac{p_i-1}{p_i}\)。
证明待补。
欧拉定理
对于 \((a,p)=1\)，满足 \(a^{\varphi(p)}\equiv 1(\bmod p)\)。
证明
几乎与费马小定理完全相同的套路，但是此时 \(p\) 不一定是质数，因此我们需要避开 \((p-1)!\)，选择将费马小定理证明中的完全剩余系改为既约剩余系。然后利用模运算的性质进行化简即可。
扩展欧拉定理
你先别急，让我先急。
\[a^b\equiv\begin{equation} \left\{ a^{b\bmod\varphi(m)}, \right. \end{equation}\] 标签：剩余,运算,数论,定理,varphi,证明,equiv From： https://www.cnblogs.com/BYR-KKK/p/18295081