二次剩余的判定及应用

二次剩余理论试题及答案1、已知素数p 判别同余方程x 2≡a(mod p)是否有解。

即计算⎪⎪⎭⎫ ⎝⎛p a =1或-1 。

2、已知a ，求所有使及⎪⎪⎭⎫ ⎝⎛p a =1或⎪⎪⎭⎫ ⎝⎛p a =-1的p 的一般形式。

3、在⎪⎪⎭⎫ ⎝⎛p a =1的条件下，如何求出x 2≡a(mod p)的解。

若x 1为一个解，则另一个解为-x 1 。

上述已叙述了问题（1）、（2），现在只剩下解（3）解的方法。

除了书上介绍的公方法，我们再补充另一个方法即高斯逐步淘汰法。

补充知识高斯逐步淘汰法：首先，不妨设因解同余方程x 2=a+py ，故， 因而在求y 的值时，不必考虑大于4p的整数，这就大大缩小了讨论的范围。

其次，任取素数q ≠p ，求出q 的平方非剩余为a 1 ,a 2……a s 并以v 1 ,v 2,……v s 表示同余方程a+py ≡a 1 (mod q) ,a+py ≡a 2(mod q)，……a+py ≡a s (mod q)的解，由于平方数一定为任何模的平方剩余，故若取y ≡v i (mod q)，则a+py 是q 的平方非剩余，因而a+py 一定不是平方数。

而不能有x 2=a+py 这样可淘汰满足y ≡v i (mod g)的各个y 的值。

取不同的q ，淘汰y 的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）的解。

例：解同余方程x 2≡73(mod137)解 ∵ ⎪⎭⎫⎝⎛13773=1，∴x 2≡73(mod137)有二个解因为p=137，故0<y ≤34取q=3，则2为3一平方非剩余。

解同余方程 73+137y ≡3(mod3)得y ≡2(mod 3)，从不大于34的正整数中淘汰形如y=2+3t 的数，即有下面 1，3，4，6，7，9，10，12，13，15，16，18，19，21，22，24，25，27，28，30，31，33，34。

再取q=5，2，3为g 的平方非剩余的同余方程73+137y ≡2(mod5) ，73+137y ≡3(mod5)解为y ≡2(mod5) ,y ≡0(mod5)，再从前面的数中淘汰形如y=2+5t 和y=5t ，有下面1，3，4，6，9，13，16，18，19，21，24，28，31，33，34。

二次同余式的一般形式ax2＋bx＋c≡0(mod m)由算术基本定理知道m可以分解成一些素数乘积,再由孙子定理知道ax2＋bx＋c≡0(mod m)可以转化为同余式组ax2＋bx＋c≡0(mod pα)因此,本章只讨论模为素数幂pα的同余式设p是素数，我们来研究素数模p的二次同余方程ax2+bx+c≡0 (mod p)。

(1)如果p= 2，则可以直接验证x≡0或1 (mod 2)是否方程(1)的解。

如果(a, p) = p，则方程(1)成为一元一次同余方程。

因此，只需考察p > 2，(a, p) = 1的情形。

此时，因为(4a, p) = 1，所以，方程(1)等价于方程4a2x2+4abx+4ac≡0 (mod p)，即(2ax+b)2≡b2-4ac(mod p)。

这样，研究方程(1)归结为对方程x2≡a(mod m) (2)定义１给定整数m，对于任意的整数a，(a，m) = 1，若方程x2 a(mod m)有解，则称a是模m的二次剩余；否则，称a是模m的二次非剩余.例1验证1是模4的平方剩余,‐1是是模4的非平方剩余 例21,2,4 是模7的平方剩余,‐1,3,5是模7的非平方剩余解因为,12≡1, 22≡4, 32≡2, 42≡2，52≡4，62≡1（mod7），例3 求满足方程E:y2≡x3+x+1(mod 7)的所有点 解x ≡0, y2 ≡1(mod 7) y ≡1,6 (mod 7)x ≡1, y2 ≡3(mod 7) 无解x ≡2, y2 ≡4(mod 7) y ≡2,5 (mod 7)x ≡3, y2 ≡3(mod 7) 无解x ≡4, y2 ≡6(mod 7) 无解x ≡5, y2 ≡5(mod 7) 无解x ≡36, y2 ≡6(mod 7) 无解4.2模为奇素数的平方剩余与非平方剩余 在这节里讨论模为素数的二次同余式定理１(欧拉判别条件) 若(a , p ) = 1，p 是奇素数则 (ⅰ) a 是模p 的二次剩余的充要条件是≡1 (mod p )；(3) (ⅱ) 若a 是模p 的二次剩余，则方程(2)有两个解； (ⅲ) a 是模p 的二次非剩余的充要条件是 ≡-1 (mod p )。

