第五讲 二次剩余

二次剩余反演公式首先，我们来回顾一下二次剩余的概念。

对于给定的正整数n和整数a，如果存在整数x满足x^2≡a(mod n)，则称a是关于模n的一个二次剩余。

可以看出，如果a是一个二次剩余，则a的每个剩余类都是一个二次剩余。

反之，如果a不是一个二次剩余，则a的每个剩余类都不是一个二次剩余。

现在，我们来讨论二次剩余反演公式的原理。

设p是一个奇素数，a是一个整数，p不整除a。

根据费马小定理，p为奇素数时，a^(p-1)≡1(mod p)。

由此可以得到以下结论：(1) 如果a是p的一个二次剩余，则存在整数b满足b^2≡a(mod p)。

那么，a^((p-1)/2)≡b^(p-1)≡1(mod p)。

(2) 如果a不是p的一个二次剩余，则a^((p-1)/2)≡(-1)(mod p)。

根据勒让德符号的定义，可以得到以下关系：(1)如果a是p的一个二次剩余，则(a/p)=1(2)如果a不是p的一个二次剩余，则(a/p)=-1现在，我们可以叙述二次剩余反演公式的基本形式。

设p是一个奇素数，a是一个整数，p不整除a。

那么，我们可以得到以下等式：\sum_{x=0}^{p-1} (a/p)^(x^2) = (a/p)^(p-1)。

这个公式的证明需要使用因子分解和费马小定理的性质，这里我们不再详述。

二次剩余反演公式的应用非常广泛。

它可以用于求解一些特定形式的整数解方程和模方程。

例如，如果我们要求解关于模p的方程x^2≡a(mod p)，其中p为奇素数，a为整数，p不整除a，我们可以利用二次剩余反演公式来求解。

具体的求解方法如下所示。

首先，我们根据二次剩余的定义，判断a是否是p的一个二次剩余。

如果a是一个二次剩余，则根据二次剩余反演公式，方程的解个数为(p+1)/2、如果a不是一个二次剩余，则方程无解。

在实际求解中，我们可以利用勒让德符号的计算公式来判断a是否是一个二次剩余。

另外，二次剩余反演公式还可以用于研究模方程的解的性质和分布情况。

