下载文档原格式
初等数论第五章二次同余式与平方剩余第五章二次同余式与平方剩余第五章二次同余式与平方剩余§1二次同余式与平方剩余二次同余式的一般形式是ax2?bx?c?0(modm)，a??0(modm)(1)下面讨论它的解的情况。
?k?1?2令m?p1p2?pk，则(1)有解的充要条件为ax2?bx?c?0(modpi?i)，i?1,2,?,k有解，而解f(x)?ax2?bx?c?0(modp?)，p为质数(2)又可以归结为解f(x)?ax2?bx?c?0(modp)，p为质数(3)。
当p?2时，同余式(3)极易求解，因此，我们只需讨论二次同余式f(x)?ax2?bx?c?0(modp)，p为奇质数(4)若p?|a，用4a乘(4)再配方得(2ax?b)2?4ac?b2?0(modp)，令y?2ax?b,A?b2?4ac，得y2?A?0(modp)可以证明：同余式(4)和(5)是等价的。
证明必要性显然；反之，设(5)有一解y?y0，因为(p,2a)?1，所以2ax?b?y0(modp)有解，即(4)有解。
以上讨论可知，二次同余式可以化为x2?a(modp)，p为奇质数(6)(5)来求解，当p|a时，(6)仅有一个解x?0(modp)，所以我们下面总假定p?|a或(p,a)?1。
因此，下面主要研究形如x2?a(modp)，(p,a)?1，p为奇质数同余式。
(7)的定义若同余式x2?a(modp),(a,p)?1,p为奇质数有解，则a 叫做模p的平方剩余(二次剩余)，若无解，则a叫做模p的平方非剩余(二次非剩余)。
定理1(欧拉判别条件)若(a,p)?1，则a是模p的平方剩余的充要条件为ap?12?1(modp)；a是模p的平方非剩余的充要条件为a- 1 - p?12??1(modp)。
若a是模p的平方剩余，则(7)式恰有两解。
第五章二次同余式与平方剩余证明(1)设a是模p 的平方剩余，则同余式x2?a(modp)，(a,p)?1有解，设为?，于是??a(modp)，从而欧拉定理可知反之，若ap?122ap?12??p?1?1(modp)。
第 5 章 原根与指标（一） 内容● 指数 ● 原根● 有原根的整数 ● 指标（对数）（二） 重点● 原根及其意义 ● 有原根的整数的条件 ● 指标及其性质5.1 指数及其基本性质准备知识：（1） 欧拉定理：m ＞1，(a,m)＝1，则()m a ϕ≡1（mod m ）（2） 问题：①()m ϕ是否是使得上式成立的最小正整数？ ②该最小正整数有何性质？ (一) 指数和原根概念【定义5.1.1】（定义1）设m ＞1，(a,m)＝1，则使得e a ≡1（mod m ）成立的最小正整数e 叫做a 对模m 的指数（或阶），记作m ord (a)。
若a 的指数e ＝()m ϕ，则a 叫做模m 的原根。
(二) Diffie —Hellman 密钥交换算法全局公开量q 素数α q 的原根（α<q ）交换公开密钥 A →B ： A Y B →A ： B Y例如：● 素数q ＝353，原根α＝3● A 选 A X ＝97， 计算A Y ≡973≡40 mod 353 ● B 选 B X ＝233， 计算B Y ≡2333≡248 mod 353 ● A 与B 交换● A 计算密钥 K ≡97248≡160 mod 353 ● B 计算密钥 K ≡23340≡160 mod 353(三) 用定义求指数和原根【例1】（按定义求指数和原根）（例1）m ＝7，则ϕ(7)＝6。
且11≡1，32≡1，63≡1，34≡1，65≡1，26≡1（mod 7）故对模数7而言，1，2，3，4，5，6的指数分别为1，3，6，3，6，2。
列表表示为因此，3，【例2】（快速求指数）（例2）m ＝14＝2·7， ϕ(14)＝6，则11≡1，33≡－1，35≡－1，39≡1，311≡1，213≡1（mod7）列表故3，5【例3】（无原根的整数）（例3）m ＝15＝3·5， ϕ(15)＝8，则同理，可知模数m ＝9时，其原根为2，5；而整数8则没有原根。
二次同余式的解法一、什么是二次同余式二次同余式是指形如ax2+bx+c≡0(mod m)的同余方程，其中a,b,c,m是给定的整数，x是未知数，≡表示模同余。
二、二次同余式的解法解二次同余式的一种常用方法是通过模平方根的性质。
下面介绍二次同余式的两种解法：平方剩余和二次非剩余。
2.1 平方剩余如果存在一个整数x，使得x2≡c(mod m)，则称c是模m的平方剩余。
我们可以通过以下步骤求解二次同余式：1.计算模m的平方剩余集合{02,12,22,…,(m−1)2}。
2.判断c是否在平方剩余集合中。
–如果在集合中，即存在x满足x2≡c(mod m)，则可以得到两个解：x≡±√c(mod m)。
–如果不在集合中，则二次同余式无解。
2.2 二次非剩余如果不存在一个整数x，使得x2≡c(mod m)，则称c是模m的二次非剩余。
解决二次同余式的方法如下：1.计算模m的平方剩余集合{02,12,22,…,(m−1)2}。
2.判断c是否在平方剩余集合中。
–如果在集合中，则二次同余式无解。
–如果不在集合中，可以通过以下步骤求解二次同余式：1.找到一个整数y，使得y2≡c⋅a(mod m)，其中a是模m的一个非平方剩余。
2.利用模m的平方剩余集合求解y的平方根。
3.根据平方根的性质，可以得到两个解：x≡±y(mod m)。
2.3 例子假设我们要解决二次同余式3x2+5x+2≡0(mod11)。
按照上述方法，我们可以进行如下步骤：1.计算模11的平方剩余集合：{02,12,22,…,102}={0,1,4,9,5,3,3,5,9,4,1}。
2.判断2是否在平方剩余集合中，发现不在集合中。
3.找到一个整数y，使得y2≡2⋅a(mod11)，其中a是模11的一个非平方剩余。
可以选择a=3，则62≡2⋅3(mod11)。
4.利用模11的平方剩余集合求解6的平方根，发现6在平方剩余集合中。
5.得到两个解：x≡±6(mod11)。
二次同余式的解法
（原创实用版）
目录
1.二次同余式的基本概念
2.二次同余式的解法
3.实际应用案例
正文
【1.二次同余式的基本概念】
二次同余式，是指包含两个未知数的同余方程组。
同余方程组，是指一组含有相同未知数的整式方程，并且这些整式方程的解是整数。
在数学研究中，同余方程组的解法一直是一个重要研究领域。
二次同余式广泛应用于数论、代数几何等领域。
【2.二次同余式的解法】
解二次同余式通常采用代数方法，主要包括以下几种：
（1）替换法：将同余式中的一个未知数用另一个未知数表示，代入另一个方程求解。
（2）消元法：通过加减消去一个未知数，得到一个一元二次方程，然后求解。
（3）配方法：将同余式转化为两个一元二次方程，然后通过配方法求解。
（4）韦达定理：对于二次同余式，根据韦达定理，两个方程的根之和与根之积可以表示为另一个方程的系数。
利用这个定理，可以快速求解二次同余式。
【3.实际应用案例】
二次同余式在数学中有广泛应用，例如：已知方程组
```
x + y = 6
2x - y = 5
```
这是一个二次同余式，我们可以通过以上提到的方法求解，得到 x = 3, y = 4。
这个解在实际问题中有很多应用，比如在计算机图形学中，可以用这个解来表示两个图形的坐标。
总的来说，二次同余式是代数学的一个重要组成部分，它提供了一种处理含有两个未知数的整式方程的方法。
第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 。
若同余方程2x ≡a （mod m ） （6）有解，则称a 是模m 的平方剩余（或二次剩余）；若无解，则称a 是模m 的平方非剩余（或二次非剩余）。
【例】1是模4平方剩余，－1是模4平方非剩余。
【例】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。
问题：（1）设正整数a是模p的平方剩余，若记方程（6）中的解为x≡a（mod m），那么此处的平方根a（modm）与通常的代数方程2x＝a的解a有何区别？（2）如何判断方程（6）有解？（3）如何求方程（6）的解？（五）例【例5.1.2】求以15为模的所有平方剩余和平方非剩余。
（解）直接计算12，22，...，142得模15的平方剩余（实际只需计算12，22， (72)1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例5.1.3】求满足方程E：2y≡3x＋x＋1（mod 7）的所有整点（即坐标为整数的点）。
（解）对x＝0，1，2，3，4，5，6分别解出y：x＝0，2y≡1（mod 7），y≡1，6（mod 7）x＝1，2y≡3（mod 7），无解x＝2，2y≡4（mod 7），y≡2，5（mod 7）x＝3，2y≡3（mod 7），无解x＝4，2y≡6（mod 7），无解x＝5，2y≡5（mod 7），无解x＝6，2y≡6（mod 7），无解所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。
附：方程E ：2y ≡3x ＋x ＋1的图形称为椭圆曲线。
5.2 模为奇素数的平方剩余与平方非剩余方程2x ≡a （mod p ）, (a,p)＝1 （1）结论：方程（1）要么无解，要么有两个解（因为()2x -＝2x ）。
（p ＝时，方程恰好1个解）5. 2. 1 平方剩余的判断条件【定理5.2.1】（欧拉判别条件）设p 是奇素数，(a,p)＝1，则（i ）a 是模p 的平方剩余的充要条件是()21-p a ≡1（mod p ） （2）（ii ）a 是模p 的平方非剩余的充要条件是 ()21-p a ≡－1（mod p ） （3）并且当a 是模p 的平方剩余时，同余方程（1）恰有两个解。
（证）先证p a 时，式（2）或（3）有且仅有一个成立。
由费马定理1-p a ≡1（mod p ）()()221-p a －1≡0（mod p ） ()()()()112121+---p p a a ≡0（mod p ） （4） 即 11--p a p ＝()()()()112121+---p p a a但()()()1,12121+---p p a a ＝1或2且p ＞2。
⇒p 能整除()()()()11121+---p p a a ，但p 不能同时整除()121--p a 和()121+-p a （否则，p 能整除它们的最大公因子1或2） ⇒由式（4）知式（2）或（3）有且仅有一式成立。
（i ）必要性：a 是模p 的二次剩余⇒有0x 使得20x ≡a （mod p ）， ⇒()()21p 20-x ≡()21-p a （mod p ）。
即 ()2110--≡p p a x （mod p ）。
由于p a ⇒p 0x ，由欧拉定理10-p x ≡1（mod p ）。
充分性：()21-p a ≡1（mod p ）⇒p a 。
故一次同余方程bx ≡a （mod p ）, (1≤b ≤p －1) （5）有唯一解，对既约剩余系⎭⎬⎫⎩⎨⎧----=21,,1,1,,21p p A ΛΛ （6） 设b ＝j 时方程（5）的解j x x =（A x j ∈）。
若a 不是模p 的二次剩余⇒jx j ≠⇒A 中各数可按j 、x j配对，两两分完。
（b 1≠b 2，则相应的解x 1≠x 2，且除了±1之外，每个数的逆不是它本身） ⇒()()p a p p m od )!1(21-≡-即 ()()p a p m od 121-≡-（威尔逊定理）与式（2）矛盾⇒必有某个0j ，使00j x j =⇒a 是模p 的二次剩余。
（ii ）显然（由（i ）的证明即知）其次，若0x 0（mod p ）是方程（1）的解，则－0x 也是其解，且必有0x －0x （mod p ）。
故当(a , p )＝1时，方程（1）要么无解，要么同时有两个解。
（说明：本定理只是一个理论结果，当p >>1时，它并不是一个实用的判断方法）小结：对于任何整数a ，方程（1）的解数可能为()p a x T ;2-＝0, 1, 2【例5.2.1】设p ＝19，验证定理5.2.1的证明过程。
（解）由费马定理18a ≡1（mod 19），a ＝1, 2, …, 18方程2x ≡1（mod 19）只有两个解，即x ≡±1（mod 19）。
⇒9a ≡±1（mod 19）（视()2918a a ≡≡1（mod 19），即9a x ≡）◆ 针对必要性：【例】a ＝17是模19的二次剩余，即存在0x ≡6使得26≡17（mod 19）。
有()21-p a≡917≡186≡1（mod 19） 【2】2x ≡2（mod 19）无解，即a ＝2是模19的二次非剩余。
则9211922≡-≡－1（mod 19）◆ 针对充分性：【例】a ＝6，()21-p a ≡96≡1（mod 19），验证6是二次剩余。
解方程bx ≡6（mod 19）, (1≤b ≤18)所以6是二次剩余。
又选a ＝8，()21-p a ≡98≡－1（mod 19），验证：解方程 bx ≡8（mod 19）, 1≤b ≤181•2•…•18≡(1•8)(2•4)(3•9)(5•13)(6•14)(7•12)(10•16)(11•18)(15•17) ≡98≡－1（mod 19）【例2】判断137是否为模227的平方剩余。
（解）首先，227是素数。
其次，计算()1227137-≡－1（mod 227）所以，137是模227的平方非剩余。
【推论】设p 是奇素数，(a 1, p )＝1，(a 2, p )＝1，则 （i ）若a 1，a 2都是模p 的平方剩余，则a 1a 2是模p 的平方剩余；（ii ）若a 1，a 2都是模p 的平方非剩余，则a 1a 2是模p 的平方剩余；（iii ）若a 1是模p 的平方剩余，a 2是模p 的平方非剩余，则a 1a 2是模p 的平方非剩余。
（证）因()()2121-p a a ＝()()12211--p p a a5. 2. 2 平方剩余的个数【定理5.2.2】设p 是奇素数，则模p 的既约剩余系中平方剩余与平方非剩余的个数各为(p －1)／2，且(p －1)／2个平方剩余恰与序列12，22，…，221⎪⎭⎫ ⎝⎛-p 中的一个数同余。
（证）由定理5.2.1，模p 的平方剩余个数等于方程 21-p x ≡1（mod p ）的解数。
但 1121---p p x x由定理4.4.5知，方程的解数为21-p ，即平方剩余的个数是21-p ，且平方非剩余的个数是(p －1)－21-p ＝21-p 。
其次，可以证明当1≤k 1≤21-p ，1≤k 2≤21-p ，且k 1≠k 2时，有21k 22k mod p 。
故结论成立。
（定理4.4.5：设p 为素数，n 为正整数，n ≤p 。
则同余方程()x f ＝0111a x a x a x n n n ++++--Λ≡0 mod p 有n 个解⇔x x p -被()x f 除所得余式的所有系数都是p 的倍数）5.3 勒让德符号目的：快速判断整数a 是否为素数p 的平方剩余。
（一） 勒让德符号【定义5.3.1】设p 是素数，定义勒让德（Legendre ）符号为：L(a, p)＝⎪⎪⎭⎫ ⎝⎛p a ＝⎪⎩⎪⎨⎧-。
当的二次非剩余；是模当的二次剩余；是模当a p p a p a ,0,1,1 【推论】整数a 是素数p 的平方剩余的充要条件是⎪⎪⎭⎫ ⎝⎛p a ＝1。
（证）由定义5.3.1。
意义：判断平方剩余转化为计算勒让德符号的值。
【例5.3.1】计算勒让德符号17a ⎛⎫ ⎪⎝⎭的值。
其中a ＝0, 1, 2, …,16。
（解）直接计算： ⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛171617151713179178174172171＝1 ⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛1714171217111710177176175173＝－1 （注：本例仍是利用平方剩余而得到勒让德符号值） 问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。
