中国剩余定理（CRT）证明与应用
问题定义
给定一组同余方程：
\[(S):\begin{cases}x≡a_1(\text{mod }m_1)\\x≡a_2(\text{mod }m_2)\\……\\x≡a_n(\text{mod }m_n)\\\end{cases} \]求解此关于 \(x\) 的方程组的最小非负整数解。同余
方程中整数\(m_1,m_2…m_n\)互质。
基本结论
设 \(M=∏_{i=1}^nm_i\) 是整数 \(m_1,m_2…m_n\) 的乘积，并设 \(M_i=\frac{M}{m_i} ,∀i∈\{x∈N^* |1≤x≤n\}\) 是除 \(m_i\) 之外的其余 \((n-1)\) 个整数的乘积。设\(t_i=m_i^{-1}\) 为 \(M_i\) 的数论倒数（对 \(m_i\) 取模意义下的逆元），即满足 \(M_i t_i=1(\text{mod }m_i ),∀i∈\{x∈N^* |1≤x≤n\}\)。
方程组 \((S)\) 的通解形式表示为：
\[x=kM+∑_{i=1}^na_it_iM_i,k∈Z \]在对 \(M\) 取模的意义下，方程组(S)存在唯一解 \(x=(∑_{i=1}^na_it_iM_i) \text{mod }M\)。
证明过程
因为问题定义中限制了整数 \(m_1,m_2…m_n\) 互质的性质，所以可得对于任何正整数 \(i∈\{x∈N^* |1≤x≤n\}\)，由于 \(∀j∈\{x∈N^* |1≤x≤n\},j≠i\)，则得到 \(gcd(m_i,m_j)=1\) ，即 \(gcd(m_i,M_i )=1\) 。
根据 \(m_i\) 与 \(M_i\) 互质的性质与逆元的存在条件，可知必然存在整数 \(t_i\) 是\(M_i\) 模 \(m_i\) 的逆元，即满足\(M_i t_i=1(\text{mod } m_i )\)。
结合上面推导出的两条结论可以进一步得到如下恒等式：
\[a_iM_it_i≡a_i(\text{mod }m_i),∀j∈\{x∈N^* |1≤x≤n\},j≠i,a_iM_it_i≡0(\text{mod } m_j) \]根据上述恒等式可以得出，对于一个正整数\(x=∑_{i=1}^na_iM_it_i\)，其必然满足如下条件：
\[∀i∈\{x∈N^* |1≤x≤n\},x=a_iM_it_i+∑_{j≠i}^na_jM_jt_j≡a_i(\text{mod }m_i) \]说明此时的 \(x\) 为方程组 \((S)\) 的一个解。由此，我们进一步假设 \(x_1,x_2\) 都是方程组 \((S)\) 的解，那么这两个数必然满足 \(∀i∈\{x∈N^* |1≤x≤n\},x_1-x_2≡0(\text{mod } m_i)\)。
又由于整数 \(m_1,m_2…m_n\) 两两互质，则 \(M|(x_1-x_2)\)，即 \(x_1，x_2\) 必然相差 \(M\) 的整数倍。而方程组 \((S)\) 特解为 \(x=∑_{i=1}^na_it_iM_i,k∈Z\)，由此可得其通解 \(x=kM+∑_{i=1}^na_it_iM_i,k∈Z\)。
扩展欧几里得算法（Exgcd）证明与应用
问题定义
给定一个不定方程 \(ax+by=\text{gcd}(a,b)\)，要求求其整数解。
基本结论
根据欧几里得算法，通过对辗转相除法过程中产生式子的收集，可以反代入原方程求出所有整数解。
具体而言，只要对原方程求解出了一组特解 \(x_0,y_0\)，就可以得到所有通解的表达式：
\[\begin{cases}x=x_0+t\frac{b}{gcd(a,b)}\\y=y_0-t\frac{b}{gcd(a,b)}\end{cases},t\in N^* \]数学证明
对于不定方程 \(ax+by=\text{gcd}(a,b)\) ①，假设先前已经求得另一个不定方程的解 \(x_1,y_1\) 满足\(bx_1+(a\text{ mod }b)y_1=\text{gcd}(a,b)\) ②，则联立 ①② ，必然可得到 \(ax+by=bx_1+(a\text{ mod }b) y_1\) ③。
由对模运算的分析我们可以知道，模运算实质是被除数与除数与商进行减法运算的过程，即 \(a \text{ mod } b=a-b[\frac{a}{b}]\)。那么 \(ax+by=bx_1+(a\text{ mod }b) y_1\) ③就可以作如下转换：
\[ax+by=bx_1+(a\text{ mod }b)y_1 \]\[⇒ax+by=bx_1+ay_1-b[\frac{a}{b}]y_1 \]\[⇒ax+by=ay_1+b(x_1-[\frac{a}{b}]y_1) \]设 \(⇒ax+by=ay_1+b(x_1-[\frac{a}{b}]y_1)\) 为④式
对比③④两式，可以得到 \(\begin{cases}x=y_1\\y=x_1-[\frac{a}{b}] y_1\end{cases}\)。当前求 \(x,y\) 的问题就转化为了求出满足 \(bx_1+(a\text{ mod }b)y_1=\text{gcd}(a,b)(2)\) 的整数解 \(x_1,y_1\)。根据最大公约数的基本性质可以知道 \(\text{gcd}(a,b)=\text{gcd}(b,a\text{ mod }b)\)，那么 \(x_1,y_1\) 所满足的 \(bx_1+(a\text{ mod }b) y_1=\text{gcd}(a,b)\) ②就可以转化为形如 \(ax+by=\text{gcd}(a,b)\) ①的不定方程，在此基础上又可以得到下一个 \(x_2,y_2\) 用于求解\(x_1,y_1\)。如此一来，这个问题的求解就成了一个具有递归性质的过程。
与传统欧几里得算法类似在这个递归过程中，方程参数a,b会被不断互相替换为 \(b,a\text{ mod }b\)，以此类推，最终必然会出现 \(a_k=\text{gcd}(a,b),b_k=0\) 的情况，此时的方程为 \(a_kx_k=\text{gcd}(a_k,b_k)\)，由于 \(b_k=0\)，所以\(\text{gcd}(a_k,b_k)=a_k\)，即 \(a_kx_k=a_k\)，此时 \(x_k=1,y_k∈R\) 。此时将 \(x_k,y_k\) 反代入上一个方程，即可最终得到特解 \(x_0,y_0\)。
乘法逆元求法概述
问题定义
乘法逆元，是指数学领域群 \(G\) 中任意元素a，都在G中有唯一的逆元 \(a'\)，使得 \(aa'=a' a=e\)，其中 \(e\) 为该群中的单位元。
简而言之，对于两个整数 \(n,p\)，使得 \(nx=1(\text{mod }p)\) 的 \(x\) 即为 \(n\) 在模 \(p\) 意义下的逆元。
基本结论
扩展欧几里得算法（Exgcd）
通过将 \(nx≡1(\text{mod }p)\) 转化为 \(nx+py=1\)，即可用扩展欧几里得算法解决（此处 \(\text{gcd}(n,p)=1\)，说明 \(n,p\) 互质）。只需要对原方程求解出了一组特解 \(x_0,y_0\)，就可以得到所有通解的表达式：
\[\begin{cases}x=x_0+t\frac{b}{gcd(a,b)}\\y=y_0-t\frac{b}{gcd(a,b)}\end{cases},t\in N^* \]费马小定理
对于整数 \(n,p\)，若 \(p\) 为质数，且 \(p∤n\)，则有 \(n^{p-1}≡1(\text{mod }p)\)，\(n\) 在对 \(p\) 取模意义下的逆元即为 \(n^{p-2}\)。
线性乘法逆元算法
对于任意一串整数中的一个数 \(n\)，其在模 \(p\) 意义下的逆元为 \(n^{-1}=\begin{cases}1(\text{mod }p),n=1\\-[\frac{p}{n}] (p\text{ mod }n)^{-1}(\text{mod }p),n≠1\end{cases}\)，此方法可以在线性时间复杂度内求解一串连续整数中每一个数在模 \(p\) 意义下的乘法逆元
数学证明
扩展欧几里得算法（Exgcd）
见上。
费马小定理
引理1：给定任意三个整数 \(a,b,c\) 和正整数 \(m\)，并且满足 \(\text{gcd}(m,c)=1\)，则当 \(ac≡bc(\text{mod }m)\)时，\(a≡b(\text{mod }m)\)。原因是由 \(ac≡bc(\text{mod }m)\) 可得 \(ac-bc≡0(\text{mod }m)\)，由于 \(m,c\) 互质，所以得到 \(a-b≡0(\text{mod }m)\)，即 \(a≡b(\text{mod }m)\)。
·引理2：一对正整数 \(m,n(m>1\text{且} \text{gcd}(m,n)=1)\)，构造模 \(m\) 的完全剩余系 \(M=\{a_1,a_2,a_3…a_m\}\)，则
\(M'=\{na_1,na_2,na_3…na_m\}\)也构成模 \(m\) 的完全剩余系。原因是若完全剩余系M中存在 \(na_i,na_j\) 模 \(m\) 同余，即 \(na_i≡na_j(\text{mod }m)\)，根据引理1则可得 \(a_i≡a_j(\text{mod }m)\)，再根据完全剩余系的定义可以知道不存在上述情况，因此不存在 \(na_i,na_j\) 模 \(m\) 同余，该引理得证。
构造模 \(p\) 的完全剩余系 \(P=\{1,2,…p\}\)，由于 \(n,p\) 互质，故由引理2可以得到 \(P'≡\{n,2n,3n…pn\}\)也构成模 \(p\) 的完全剩余系。根据完全剩余系的性质可以将上述 \(P\) 与 \(P'\) 中的所有元素分别相乘可以得到 \(1×2×3…×p≡n·2n·3n…pn(\text{mod }p)\)，即 \(p!≡n^{p-1}p!(\text{mod }p)\)，将等号两端 \(p\) 消去后即得到\(n^{p-1}≡1(\text{mod }p)\)，结论得证。
线性逆元算法
首先不难直接知道 \(1^{-1}≡1(\text{mod }p)\)。
设 \(p=kn+r(1<r<n<p)\)，此时 \(k\) 为 \(n\) 除 \(p\) 的商，\(r\) 为余数。将这个式子代入模 \(p\) 的意义下就可以得到\(kn+r≡0(\text{mod }p)\) ①。在①恒等号两端乘上 \(n^{-1},r^{-1}\)，则可以得到 \(kr^{-1}+n^{-1}≡0(\text{mod }p)\)，即 \(n^{-1}≡-kr^{-1}(\text{mod }p)\)，将 \(k,r\) 分别以 \(p=kn+r(1<r<n<p)\) 的变型式的形式表示后就得到 \(n^{-1}≡-[\frac{p}{n}] (p\text{ mod }n)^{-1}(\text{mod }p)\)。但特殊地，\(1\) 可以作为 \(1\) 模任何整数意义下的乘法逆元。结论得证。
米勒-拉宾素性测试算法证明与应用
问题定义
给定一个正整数 \(n\)，要求判断其是否为素数。
对于给定一个正整数 \(n\)，若对\(a,d,r(a,d,r∈N^* ,a,d<n,r∈[0,s-1],n-1=2^s×d)\)都满足 \(\begin{cases}a^d≠1(\text{mod }n)\\a^{2^rd}≠n-1(\text{mod }n)\end{cases}\) 中的一种情况，则可以判断 \(n\) 为合数。反之，则可以判定 \(n\) 为素数。
数学证明
根据费马小定理可知，对于一个素数 \(n\)，必然有\(a(a∈N^* )\)满足 \(a^{n-1}≡1(\text{mod }n)\)。
假设 \(n\) 是一个奇素数，那么 \(n-1\) 必然为偶数，即可以表示为 \(2^s×d(s,d∈N^* )\)的形式，那么其对于 \(a(a∈N^* )\)，必然满足\(\begin{cases}a^d≡1(\text{mod }n)\\a^{2^rd}≡n-1(\text{mod }n)\end{cases}\)。由此，结合费马小定理的内容，若我们不断对 \(n-1\) 进行开平方根的操作，则必然得到在对 \(n\) 取模意义下的 \(1\) 或 \(-1\)。也就是说，若找到任意一个\(a(a∈N^* )\)满足\(\begin{cases}a^d≠1(\text{mod }n)\\a^{2^rd}≠n-1(\text{mod }n)\end{cases}\)，那么 \(n\) 就不是一个素数，\(a\) 被称为 \(n\) 是合数的一个凭证（witness）。
但通过对部分特殊 \(n\) 的分析，可以发现并不是所有通过一次测试的 \(n\) 都是素数：对于部分合数 \(n\)，也有概率能通过上述测试，此时的 \(a\) 称为证明 \(n\) 是素数的强伪证（strong liar）。在实际算法设计中，由于无法知道 \(n\) 的所有强伪证在 \([1,n-1]\) 的具体分布，需要多次随机选取基数 \(a\) 进行测试。
注意事项
由于米勒-拉宾素性测试算法只针对奇素数，所以在实际应用中要对素数 \(2\) 进行特判。
标签：总结,专题,gcd,数论,text,逆元,na,cases,mod From： https://www.cnblogs.com/frkblog/p/16747868.html