数论-⼆次剩余、欧拉判别准则、⾼斯引理定义：∀ n,m ,(n,m)=1,m≥2，若n是模m的⼆次剩余《==》x**2 ≡ n (mod m)有解例：若n=2,m=3，x**2 ≡ 2 (mod 3)⽆解，则2是模3的⼆次⾮剩余若n=2,m=7，x**2 ≡ 2 (mod 7)在x=3时成⽴，有解，故2是模7的⼆次剩余Th1:在模p(奇素数)的缩系{1,2,3,...,p-1}中，有(p-1)/2个⼆次剩余和(p-1)/2个⼆次⾮剩余，且其中⼆次剩余为A:{<1>,<2**2>,...,<((p-1)/2)**2>}证明：（A中元素两两不同）假设∃i,j i≠j ,1≤i≤(p-1)/2有<i**2> ≡ <j**2>故<i**2> ≡ i**2 (mod p)<j**2> ≡ j**2 (mod p)∴i**2 ≡ j**2 (mod p)∴p|(i**2-j**2)即p | (i+j)*(i-j)∵2<i+j<p-1∴p|i-j,故p≤|i-j|∵|i-j|<(p-1)/2∴假设所得结果与事实不成⽴，故A中元素两两不同（A中每个元素是模p的⼆次剩余）∀ <i**2> ∈A ,<i**2> ≡ i**2 (mod A)∴∃x=i,有x**2≡ <i**2> (mod p)故A中的每个元素是模p的⼆次剩余（n∈{1,2,...,p-1}(模p的缩系)是模p的⼆次剩余，则n∈A）∃ x,有x**2 ≡ n (mod p)∴(p-x)**2 ≡ n (mod p)若x≥(p-1)/2+1,(p-x)≥(p-1)/2+1，则p≥p+1,但p<p+1,故p-x和x中有⼀个≤(p-1)/2,⼀个≥(p-1)/2+1∴n ≡ x**2 (mod p) (或者n ≡ (p-x)**2 (mod p))∵x≤(p-1)/2(或p-x≤(p-1)/2)故n∈A,即A中每个元素是模p的⼆次剩余，得证Th2:(欧拉判别准则）---------------------------------------------引⼊勒让德符号：(n/p),其中①(n/p)=1 --> n是p的⼆次剩余②(n/p)≠1 --> n是p的⼆次⾮剩余--------------------------------------------①若(n/p)=1，则n**((p-1)/2) ≡ 1 (mod p)②若(n/p)=-1，则n**((p-1)/2) ≡ -1 (mod p)证明：（(n/p)=1 => n**((p-1)/2) ≡ 1 (mod p)）∵(n/p)=1故∃ x,有 x**2 ≡ n (mod p)∵(x,p)=1，故x**(p-1) ≡ 1 (mod p)故(x**2)**((p-1)/2) ≡ n**(p-1)/2 (mod p)即n**((p-1)/2）≡ 1 (mod p)（ n**((p-1)/2) ≡ 1 (mod p) => （n/p）=1）∵n**((p-1)/2) ≡ 1 (mod p)，且1 ≠ 0 (mod p)根据拉格朗⽇定理，可知对于同余式，解数≤(p-1)/2⼜∵对于集合A={<1>,<2**2>,...,<((p-1)/2)**2>}取i∈A,则有(<i**2>)**(p-1)/2 ≡ (i**2)**(p-1)/2 ≡ i**(p-1) ≡ 1 (mod p)∴A中元素为同余式n**((p-1)/2) ≡ 1 (mod p)的解⼜∵A中元素恰为(p-1)/2个∴A中元素就是同余式n**((p-1)/2) ≡ 1 (mod p)的解，也就是说n的取值在集合A中∴(n/p)=1若(n/p)=-1，则(n/p)≠1∴n**(p-1)/2 ≠ 1 (mod p)∵(n,p)=1 ∴n**(p-1) ≡ 1 (mod p)∴(n**(p-1)/2)**2 ≡ 1(mod p)∴((n**(p-1)/2)**2)-1 ≡ 0 (mod p)∴p | (n**(p-1)/2)**2-1 即p | ((n**(p-1)/2)+1)*((n**(p-1)/2)-1)∵n**(p-1)/2 ≠ 1 (mod p) ∴ p | (n**(p-1)/2)+1 即 (n**(p-1)/2) ≡ -1 (mod p)得证，综上所述，n**(p-1)/2 ≡ (n/p) (mod p)推论：若p 不整除于 m*n,则((m*n)/p)=(m/p)*(n/p)证明：(m/p)=m**(p-1)/2 (mod p)(n/p)=n**(p-1)/2 (mod p)故(m/p)*(n/p)=m**(p-1)/2 * n**(p-1)/2 (mod p)= (m*n)**((p-1)/2) (mod p)=((m*n)/p) (mod p),得证⾼斯引理：若(p,n)=1,<1*n><2*n>,...,<(p-1)/2*n>中有m个数>p/2,则(n/p)=(-1)**m证明：设集合A={<1*n>,<2*n>,...,<(p-1)/2*n>}={a1,a2,...,al,b1,b2,...,bm}，其中1≤ai<p/2, bj>p/2,l+m=p-1,A∈{1,2,...,p-1}则p-bj≠ ai (mod p)(证明p-bj≠ ai (mod p):p/2<bj<p-1<p故0<bj<p/2，即1≤p-bj<p/2若p-bj ≡ ai (mod p),则ai+bj≡ 0 (mod p)∴∃ x,y，有<x*n>+<y*n> ≡ 0 (mod p)即<n*(x+y)> ≡ 0 (mod p)∵x,y∈[1,p-1/2]∴x+y∈[2,p-1]∴(<x+y>,p)=1∵(n,p)=1，故<n*(x+y)> ≠ 0 (mod p)与<n*(x+y)> ≡ 0 (mod p)，故不存在这样的x,y使得p-bj ≡ ai (mod p)成⽴∴p-bj≠ ai (mod p))∴{a1,a2,...,al,p-b1,p-b2,...,p-bk}={1,2,...,(p-1)/2}(模p的⼆次剩余集合)∴∏ai*∏(p-bj)=((p-1)/2)!∵ai,bj∈{<1*n><2*n>,...,<(p-1)/2*n>},故∏ai*∏(p-bj) = [1*2*...*((p-1)/2)]*[(-1)**(m)]*[n**(p-1)/2] ≡ ((p-1)/2)! (mod p)即 [(-1)**(m)]*[n**(p-1)/2] ≡ 1 (mod p)∵[n**(p-1)/2] ≡ (n/p) (mod p)∴ [(-1)**(m)]*[n**(p-1)/2] =(n/p)*(-1)**(m) ≡ 1 (mod p)∴(n/p)≡(-1)**(m) (mod p)得证。

第五章 二次同余式与平方剩余本章的目的是较深入地讨论二次同余式。

讨论方法是把问题归结到讨论形如)(mo d 2m a x ≡的同余式，进而引入平方剩余和平方非剩余的概念，再应用数论中常用的函数(勒让德符号及雅可比符号)去讨论m 是单质数的情形，进而讨论一般的情形。

最后还应用本章结果解决两个不定方程的问题，并介绍一下与它们有关的著名的华林问题。

教学内容: 1.一般二次同余式教学目的: 了解一般二次同余式及平方剩余，平方非剩余的概念： 教学重难点: 平方剩余的概念 教学过程:本节主要讨论二次同余式，讨论方法是把问题归结到讨论形如)(mod 2m a x ≡的同余式，进而引入平方剩余和平方非剩余的概念，再应用数论中常用的函数讨论m 是单质数的情形，进而讨论一般的情形： 一． 基本概念： 首先：二次同余式的一般形式：)(m od 0),(m od 02m a m c bx ax ≡/≡++（1） 用4a 乘（1）式再加上2b 得：acb b ax am ac b b abx x a 4)2()4(mod 444222222-≡+-≡++即若令ac b D b ax y 4,22-=+=则上式变为)4(mod 2am D y ≡（2）具体分析过程见书上P74:由同于是的性质可知（2）与（1）式同时有解或同时误解：故讨论（1）式有解的问题可以转为讨论（2）式有解的问题：为了讨论（2）式是否有解，我们引入平方剩余和平方非剩余的概念：定义：假设（a,m ）=1，如果同余式)(mod 2m a x ≡有解，则a 叫做模m 的平方剩余，否则叫做模m 的平方非剩余：例：)7(m od 2a x ≡根据同余式解的形式：他的接有0，1，2，3，4，5，6这7中可能，而a 有1，2，3，4，5，6这六种可能，严整可知 当a 取1，2，4是有解，当a 取3，5，6时误解，故1，2，4为模7的平方剩余，而3，5，6为模7的平方非剩余：教学内容: 2.单质数的平方剩余与平方非剩余教学目的: 了解单质数的平方剩余，平方非剩余的基本性质及判别方法： 教学重难点: 平方剩余，平方非剩余的判别 教学过程:这节我们讨论单质数p 的平方剩余，平方非剩余： 一． 判别方法： 定理1：（欧拉判别条件）：若（a,p ）=1，则a 是模p 的平方剩余的充要条件是：)(mod 121p ap ≡-：而a 是模p 的平方非剩余的充要条件是：)(mod 121p ap -≡-证明：见书上P76：由此定理我们就可以判别单质数p 的平方剩余，平方非剩余： 二．基本性质：定理2：模p 的平方剩余和平方非剩余各为21-p ，而且21-p 个平方剩余分别与序列)21(2,122-p 中之一数同余，且仅与一数同余： 证明：见书上P77：关于平方剩余和平方非剩余具有以下性质： 定理3：对于同一素数p 来说： 1． 二平方剩余之积仍是平方剩余：2． 一平方剩余与一平方非剩余之积为平方非剩余： 3． 二平方非剩余之积为平方剩余：证明：1。

浅谈⼆次剩余——求解⼆次同余⽅程1.⼆次同余式⼆次同余式是关于未知数的⼆次多项式的同余⽅程。

即：是⼀个⼆次同余⽅程。

此外，称为最简⼆次同余式，或称最简⼆次同余⽅程。

⼀般的，通过配⽅，可以把⼀个⼀般的⼆次同余⽅程转化为⼀个最简⼆次同余式接下来只需要讨论最简⼆次同余式。

2⼆次剩余2.1 前置概念、定理即证明：若⽆特殊说明，下⾯的模运算都是在模p的意义下1.有正整数n，奇质数p，且p∤n，若存在⼀个正整数x，使得x2≡n(mod则称n为p的⼆次剩余。

2.勒让德符号\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}，若n为p的⼆次剩余，则该值为1，若不是则该值为-1，若p\mid n，则该值为0定理1：\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}\equiv n^{\frac{p-1}{2}}证明：1.若p能整除n，那右边明显模p与0同余，故成⽴。

2.若n是p的⼆次剩余，则根据费马⼩定理(n^{p-1}\equiv1(\bmod p)其中，p为质数)，有n^{\frac{p-1}{2}} = {\sqrt{n}^{p-1}}\equiv 1，故成⽴3.若n不是p的⼆次剩余，则根据扩展欧⼏⾥得算法，对于i\in[1,p-1]都有唯⼀的j\in[1,p-1],i\neq j且ij\equiv n这样的数⼀共有\frac{p-1}{2}个，因此\frac{p-1} {2}\equiv (p-1)!根据威尔逊定理)(：当且仅当p为素数时有：( p -1 )! \equiv -1 ( \bmod p ))，就有\frac{p-1}{2}\equiv -1证毕威尔逊定理证明：我们知道1\times1\equiv 1(mod p),( − 1 ) \times ( − 1 )\equiv (mod p)，且仅有这两组的逆元与本⾝相等。