数学中的整数论数学中的整数论是数论的一个重要分支，研究关于整数的性质和其在代数、几何等方面的应用。

整数论广泛应用于密码学、编码理论、算法设计以及计算机科学等领域，对于理解数字的性质和解决实际问题具有重要意义。

一、素数与因子分解素数是整数论中的基础概念。

素数是只能被1和自身整除的自然数，如2、3、5、7等。

整数可以唯一地表示为素数的乘积，这就是因子分解定理的基本思想。

例如，120可以分解为2^3 × 3 × 5，其中2、3和5都是素数。

二、最大公约数与最小公倍数最大公约数（GCD）和最小公倍数（LCM）是整数论中常见的概念。

对于给定的两个整数，它们的最大公约数是能够同时整除这两个整数的最大自然数，而最小公倍数是能够同时被这两个整数整除的最小自然数。

最大公约数和最小公倍数在求解分数的最简形式、解方程以及进行模运算等方面起着重要的作用。

三、同余与模运算同余是整数论中研究的重要概念之一。

对于给定的整数a、b和正整数m，如果a与b除以m得到的余数相同，则称a与b关于模m同余，记作a ≡ b (mod m)。

同余关系在密码学和编码理论中有广泛的应用，例如RSA算法中的大数素性测试以及多项式哈希函数的构造等。

四、费马小定理与欧拉定理费马小定理是整数论中的重要结论之一，它指出对于任意素数p和整数a，若a不是p的倍数，则a^(p-1) ≡ 1 (mod p)。

费马小定理在密码学中的应用十分广泛，特别是RSA算法的关键步骤之一。

欧拉定理是对费马小定理的推广，它指出对于任意正整数n和整数a，如果a与n 互质（即它们的最大公约数为1），则a^φ(n) ≡ 1 (mod n)，其中φ(n)表示小于等于n且与n互质的正整数的个数。

五、二次剩余与勒让德符号二次剩余是整数论中的一个重要概念，它涉及到整数平方剩余的性质。

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

二次剩余及其应用一、二次剩余的定义：正整数m>1，n∈Z，(m,n)=1，若存在x∈Z，使得x2≡n(mod m)，则称n为模m的二次剩余。

否则，称为二次非剩余。

勒让德(Legendre)符号：设p为奇素数，a∈Z且(a,p)=1，定义：(ap )={1，若a为p的二次剩余−1，若a为p的二次非剩余，称为勒让德符号。

当a≡b(mod p)时，显然(ap )=(bp)。

例1、证明具有下列形式的素数有无穷多个.（1）8k+3（2）8k+5（3）8k+7例2、求有序整数对(a,b)的个数，使得x2+ax+b=167y有整数解(x,y)，其中1≤a、b≤2004.二、 与素数的二次剩余相关的定理：定理1、设p 为奇素数，模p 的缩系中有p−12个二次剩余，有有p−12个二次非剩余。

且12、22、⋯、(p−12)2即为其p−12个二次剩余。

定理2、设p 为奇素数，a ∈Z 且(a,p )=1，则(p −1)!≡−(ap)ap−1(mod p)。

定理3（欧拉(Euler)判别条件）、设p 为奇素数，a ∈Z 且(a,p )=1，a p−1则≡(ap)(mod p)。

定理4、设p 为奇素数，则(−1p )≡(−1)p−1(mod p)。

即当p ≡1(mod 4)时，-1为p 的二次剩余；当p ≡3(mod 4)时，-1为p 的二次非剩余。

例3、 已知pqr 均为素数，n 为正整数，p n +q n =r 2，求证：n=1.例4、 若p 为奇素数，证明：当且仅当p ≡1(mod 4)时，p 可以表示成两个非零完全平方数之和，且表示方法唯一.三、二次互反律定理5(高斯(Gause)引理)、设p 为奇素数，a ∈Z 且(a,p )=1，若a 、2a 、⋯、p−12a 关于模p 的最小正余数中有μ个大于p 2，则(ap )=(−1)μ。

定理6、设p 为奇素数，(2p )=(−1)p 2−1。

即当p ≡±1(mod 8)时，2为p 的二次剩余；当p ≡±3(mod 8)时，2为p 的二次非剩余。