首页 > 其他分享 >个人数论专题总结

个人数论专题总结

时间:2022-10-01 22:00:39浏览次数:51  
标签:总结 专题 gcd 数论 text 逆元 na cases mod

中国剩余定理(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

相关文章

  • docker-compose + yaml 发布系统:使用总结
    docker-compose使用总结 docker-compose+yaml发布系统:使用总结1.下载安装docker-compose下载curl-Lhttps://get.daocloud.io/docker/compose/releases/download/......
  • 数论笔记
    倍数若\(a,b,k\in\mathbbN\),且\(a\timesk=b\),那么\(b\)是\(a\)的倍数,称\(a\)整除\(b\),记作\(a\midb\)。\([1,n]\)中\(x\)的倍数有\(\left\lfl......
  • PTA题目集1~3的总结
    一、前言在新学期中我们初步学习了JAVA这门新的计算机语言,相较于之前学习的c语言,数据结构,JAVA在算法的运用上几乎相同,但又有许多差异。JAVA语言最大的特点是要构造类,并通......
  • 2022-2023-1 20221404 《计算机基础与程序设计》第5周学习总结
    2022-2023-120221404《计算机基础与程序设计》第5周学习总结作业信息班级链接(2022-2023-1-计算机基础与程序设计)作业要求(2022-2023-1计算机基础与程序设计第......
  • 窗口函数专题
    窗口函数之“最大/最小”问题,可和groupby互相改写。力扣1070:selectdistinctproduct_id,yearasfirst_year,quantity,pricefrom(select*,rank()over(......
  • 2022高联P2数论
    P2:设整数\(n(n>1)\)恰有k个互不相同的质因子,记n的所有正约数之和为\(\sigma(n)\).求证:\(\sigma(n)|(2n-k)!\).既然已给出了质因子个数和\(\sigma(n)\),那么就可设出\(n\)......
  • 2022-2023-1 20221322《计算机基础与程序设计》第五周学习总结
    作业信息这个作业属于哪个课程<班级的链接>(2022-2023-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(2022-2023-1计算机基础与程序设计第四周作业......
  • 第五周学习总结
    2022-2023-120221427《计算机基础与程序设计》第四周学习总结作业信息班级链接(2022-2023-1-计算机基础与程序设计)作业要求(2022-2023-1计算机基础与程序设计第......
  • 2022-2023-1 20221305 《计算机基础与程序设计》第五周学习总结
    教材学习内容总结了解pep/9的使用方法将汇编语言转化为机器语言学习简单的伪代码,为写程序提供基本思路了解黑盒白盒测试的原理和使用条件教材学习中的问题和解决过程......
  • 学期(如2022-2023-1) 学号(如:20221425) 《计算机基础与程序设计》第五周学习总结
    学期(如2022-2023-1)学号(如:20221425)《计算机基础与程序设计》第五周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2022-2023-1-计算机基础与程序设计)这......