如果x^2\equiv 1(\bmod p)那么通过移项再因式分解可以得到x=-1或x=1，除了1，-1这两个数之外，2⾄p-2中的每⼀个数都⼀定有⼀个对应的逆元（注明：-1\equiv p-1(\bmod p)）且⼀定与⾃⼰不相等，且每⼀个数与他的逆元⼀⼀对应。

第5章 二次同余方程与平方剩余内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 5.1 一般二次同余方程（一） 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ）） （1）（二） 化简设m ＝k kp p p αααΛ2121，则方程（1）等价于同余方程组 ⇒ 2ax ＋bx ＋c ≡0（mod αp ）， （pa ） （2）（三） 化为标准形式p ≠2，方程（2）两边同乘以4a ， 422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （modαp ）变量代换， y ＝2ax ＋b （3）有2y ≡2b －4ac （mod αp ） （4） 当p 为奇素数时，方程（4）与（2）等价。

即两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p ,2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

两者解数相同。

结论：只须讨论方程 2x ≡a （mod αp ） （5）【例5.1.1】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））（四） 平方剩余【定义5.1.1】设m 是正整数，a 是整数，m a 。

二次剩余反演公式(一)
二次剩余反演公式
什么是二次剩余反演公式？
二次剩余反演公式是一种用于求解二次剩余方程的数学公式。

