第三章 二次剩余

⼆次剩余理论
定义：设 m 是正整数 若同余式
x2≡a(mod p), (a,p)=1
有解，则 a 叫做模 p 的⼆次剩余（或平⽅剩余）；否则，a 叫做模 p 的⼆次⾮剩余。

欧拉判别条件：
设⽅程
x2≡a(mod p), (a,p)=1,p为奇素数(i) a 是模 p 的⼆次剩余的充分必要条件是
a p−1
2≡1(mod p)
(ii) a 是模 p 的⼆次⾮剩余的充分必要条件是
a p−1
2≡−1(mod p)
并且当 a 模 p 的⼆次剩余时，同余式有两个解。

定理1：x2≡a(mod p) 中有 p−1
2 个 a 能使得⽅程有解
也就说有 p−1
2 的⼆次剩余。

例如，1，2，4是模7的⼆次剩余，-1，3，5是模4的⼆次⾮剩余。

勒让德（Lagendre）符号：
设 p 是素数，定义如下：
n
p=1,p不是n的倍数,n是p的⼆次剩余
−1,p不是n的倍数，n是p的⼆次⾮剩余（不是⼆次剩余就是⾮剩余）0,p是n的倍数
有定理1知，p−1 中有⼀半为1，⼀半为-1.
根据欧拉判别法则，设 p 是奇素数，对任意整数 a，
(a
p)≡a p−12(mod p)
⼆次互反律：若 p,q 是互素奇素数，则
(q
p)=(−1)
p−1
2⋅
q−1
2(
p
q)
参考链接：
(){ Processing math: 100%。

二次同余式的一般形式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 )。

高一竞赛数论专题 11.模为素数的二次剩余设素数2,p d >是整数,.p d Œ如果同余方程2(mod )x d p ≡有解,则称d 是模p 的二次剩余,若无解,则称d 是模p 的二次非剩余.注意到|.p d 则同余方程20(mod )x d p ≡≡,则其有且只有一解0(mod ).x m ≡若2,p =且.p d Œ则同余方程2(mod 2)x d ≡为21(mod 2)x ≡有且只有一解1(mod 2).x ≡1.设素数2p >,证明在模p 的一个既约剩余系中,恰有12p -个模p 的二次剩余,12p -个模p 的二次非剩余.此外,若d 是模p 的二次剩余,则同余方程2(mod )x d p ≡的解数为2.2.(Euler 判别法)设素数2,,p p d >Œ那么,d 是模p 的二次剩余的充要条件是121(mod );p d p -≡d 是模p的二次非剩余的充要条件是121(mod ).p d p -≡-3. 若素数2,p >证明：1-是模p 的二次剩余的充要条件是1(mod 4).p ≡当1(mod 4)p ≡时,21!1(mod ).2p p ⎛-⎫⎛⎫±≡- ⎪ ⎪⎝⎭⎝⎭4.设p 是奇素数,证明：1,2,,1p -中全体模p 的二次剩余之和12221(1).24p j p p j S p p -=⎡⎤-=-⎢⎥⎣⎦∑由此可以证明当1(mod 4)p ≡时,12221(1)(1).244p j j p p p p p p -=⎡⎤--=-⎢⎥⎣⎦∑高一竞赛数论专题 11.模为素数的二次剩余解答设素数2,p d >是整数,.p d Œ如果同余方程2(mod )x d p ≡有解,则称d 是模p 的二次剩余,若无解,则称d 是模p 的二次非剩余.注意到|.p d 则同余方程20(mod )x d p ≡≡,则其有且只有一解0(mod ).x m ≡若2,p =且.p d Œ则同余方程2(mod 2)x d ≡为21(mod 2)x ≡有且只有一解1(mod 2).x ≡1.设素数2p >,证明在模p 的一个既约剩余系中,恰有12p -个模p 的二次剩余,12p -个模p 的二次非剩余.此外,若d 是模p 的二次剩余,则同余方程2(mod )x d p ≡的解数为2.证明：取模p 的绝对最小既约剩余系1111,1,,1,1,,1,.2222p p p p ------+-- d 是模p 的二次剩余当且仅当2222221111(),(1),,(1),1,,(1),().2222p p p p d ----≡--+-- 由于22()(mod ),j j p -≡所以d 是模p 的二次剩余当且仅当222111,,(1),().22p p d --≡- 当112p i j -≤<≤时,121,10,2p i j p i j -<+<--<-<22()()0(mod ).i j i j i j p -=+-≡/ 所以222111,,(1),()22p p d --≡-给出了模p 的全部二次剩余,共有12p -个. 由于模p 的既约剩余系(简系)有1p -个数,所以另外的12p -个必为模p 的二次非剩余. 当d 是模p 的二次剩余时,必存在唯一的1,1,2p i i -≤≤使得(mod )x i p =是同余方程2(mod )x d p ≡的解,于是在模p 的绝对最小既约剩余系1111,1,,1,1,,1,.2222p p p p ------+--中有且仅有(mod )x i p =±是同余方程2(mod )x d p ≡的解,所以解数为2.2.(Euler 判别法)设素数2,,p p d >Œ那么,d 是模p 的二次剩余的充要条件是121(mod );p d p -≡d 是模p的二次非剩余的充要条件是121(mod ).p dp -≡-证明：首先来证明对任一,,d p d Œ11221(mod ),1(mod )p p d p dp --≡≡-有且仅有一个成立.由Euler 定理知道11(mod ).p dp -≡因此1122(1)(1)0(mod ).p p d dp --+-≡。

