下载文档原格式
初等数论第五章二次同余式与平方剩余第五章二次同余式与平方剩余第五章二次同余式与平方剩余§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)。
二次同余式的解法一、什么是二次同余式二次同余式是指形如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)。
数论的四⼤定理详解（转载）转载于:前⾔可以发现RSA中的很多攻击⽅法都是从数论四⼤定理推导出的，所以找时间好好学习了⼀下数论四⼤定理的证明及其应⽤场景——Rabin算法。
欧拉定理若$n,a$为正整数，且$n,a$互素，即$gcd(a,n) = 1$，则$a^{φ(n)}\equiv1\pmod{n}$证明⾸先，我们需要知道欧拉定理是什么：数论上的欧拉定理，指的是$a^{φ(n)}\equiv1\pmod{n}$这个式⼦实在$a$和$n$互质的前提下成⽴的。
证明⾸先，我们知道在1到$n$的数中，与n互质的⼀共有$φ(n$)个，所以我们把这$φ(n)$个数拿出来，放到设出的集合X中，即为$x_1,x_2……x_{φ(n)}$那么接下来，我们可以再设出⼀个集合为M，设M中的数为：$m_1=a∗x_1,m_2=a∗x_2……m_φ(n)=a∗x_{φ(n)}$下⾯我们证明两个推理：⼀、M中任意两个数都不模n同余。
反证法。
证明：假设M中存在两个数设为$m_a,m_b$模$n$同余。
即$m_a\equiv m_b$移项得到：$m_a−m_b=n∗k$再将m⽤x来表⽰得到：$a∗x_a−a∗x_b=n∗k$提取公因式得到：$a∗(x_a−x_b)=n∗k$我们现在已知$a$与$n$互质，那么式⼦就可以转化为：$x_a−x_b\equiv 0 \pmod{n}$因为$a$中没有与$n$的公因⼦（1除外）所以$a !\equiv 0 \pmod{n}$ 所有只能是$ x_a−x_b\equiv 0\pmod{n}$。
⼜因为$x_a,x_b$都是⼩于$n$的并且不会相同，那么上述的式⼦⾃然全都不成⽴。
假设不成⽴。
证得：$M$中任意两个数都不模$4$同余。
⼆、M中的数除以n的余数全部与n互质。
证明：我们已知$m_i=a∗x_i$⼜因为$a$与$n$互质，$x_i$与$n$互质，所以可得$m_i$与$n$互质。
带⼊到欧⼏⾥得算法中推⼀步就好了。
二次同余式的解法1. 引言在数论和抽象代数中，同余是一个重要的概念。
同余关系是指两个整数之间具有相同的余数，即它们除以某个整数所得的余数相等。
在解决一些问题时，我们经常会遇到二次同余式，即形如x^2 ≡ a (mod m)的方程。
本文将介绍二次同余式的解法，并详细讨论三种常用的解法：勒让德符号、平方剩余和中国剩余定理。
2. 勒让德符号勒让德符号是二次剩余理论中一个重要的工具。
对于给定的整数a和素数p，勒让德符号(a/p)定义为：(a/p) = { 1, 若存在整数x满足x^2 ≡ a (mod p) -1, 若不存在整数x满足x^2 ≡ a (mod p) }根据勒让德符号，可以判断一个整数是否为平方剩余。
如果(a/p) = 1，则a是p模意义下的平方剩余；如果(a/p) = -1，则a是p模意义下的非平方剩余。
使用勒让德符号可以解决一些特殊情况下的二次同余式。
例如，当p是奇素数且a是整数时，如果(a/p) = 1，则二次同余式x^2 ≡ a (mod p)有两个解；如果(a/p) = -1，则无解。
3. 平方剩余平方剩余是指对于给定的整数a和模m，存在一个整数x使得x^2 ≡ a (mod m)成立。
平方剩余是二次同余式的一种特殊情况。
为了判断一个整数是否为平方剩余，可以使用勒让德符号。
对于给定的素数p和整数a，如果(a/p) = 1，则a是p模意义下的平方剩余；如果(a/p) = -1，则a是p 模意义下的非平方剩余。
当我们确定一个整数a是模m意义下的平方剩余后，可以进一步求解二次同余式x^2 ≡ a (mod m)。
其中m可以是任意正整数。
求解二次同余式有多种方法，如试位法、勒让德符号法和Tonelli-Shanks算法等。
这些方法都可以根据给定的模m和平方剩余a来找到所有满足条件的x。
4. 中国剩余定理中国剩余定理是一种用于求解一组同余方程组的方法。
对于给定的一组同余方程：x ≡ a1 (mod m1) x ≡ a2 (mod m2) … x ≡ an (mod mn)其中m1, m2, …, mn两两互质，中国剩余定理可以找到一个解x，且满足0 ≤ x < M = m1 * m2 * … * mn。
本章的目的是较深入地讨论 1.一般二次 了解一般二次及：教学过程:本节主要讨论 2.单质数的 了解单质数的：教学过程:这节我们讨论单质数p 的)(mod 121p ap ≡-：而)(mod 121p ap -≡-单质数p 的使的)(mod ),(mod 222121p a r p a r ≡≡于是有)(mod )(21221p a a r r ≡ 这说明一般二次同余式在第四章中，我们讨论了高次同余式的解的一般理论，但在实际中，要解一个高次同余式一般比较困难。
在本章我们重点讨论二次同余式的解法。
思路是先把一般二次同余式化为特殊的二次同余式，再引入平方剩余与平方非剩余，并利用勒让得符号来判断特殊二次同余式是否有解。
二次同余式的一般形式 二次同余式的一般形式是，0 （） （1）化一般二次同余式为特殊二次同余式 由高次同余式的理论知，若的标准分解式为，则（1）有解的充要条件是下面同余式组中每个同余式有解。
于是要判别（1）是否有解及如何解（1），我们可重点讨论为质数。
（2）下面对（2）分情况进行讨论。
找到（2）有解的判别法。
由于（2）为二次同余式，故可假定，若有但(,,)，则（2）化为。
而。
故还可假定(,,)。
1) |，|。
则。
因而同余式无解。
故（2）设有解。
2)|，。
则无解，故（2）有解的充要条件是有解，即有解。
但（，）＝1。
故有解，从而（2）有解，且（2）的解可由的解求出。
3) ，>2。
则。
用4乘（2）后再配方，即得（3）易证（2）和（3）等价。
用代2＋得（4）则（2）有解的充要条件是（4）有解，于是将（2）化为（4）讨论。
4)，＝2。
这时为奇。
（i ）若2，则无解。
故（2）有解的充要条件是有解。
因对任何整数恒有。
所以（2）有解的充要条件是有解，即2|。
（ii ） 若2|，令。
由知（2）有解的充要条件是有解。
即(5)有解。
作代换＝＋，则（2）有解的充要条件是有解。
由上面讨论，可将（2）的问题化为二次同余式或一般情况即(6)平方剩余和非平方剩余定义 若同余式（6）有解，则叫模的平方剩余，若同余式（6）无解，则叫模的平方非剩余。