在数论和密码学中，二次剩余反演公式起到了重要的作用。

它通过将二次剩余方程转化为其他数学问题的求解，从而简化了计算过程。

二次剩余方程公式
二次剩余方程公式可以表示为：
x^2 ≡ a (mod p)
其中，p是一个素数，a是一个整数，x是未知数。

二次剩余反演公式
二次剩余反演公式可以表示为：
x ≡ a^((p+1)/4) (mod p)
其中，p是一个素数，a是一个二次剩余数，x是满足x^2 ≡ a (mod p)的正整数解。

举例说明
假设我们要求解二次剩余方程x^2 ≡ 5 (mod 11)，基于二次剩余反演公式，我们可以得到：
x ≡ 5^((11+1)/4) (mod 11)
计算公式右侧的指数部分：
(11+1)/4 = 3
此时，我们可得到：
x ≡ 5^3 (mod 11)
继续计算：
5^3 = 125
将125除以11得到的余数是3，因此：
x ≡ 3 (mod 11)
所以，该二次剩余方程的解为x ≡ 3 (mod 11)。

结论
通过二次剩余反演公式，我们可以在一定条件下求解二次剩余方程。

它在数论和密码学领域中具有重要的应用价值。

通过简化计算过程，二次剩余反演公式帮助我们更高效地解决二次剩余问题。

第5章 二次同余方程与平方剩余内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 5.1 一般二次同余方程（一） 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ）） （1）（二） 化简设m ＝k kp p p ααα 2121，则方程（1）等价于同余方程组 ⎪⎪⎩⎪⎪⎨⎧≡++≡++≡++）（）（）（k k p c bx ax p c bx ax p c bx ax αααmod 0mod 0mod 02221221⇒ 2ax ＋bx ＋c ≡0（mod αp ）， （pa ） （2）（三） 化为标准形式p ≠2，方程（2）两边同乘以4a ， 422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （modαp ）变量代换， y ＝2ax ＋b （3）有2y ≡2b －4ac （mod αp ） （4）当p 为奇素数时，方程（4）与（2）等价。

即● 两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p , 2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

● 两者解数相同。

结论：只须讨论方程 2x ≡a （mod αp ） （5）【例5.1.1】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））（四） 平方剩余【定义5.1.1】设m 是正整数，a 是整数，m a 。

二次剩余的判定及应用【摘要】通过讨论形式如x2≡a（mod m）的同余式，引出二次剩余的概念，应用数论中常用的函数（勒让德符号和雅可比符号）去讨论二次同余式中m是单质数的情形和一般的情形，并利用其解二次同余式。

【Abstract】Through the discussion form like x2≡a （mod m）congruence type，leads to second remaining concept，application of the general functions （theory，Legendre symbols and Jacobi symbols）to discuss the second congruence type in the number of elemental m is condition and the general situation，this paper briefly introduces solutions second congruence type equations.【Key words】Second remaining；second congruence type equations；Legendre symbols；Second reverse law引言数论是数学本科的基础课程之一，是学习数学的必修课程之一。

数论问题的丰富性，多样性及解题所具有的高度技巧对培养灵活创新的思维品质，逻辑思维，发散思维能力，系统的掌握各种数学思维，都是必不可少的。

本文针对数论中一般二次同余式的解法问题进行总结概括。

为了找到更为简单，有效地解一般二次同余式的方法，主要通叙述定理和举例，总结说明了欧拉判别条件，勒让德符号在解一般二次同余式时的具体应用以及一般二次同余式的解和解数问题。

1. 一般二次同余式二次同余式最基本的形式：（1）x2≡a（mod m），（a，m）=1二次剩余。