利用二次剩余判断整数的奇偶性在数论中，二次剩余是一个重要的概念，它可以帮助我们判断一个整数的奇偶性。

本文将详细介绍二次剩余的概念及其应用方法。

一、二次剩余概念的介绍二次剩余是指对于给定的正整数p和整数a，如果存在整数x满足x^2≡a(mod p)，则称a是模p的二次剩余。

如果不存在满足条件的整数x，则称a是模p的二次非剩余。

二、判断整数奇偶性的方法利用二次剩余可以判断一个整数的奇偶性。

具体步骤如下：1. 若p是奇素数，a是自然数，则a是模p的二次剩余的充要条件是a^((p-1)/2)≡1(mod p)。

2. 若p是奇素数，a是自然数，则a是模p的二次非剩余的充要条件是a^((p-1)/2)≡-1(mod p)。

三、应用举例以一个具体的例子来说明如何利用二次剩余判断整数的奇偶性。

假设我们要判断整数5的奇偶性，我们可以利用模7的二次剩余来进行判断。

根据上述方法，计算得到5^3≡-1(mod 7)。

由此可知，5是模7的二次非剩余，即5是奇数。

四、注意事项在使用二次剩余判断整数的奇偶性时，需要注意以下几点：1. 二次剩余的应用范围主要是奇素数p，对于偶数或合数，不适用。

2. 在应用二次剩余进行判断时，需先判断给定的整数是否满足条件，即是否为自然数、素数等。

五、总结通过利用二次剩余的概念，我们可以判断一个整数的奇偶性。

通过计算模p的二次剩余，我们可以得到结论，进而对整数进行分类。

然而，在使用二次剩余时，需要注意条件的限制，以及选择合适的素数p 进行判断。

六、结语本文简要介绍了利用二次剩余来判断整数奇偶性的方法。

通过对二次剩余的概念和应用进行详细说明，希望读者能够更好地理解和应用这一数论中的重要概念。

同时，在具体应用中需要根据实际情况选择适当的素数p进行判断，提高判断的准确性和可靠性。

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

【关键词】二次剩余；二次同余式；勒让德符号；二次反转定律引言数论是数学本科的基础课程之一，是学习数学的必修课程之一。

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

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

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

1．一般二次同余式二次同余式最基本的形式：我们知道，解同余式(1)归结到m为素数的情形，因为m=2时，解同余式(1)变得极为容易，所以着重讨论m=p的情形，这里p是一个奇素数。

定义1：设m &gt;1，若(1)有解，则a叫做模m的二次剩余；若无解，则a叫做模m的二次非利余。

2．单质数的二次剩余的判定2.1欧拉判别条件。

讨论p是单质数的二次剩余和二次非剩余，即讨论形如：x-21 ,53,-21,-53(mod 64)是所求的四个解。

结论二次剩余的判定问题等价于判断一般二次同余式X2 -a( mod p)，(a，p) =1是否有解的问题。

而当p取不同的数时，解决问题的方法不同。

本文针对不同情况，运用了不同的方法，从而更简便地得出判断结果。

单质数的二次剩余判定可以利用欧拉判别条件，勒让德符号和二次反转定律，合数模的二次剩余也可以转化成单质数的二次剩余进行判定。