初等数论(十)——平方剩余

中国剩余定理知识点总结在初等数论中，我们经常会遇到形如x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (mod mn)的线性同余方程组，其中ai和mi都是整数，m1, m2, ..., mn是两两互质的正整数。

中国剩余定理就是解决这类问题的重要方法。

下面我们来详细介绍一下中国剩余定理的一些基本知识点。

1. 中国剩余定理的表述中国剩余定理可以用如下的形式来表述：对于给定的两两互质的正整数m1, m2, ..., mn，以及任意的整数a1, a2, ..., an，中国剩余定理断言，存在一个解x，使得对于所有的i=1,2,...,n，都有x≡ai(mod mi)。

这个解x是唯一存在的，并且可以用下面的形式来表示：x = a + tM其中a是通解，t是任意整数，M是m1, m2, ..., mn的最小公倍数，即M=lcm(m1, m2, ..., mn)。

2. 中国剩余定理的应用在数论和密码学等领域中，中国剩余定理有着广泛的应用。

例如，可以利用中国剩余定理来解决一些测定一些重要的数学问题，如幂模运算、循环小数、素数和因数分解等问题。

在密码学中，中国剩余定理也被广泛应用。

例如在RSA公钥密码系统中，中国剩余定理能够加速大数的幂模运算，从而大大提高RSA的加密和解密速度。

3. 中国剩余定理的证明中国剩余定理的证明是通过数学归纳法来完成的。

首先我们可以证明当n=2时定理成立，然后利用数学归纳法来证明对于任意n都成立。

具体来说，我们首先假设对于n=k（k≥2）时定理成立，即对于任意的m1, m2, ..., mk，以及任意的整数a1, a2, ..., ak，能够找到一个解x使得x≡ai(mod mi)。

然后我们来考察下一个情况，即n=k+1时定理成立。

我们可以利用n=k时的结果来构造一个新的解x'，然后利用一些数论知识来证明x'也满足n=k+1时的情况。

通过这样的数学归纳法的证明，我们可以得出中国剩余定理的正确性。

2019/10/24
数论
三 模为奇素数的平方剩余
与平方非剩余
定理2 若p是素
再根据 1.4 定理 2，我们有
数，如果p| ab, 则有p| a 或 p| b
p1
p1
p | a 2 1或 p | a 2 1
因此，结论(i)告诉我们： a 是模 p 的 平方非剩余的充分必要条件是
p1
a 2 1(mod p)
第四章 二次同余式与平方剩余
一 二次同余式的概念 二 二次同余式的应用 三 模为奇素数的平方剩余与平方
非剩余
2019/10/24
数论
一 二次同余式的概念
二次同余式的一般形式是ax2 bx c 0(mod m)(1)
其中 a 0(mod m).
因为正整数
m
有素因数分解式
m

p1 1
2019/10/24
数论
二 二次同余式的应用
x=2, y2 =5 (mod 7), 无解， x=3, y2 =4 (mod 7), y=2,5(mod 7)， x=4, y2 =0 (mod 7), y=0(mod 7)， x=5, y2 =6 (mod 7), 无解， x=6, y2 =0 (mod 7), y=0(mod 7).
反过来，若(2)成立，则同样根据 3.4 定 理 5，我们有同余式 x2 ≡a (mod p) 有解，
即 a 是模 p 平方剩余.
(ii)因为 p 是奇素数，(a, p)=1,根据 2.4 定
理 1（欧拉定理），我们有表达式
p1
p1
(a 2 1)(a 2 1) a p1 1 0(mod p)
2019/10/24
数论

剩余．
平方剩余
定理7.1.1 设p是奇素数．在模p的简化剩余系中，有
p 1 个平方剩余， p 1 个平方非剩余．
2
2
证明 取模p的最小绝对简化剩余系
p 1 , (p 1 1 ) ,K , 2 , 1 ,1 ,2 ,K ,p 1 1 ,p 1 .
22
22
则模p的全部平方剩余为
( p 1 ) 2 , [ ( p 1 1 ) ] 2 , K , ( 2 ) 2 , ( 1 ) 2 , 1 2 , 2 2 , K , ( p 1 1 ) 2 , ( p 1 ) 2 .
对于任意aGF(p)*，有ap1 1 (mod p)，
即
ap1 –1 0 (mod p)，
p 1
p 1
a p 1 1 (a2 1 )(a2 1 ) 0 (m o dp )
由于p是素数，则
p 1
p 1
(a 2 1 ) 0 (m o d p )或 (a2 1 ) 0 (m o d p )
2
平方剩余
例7.1.2 求出p = 11，17时的平方剩余和平方非剩余．
解 p = 11时：
12 1 (mod 11)，22 4 (mod 11)，32 9 (mod 11)，42 5 (mod 11)，52 3 (mod 11)，
所以1，3，4，5，9是模11的平方剩余，而2，6，7，8，10 是模11的平方非剩余．
291
7 2 = 714 =787472 7(6)( 9) 1 (mod 29)，
所以7是模29的平方剩余．
7.2 勒让德符号
定义7.2.1 设p是奇素数，a是整数．勒让德 （Legendre）符号定义如下：
1,a是模p的平方剩余；

2019/9/15
14
例如：x2 a(mod11) 模11的平方剩余为1，-2，3，4，5.
方程 x2 1(mod11)的解为：x 1,10(mod11); 方程 x2 2(mod11)的解为：x 3,8(mod11); 方程 x2 3(mod11)的解为：x 5,6(mod11); 方程 x2 4(mod11)的解为：x 2,9(mod11); 方程 x2 5(mod11)的解为：x 4,7(mod11).
若 x2 a(modm有) 解，则a称为模m的平方剩余； 否则，称a为模m的平方非剩余。
例4.求m 3,5,7,11的平方剩余和平方非剩余.
解：要使x2 a(mod 3)有解，且(a,3) 1. 只要求出x 2对模3的余数即可.
12 1(mod 3),22 1(mod 3), ∴ 模3的平方剩余为1；平方非剩余为2(或-1).
根据§4.4-TH5[P86]知方，程(1)有两个解。
定理5 设n p，则同余方程
f(x) = xn an 1xn 1 a1x a0 0 (mod p) 有n个解的充要条件是 存在整数多项式q(x)和r(x)，r(x)的次数< n，使得
x p x = f(x)q(x) pr(x)。
2019/9/15
5
三、同余式 y2 A 0(mod p ) 解的讨论
1、当 p A时，有解，且其解易求。
例1. y2 81 0(mod 33 ) y2 0(mod 33 ) y 0(mod 32 ) y 0,9，18(mod 33 )
2、当p ŒA时，可化为y2 A 0(mod p ),( A, p ) 1.

平方非剩余
如果一个数$a$模$p$同余于$x^2$模$p$ ，则称$a$为$x^2$的平方非剩余。
判定法则
判定法则一
费马小定理，若$p$是质数，且$(a, p)=1$，则有$a^{p-1} equiv 1 pmod{p}$。
判定法则二
二次互反律，设$p, q$是两个不同的奇素数，且$(p, q)=1$，则有$(p equiv q pmod{4}) Leftrightarrow (q equiv p pmod{4})$。
03
具体的证明过程需要用到一些较为复杂的数学符号 和逻辑推导，这里不再赘述。
应用案例
01
02
03
在密码学中，二次同余 式与平方剩余的概念被 广泛应用于一些加密算 法的设计，如 RSA 算法
。
在数论研究中，这些概 念也是重要的工具，可 以帮助我们解决一些数
论中的难题。
在实际生活中，这些概 念在金融、物流等领域 也有一定的应用，例如 在电子支付和电子签名 的安全性验证等方面。
解释
这是一个关于 (x) 的二次方程，但它 的解必须满足同余条件，即解必须是 模 (m) 的同余类。
性质
性质1
如果 (a, b, c, m) 满足二次同余式的定义，那么对于任意整数 (x)，如果 (x^2 + bx + c equiv 0 (mod m)) 成立 ，那么 (ax^2 + bx + c equiv 0 (mod m)) 也一定成立。
THANKS
感谢观看
应用实例
在密码学中的应用
平方剩余在密码学中有重要的应用，例如RSA公钥密码算法中就使用了平方剩余的性质 。
在数论中的应用
平方剩余是数论中的一个重要概念，它在证明费马大定理、哥德巴赫猜想等数学问题中 发挥了重要作用。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章 整数的可除性1. 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 2性质：(1)若c b |且a c |，则a b |(传递性质)；(2)若a b |且c b |，则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。

若反复运用这一性质，易知a b |及c b |，则对于任意的整数v u ,有)(|cv au b ±。

更一般，若n a a a ,,,21Λ都是b 的倍数，则)(|21n a a a b +++Λ。

或着i b a |，则∑=ni ii b c a 1|其中n i Z c i ,,2,1,Λ=∈；(3)若a b |，则或者0=a ，或者||||b a ≥，因此若a b |且b a |，则b a ±=； (4)b a ,互质，若c b c a |,|，则c ab |；(5)p 是质数，若n a a a p Λ21|，则p 能整除n a a a ,,,21Λ中的某一个；特别地，若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。

24，29，31，32，35
8 / 38
《初等数论》习题解答（第三版）新乡学院
2、 (i)应用前几章的结果证明:模 p 的简化剩余系中一定有平方
剩余及平方非剩余存在，
(ii) 证明两个平方剩余的乘积是平方剩余;平方剩余与平方
非剩余的乘积是平方非剩余。
(iii)应用(i)、(ii)证明：模 p 的简化剩余系中平方剩余与平 p 1
设其解是： x 2mod p，即有： 22 a mod p，
13 / 38
《初等数论》习题解答（第三版）新乡学院
令22 a kp 22 a k p 0 mod p
2
而 2 a 2 C1 21 a C2 22 a a
pQ a
2 a p Q a
21 / 38
《初等数论》习题解答（第三版）新乡学院
3、设n是正整数，4n 3及8n 7都是质数，说明 24n3 1(mod 8n 7) 由此证明：23 | 211 1, 47 | 223 1,503 | 2251 1。
证明：当 p 8n 7时，由本节定理 1 的推论知2为平方剩余，
应用欧拉判别条件即有
p 3
当它们同为1或同时为
1时，
3 p
1，
3
一为1，一为 1时，
p
1
24 / 38
《初等数论》习题解答（第三版）新乡学院
p 1
p1
显然，当 为偶数，而 p 1(mod 4)时，(1) 2 1，
2
p 1
p1
当 是奇数，即 p 1(mod 4)时，(1) 2 1。
2
再因为 p 是奇质数，关于模3我们有 p 1或 p 1，
用 4a 乘 (1) 后再配方，即得 (2ax b)2 q 0(mod m), q b2 4ac 仍记2ax b为 x，即有 x2 q(mod m) 由以上讨论即知若 x x0 (mod m)为(1)的解， 则 x 2ax0 b(mod m)为(2)的解，必要性得证。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章整数的可除性1.2性质：(1)传递性质)；(2)闭。

若反复运用这一性质，易则对于任意的整更一般，(3)若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。

注意：r 共有b 种可能的取值：0,1，……，1-b 。

若0=r ，即为a 被b 整除的情形；易知，带余除法中的商实际上为⎥⎦⎤⎢⎣⎡b a （不超过b a 的最大整数），而带余除法的核心是关于余数r 的不等式：b r <≤0。

证明a b |的基本手法是将a 分解为b 与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生若n 是正整数，则))((1221----++++-=-n n n n n n y xy y x x y x y x Λ；若n 是正奇数，则))((1221----+-+-+=+n n n n n n y xy y x x y x y x Λ；（在上式中用y -代y ）(7)如果在等式∑∑===mk k ni i b a 11中取去某一项外，其余各项均为c 的倍数，则这一项也是c 的倍数；(8)个连续整数中，有且只有一个是n 的倍数；(9)任何n 个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除；第二章 不定方程1. 定义：二元一次不定方程的一般形式是ax +by = c ，其中a ,b ,c 是整数2. 定理：(1) 不定方程有整数解的充要条件为 (a,b) | c. (2) 设是方程的一组解，则不定方程有无穷解，其一切解可表示成⎩⎨⎧+=-=t a yy t b x x 1010 Λ,2,1,0±±=t 其中),(,),(11b a b b b a a a ==3. 不定方程的解法：（1）观察法：当a,b 的绝对值较小时可直接观察不定方程的一组特解，然后用⎩⎨⎧+=-=ta y y tb x x 1010得到其所有解（2）公式法：当a,b 的绝对值较小时，可用公式211021110,,1,0,,1----+===+===k k k k k k k k P Q q Q Q Q P P q P q P P 得到特解n n n n P y Q x )1(,)1(010-=-=-，然后用公式写出一切解。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章 整数的可除性1. 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 2性质：(1)若c b |且a c |，则a b |(传递性质)；(2)若a b |且c b |，则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。

若反复运用这一性质，易知a b |及c b |，则对于任意的整数v u ,有)(|cv au b ±。

更一般，若n a a a ,,,21Λ都是b 的倍数，则)(|21n a a a b +++Λ。

或着i b a |，则∑=ni ii b c a 1|其中n i Z c i ,,2,1,Λ=∈；(3)若a b |，则或者0=a ，或者||||b a ≥，因此若a b |且b a |，则b a ±=； (4)b a ,互质，若c b c a |,|，则c ab |；(5)p 是质数，若n a a a p Λ21|，则p 能整除n a a a ,,,21Λ中的某一个；特别地，若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。

全国青少年信息学奥林匹克系列竞赛大纲（草案）1.介绍1.1目的本大纲的制定目的在于：（1）为NOI系列竞赛题目的命制提供依据；（2）为NOI指导教师的教学提供方向和指导；（3）为参加NOI系列活动的学生及其他信息学爱好者提供学习范围；（4）为各省市开展和组织NOI省选等工作提供参照。

1.2原则（1）差异化原则为促进信息学和NOI活动的普及，大纲应较详尽地规定中低等级知识点的范围，以尽可能清晰地划定相应等级的知识范围，有效地指导入门学生的学习及相关的教学活动；为促进NOI的国际竞争力，大纲应避免过于严格地限制命题的思路，须为NOI等高水平竞赛的题目命制留有充分的开放性，因此不宜过于细致地规定高等级知识点的范围。

为此，大纲的制定将采取“上粗下细”的指导思想：知识等级越低，其内容规定得越细；知识等级越高，其内容规定得越粗。

（2）统一性原则为保证大纲的简明性和系统性，高等级比赛的知识范围将自动地包含低等级比赛的所有知识点。

同时，对每个等级按照竞赛环境（Linux和Windows）、程序设计语言（C++）、数据结构、算法、以及数学等进行了分类。

对每个大类又按照知识点的属性继续划分为若干小类；某些知识点可能与多个类别均有紧密或松散联系，本大纲均按其主要属性划定其类别，以避免同一知识点在多个类别中的重复出现。

2.考纲内容2.1全国青少年信息学奥林匹克联赛普及组（简称NOIP-J）2.1.1C++集成调试工具（IDE）使用1.Windows系统下：例如Dev C++,….,等【1】2.Linux系统下：例如Guide，…,等【1】2.1.2C++程序设计1.程序基本概念a)标识符、关键字、常量、变量、字符串、表达式的概念【1】b)常量与变量的命名、定义及作用【1】c)头文件与名字空间的定义与理解【2】d)编辑、编译、解释、调试等概念理解【2】2.基本数据类型a)整型：int,long long【1】b)实型：float,double【1】c)字符型：char【1】d)逻辑型：bool【1】3.程序基本语句a)cin语句，scanf语句，cout语句，printf语句，赋值语句，复合语句【2】b)if语句，switch语句，多层条件语句【2】c)for语句，while语句，do while语句d)多层循环语句【3】4.基本运算a)算术运算：加、减、乘、除、整除、求余【1】b)关系运算：大于，大于等于，小于，小于等于，等于，不等于【1】c)逻辑运算：与&&、或||、非！【1】d)变量自增与自减运算【1】e)三目运算【1】f)位运算：与&、或|、非~、异或^、左移、右移【2】5.数学库常用函数绝对值函数，四舍五入函数，取上整函数，取下整函数，常用三角函数，对数函数，指数函数，平方根函数【3】6.结构化程序设计a)顺序结构、分支结构和循环结构【1】b)自顶向下、逐步求精的模块化程序设计【2】c)流程图的概念及流程图描述【2】7.数组a)数组定义，数组与数组下标的含义【1】b)数组的读入与输出【1】c)纯一维数组的综合运用【2】d)纯二维数组与多维数组的综合应用【3】8.字符串的处理a)字符数组与字符串的关系【2】b)字符数组的综合应用【2】c)string类定义、相关函数引用【2】d)string类的综合应用【3】9.函数与递归a)函数定义与调用，形参与实参【2】b)传值参数与传引用参数【3】c)常量与变量的作用范围【2】d)递归函数的概念、定义与调用【2】10.结构体类型a)结构体的定义及应用【3】11.指针类型a)指针的概念及调用【4】b)指针与数组【4】c)指针与string类【4】d)指向结构体的指针【4】12.文件的读写操作a)文件的基本概念，文本文件的基本操作【2】b)文件类型【2】c)文件读入、输出等操作【2】13.STL模板应用a)<algorithm>中sort函数【3】b)栈（stack）、队列（queue）、链表（list）、集合（set）等容器【4】2.1.3数据结构1.线性表a)链表：单链表、双向链表、循环链表【3】b)栈【3】c)队列【3】2.简单树a)树的定义及其相关概念【3】b)树的父亲表示法【4】c)二叉树的定义及其基本性质【3】d)二叉树的孩子表示法【4】e)二叉树的遍历：前序、中序、后序遍历【4】3.特殊树a)完全二叉树的定义与基本性质【4】b)完全二叉树的数组表示法【4】c)哈夫曼树的定义、构造及其遍历【4】d)二叉排序树的定义、构造及其遍历【4】4.简单图a)图的定义及其相关概念【3】b)图的邻接矩阵存储【4】c)图的邻接表存储【4】2.1.4算法1.算法概念与描述a)算法概念【1】b)算法描述：自然语言描述、流程图描述、伪代码描述【2】2.入门算法a)枚举法【1】b)模拟法【1】3.基础算法a)贪心法【3】b)递推法【3】c)递归法【4】d)二分法【4】e)倍增法【4】4.数值处理算法a)高精度的加法【4】b)高精度的减法【4】c)高精度的乘法【4】d)求高精度整数除以单精度整数的商和余数【4】5.排序算法a)冒泡排序【3】b)简单选择排序【3】c)简单插入排序【3】6.图论算法a)图的深度优先遍历算法【4】b)图的宽度优先遍历算法【4】c)洪水填充算法（floodfill）【5】7.动态规划a)动态规划的基本原理【4】b)简单线型动态规划【4】c)简单背包类型动态规划【5】d)简单区间类型动态规划【5】2.1.5数学1.数及其运算a)数的概念，算术运算（加、减、乘、除、求余）【1】b)数制：二进制、八进制、十六进制和十进制数及其转换【1】c)编码：ASCII码，哈夫曼编码，格雷码【2】2.初中数学a)初中代数【1】b)初中平面几何【1】3.初等数论a)整除、因数、倍数、指数、质数、合数、同余等概念【3】b)唯一分解定理【3】c)欧几里德算法（辗转相除法）【3】d)埃氏筛法和线性筛法求素数【4】4.组合数学e)加法原理【2】f)乘法原理【2】g)排列及计算公式【4】h)组合及计算公式【4】i)杨辉三角公式【4】2.2全国青少年信息学奥林匹克联赛提高组（简称NOIP-S）2.2.1Linux系统1.会使用mkdir、cp、rm、mv等命令新建、复制、删除、移动等文件或目录【5】2.会使用cd、pwd、ls等命令更改、显示目录路径和查看目录中的文件【5】3.会使用Gedit、Vim或Emacs等文本编辑工具编写代码【5】4.编译工具：g++或gcc的使用【5】5.会运行程序，并使用time命令查看用时【5】6.gdb调试工具：能使用gdb中的break、display、continue、step等命令调试程序【5】2.2.1C++程序设计1.类（class）a）类的概念及简单应用【6】b）成员函数和运算符重载【6】2.STL模板：a)向量（vector）【5】b)列表(list)，双端队列(deque)，优先队列（priority_queue）【5】c)多重集合(multiset)【5】d)映射（map），多重映射(multimap)【5】e)对(pair)【5】2.2.2数据结构1.线性结构a)双端栈【5】b)双端队列【5】c)有序队列【5】d)优先队列【6】e)倍增表（ST表）【6】2.集合与森林a)等价类【6】b)并查集【6】c)树与二叉树的转化——孩子兄弟表示法【6】3.特殊树j)线段树与树状数组【6】k)二叉平衡树AVL、treap、splay等【8】l)字典树（trie树）【6】m)笛卡尔树【7】n)基环树【8】4.常见图a)稀疏图【5】b)偶图（二分图）【6】c)欧拉图【6】d)连通图与强连通图【7】e)重连通图【7】f)有向无环图【6】5.哈希表a)数值哈希函数构造【5】b)排列哈希函数构造【6】c)字符串哈希函数构造【6】d)哈希函数冲突的常用解决方法【6】2.2.3算法1.复杂性分析a)空间复杂度分析【6】b)时间复杂度分析【6】2.基础算法分治算法【6】3.排序算法o)归并排序【5】p)快速排序【5】q)堆排序【6】r)树形选择排序（锦标赛排序）【6】s)桶排序【5】t)基数排序【6】4.字符串相关算法a)字符串匹配算法——KMP【6】5.搜索算法a)搜索的剪枝优化【6】b)搜索对象的压缩存储【8】c)记忆化搜索【6】d)启发式搜索【7】e)双向宽度优先搜索【7】f)迭代加深搜索【7】6.图论算法u)Prim和kruskal等求最小生成树算法【6】v)求次小生成树算法【7】w)Dijkstra、bellman_ford、SPFA等求单源最短路算法【6】x)求单源次短路径算法【7】y)Floyd-Warshall算法求任意两点间的最短路算法和传递闭包【6】z)有向无环图的Toposort算法【6】aa)求欧拉道路和欧拉回路算法【6】ab)二分图的构造及其判定算法【6】ac)最近公共祖先【6】ad)求强联通分量算法【7】ae)强连通分量的缩点算法【7】af)求割点、割边算法【7】7.动态规划a)树型动态规划【6】b)状态压缩动态规划【7】c)动态规划的常用优化【8】2.2.4数学1.高中数学a)代数【5】b)立体几何【6】c)解析几何【6】2.初等数论ag)同余式【5】ah)欧拉定理和欧拉函数【7】ai)费马小定理【7】aj)威尔逊定理【7】ak)裴蜀定理【7】al)扩展欧几里得算法【7】am)孙子定理（即中国剩余定理）【8】3.组合数学a)可重集排列【6】b)可重集组合【6】c)错排列、圆排列【6】d)容斥原理【7】e)鸽巢原理【6】f)卡特兰数【7】g)二项式定理【6】4.线性代数a)矩阵概念【5】b)特殊矩阵：稀疏矩阵，三角矩阵，对称矩阵【6】c)矩阵的初等变换【6】d)矩阵的加减乘和转置运算【6】e)线性方程组的高斯消元法【7】2.3全国青少年信息学奥林匹克竞赛（简称NOI）2.3.1C++程序设计1.STL模板：容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)【8】2.面向对象的程序设计思想（OOP）【8】2.3.2数据结构1.线性结构an)分块【8】ao)块状链表【8】2.序列a)跳跃表【9】b)后缀数组【8】c)无根树的Prüfer序列【9】3.复杂树a)树链剖分【8】b)后缀树【9】c)二维线段树【8】d)最小树形图【10】e)树套树【9】f)k-d树【9】g)动态树（LCT）【10】h)主席树【8】4.可合并堆a)左偏树【8】b)二项堆【10】6．可持久化数据结构【9】2.3.3算法1.算法策略a)复杂分治思想【9】b)平衡规划思想【9】c)构造思想【9】2.字符串算法ap)多模匹配算法——AC自动机【8】aq)求字符串前缀和后缀算法——扩展KMP【9】ar)确定性有穷自动机——DFA算法【9】as)非确定性有穷自动机——NFA算法【10】at)求最长回文串的Manacher算法【8】au)后缀自动机【10】3.图论算法a)网络流算法【8】b)图的支配集、独立集与覆盖集【10】c)二分图的最大匹配——匈牙利算法【8】d)二分图的最佳匹配算法——KM算法【9】e)一般图的匹配【10】4.动态规划av)复杂动态规划模型构建【9】aw)复杂动态规划模型的优化【9】2.3.4数学2.初等数论a)原根和指数【8】b)完全数【9】c)平方剩余【10】d)二次同余式【10】e)二次互反律【10】f)狄利克雷（Dirichlet）卷积【9】g)大步小步（BSGS）算法【8】3.离散数学a)代数系统【10】b)群【10】c)置换群、循环群【9】4.组合数学a)母函数【9】b)莫比乌斯变换【9】c)Burnside引理与Polya原理【9】d)斯特林数【9】5.高等数学a)多项式函数微分【9】b)多项式函数积分【9】c)泰勒级数【9】d)快速傅里叶变换(FFT)【9】e)卷积【9】6.线性代数a)矩阵的逆运算【9】b)行列式及其运算【9】c)线性相关与矩阵的逆【9】7.概率论a)概率相关概念【8】b)求概率的乘法公式、全概率公式、贝叶斯公式【9】8.游戏论a)零和游戏问题——NIM游戏等【9】b)SG函数概念及应用【9】9.运筹学a)线性规划之单纯性法【10】10.计算几何a)矢量及其运算【7】b)点、线、面之间的位置判断【8】c)常见图形的面积计算【8】d)半平面交【9】e)二维凸包的求法及其应用【8】。

例6 设p是适合p 1(mod 4)的素数, y a (mod p )是模p的平方剩余. 证明 : y a (mod p )也是模p的平方剩余.
证明 : 令p 4k 1,由定理1知, a 则(-a )
p 1 2
p 1 2
1(mod p),
1(mod p ).
注意
定理11的二次剩余的充要条件是欧拉判别条件的二次剩余则方程有两个解的二次非剩余的充要条件是1证明由第四章第四节定理有解的充要条件是若有解则解数为易得1则由定理是素数的简化剩余系中二次剩余与非二次剩余的个数都是而且的每个二次剩余与且仅与数列中的一个数同余11111证明由定理知平方剩余个数等于同余式的解数个解的充要条件是存在整系数多项式的次数知平方剩余的个数是111显然中的数都是平方剩余只需证明数列任何两个数对模不同余对任意这都是不可能注意该定理给出了判断方程是否有解的一种方法即判断是否与中之一数关于模同余如果则方程有解否则方程无解欧拉定理并不是一个实用的判别法因为对具体的素数当它不太大时我们通常可以通过计算直接确定哪些是平方剩余哪些是平方非剩余这要比验要简单当较大时这两种方法都不实用
2
如果(a, p ) p, 则方程(1)成为一次同余方程, 只需考虑p 2, 且(a, p ) 1的情形. (4a, p ) 1, 方程(1)等价于 4a x 4abx 4ac 0(mod p ), (2ax b) b 4ac(mod p ), 研究方程(1)归纳对方程x a (mod p )的研究.
p -1 2
1(mod p )的解数.
-1 x p x, 即x p - x ( x
p -1 2
-1) f ( x),
由第四章第四节定理5 : 设n p, 则同余方程f ( x) x n an -1 x n-1 a1 x a0 0(mod p ) 有n个解的充要条件是存在 整系数多项式q ( x)和r ( x), 且r ( x)的次数 n, x p x f ( x)q ( x) p r ( x). p -1 知, 平方剩余的个数是 , 2 又模p恰有p -1个与p互素的剩余类, 则模p的平方剩余与非平方剩余总数等于p -1, p -1 p -1 p 1 . 2 2

高斯二次互反律高斯二次互反律，是经典数论中的定理之一。

在数论中，特别是在同余理论里，二次互反律（quadratic reciprocity law）是一个用于判别二次剩余，即二次同余方程之整数解的存在性的定律。

高斯二次互反律漂亮地解决了勒让德符号的计算问题，从而在实际上解决了二次剩余的判别问题。

欧拉和勒让德都曾经提出过二次互反律的猜想。

但第一个严格的证明是由高斯在1796年作出的，随后他又发现了另外七个不同的证明。

在《算数研究》一书和相关论文中，高斯将其称为“基石”。

私下里高斯把二次互反律誉为算术理论中的宝石，是一个黄金定律。

有人说：“二次互反律无疑是数论中最重要的工具，并且在数论的发展史中处于中心地位。

”高斯之后雅可比、柯西、刘维尔、克罗内克、弗洛贝尼乌斯等也相继给出了新的证明。

至今，二次互反律已有超过200个不同的的证明。

二次互反律可以推广到更高次的情况，如三次互反律等等。

二次互反律被称为“数论之酿母”，在数论中处于极高的地位。

后来希尔伯特、塞尔等数学家将它推广到更一般的情形。

“二次互反律”是“经典数论”中极为美妙的一个定理，有“数论之酿母”之美誉，是数论中“最重要的工具”，是“经典数论”中最出色的定理之一，在“数论”的发展过程中，有着无可替代的重要地位。

高斯把“二次互反律”誉为数论中的宝石，是一个“黄金定律”。

“二次互反律”最早产生于17世纪费马的时代。

费马曾提出了好些个关于“数论”方面的猜想，并且声称证明了它们，但是又没人见到过他的实际证明过程，也不知他是真的证明了还是吹牛。

数学家们为了证明费马的这类迷一般的命题，意外地发现了“二次互反律”。

1796年，高斯第一次证明了“二次互反律，开创了用“数学归纳法”解决“数论”问题的先河。

1798年，数学家“勒让德”创立了“勒让德符号”函数，高斯用“二次互反律”漂亮地解决了“勒让德符号”的计算问题，进而完美地解决了”二次剩余”的判别问题（只能提供判别，对于“二次同余方程”的求解没有帮助。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章 整数的可除性1. 定义：设是给定的数，，若存在整数，使得则称整除，记作，并称是的一个约数，称是的一个倍数，如果不存在上述，则称不能整除 2性质：(1)若且，则(传递性质)；(2)若且，则即为某一整数倍数的整数之集关于加、减运算封闭。

若反复运用这一性质，易知及，则对于任意的整数有。

更一般，若都是的倍数，则。

或着，则其中；(3)若，则或者，或者，因此若且，则； (4)互质，若，则；(5)是质数，若，则能整除中的某一个；特别地，若b a ,0≠bc bc a =b a a b |b a a b c b a c b |a c |a b |a b |c b |)(|c a b ±a b |c b |v u ,)(|cv au b ±n a a a ,,,21 b )(|21n a a a b +++ i b a |∑=ni ii b c a 1|n i Z c i ,,2,1, =∈a b |0=a ||||b a ≥a b |b a |b a ±=b a ,c b c a |,|c ab |p n a a a p 21|p n a a a ,,,21是质数，若，则；(6)(带余数除法)设为整数，，则存在整数和，使得，其中，并且和由上述条件唯一确定；整数被称为被除得的(不完全)商，数称为被除得的余数。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章 整数的可除性1. 定义：设是给定的数，，若存在整数，使得则称整除，记作，并称是的一个约数，称是的一个倍数，如果不存在上述，则称不能整除 2性质：(1)若且，则(传递性质)；(2)若且，则即为某一整数倍数的整数之集关于加、减运算封闭。

若反复运用这一性质，易知及，则对于任意的整数有。

更一般，若都是的倍数，则。

或着，则其中；(3)若，则或者，或者，因此若且，则； (4)互质，若，则；(5)是质数，若，则能整除中的某一个；特别地，若b a ,0≠bc bc a =b a a b |b a a b c b a c b |a c |a b |a b |c b |)(|c a b ±a b |c b |v u ,)(|cv au b ±n a a a ,,,21 b )(|21n a a a b +++ i b a |∑=ni ii b c a 1|n i Z c i ,,2,1, =∈a b |0=a ||||b a ≥a b |b a |b a ±=b a ,c b c a |,|c ab |p n a a a p 21|p n a a a ,,,21是质数，若，则；(6)(带余数除法)设为整数，，则存在整数和，使得，其中，并且和由上述条件唯一确定；整数被称为被除得的(不完全)商，数称为被除得的余数。

《初等数论》教学大纲Elementary number theory一、本大纲适用专业数学与应用数学.二、课程性质与目的1. 课程目标初等数论是数学与应用数学专业一门专业选修课.通过这门课的学习,使学生获得关于整数的整除、不定方程、同余、原根与指数的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的实际工作打下良好基础。

2。

与其它课程的关系本课程是初等数学研究、C语言程序设计A，近世代数等课程的后续课程.3. 开设学期按培养方案规定的学期开设。

三、教学方式及学时分配四、教学内容、重点第一章整数的可除性1. 教学目标理解整数整除的概念、最大公约数的概念、最小公倍数的概念,掌握带余除法与辗转相除法；理解素数与合数的概念;理解和掌握素数的性质、整数关于素数的分解定理、素数的求法；掌握函数［x]和｛x} 的性质。

2. 教学内容(1）整数整除、剩余定理：带余除法与辗转相除法；最大公约数的概念、性质及求最大公约数的方法；最小公倍数的概念、性质及最小公倍数的求法。

(2）素数与合数：素数与合数的概念、素数的性质、整数关于素数的分解定理、素数的求法;函数[x] ｛x} 的性质及其应用。

3。

教学方法讲解教学。

4。

本章重点辗转相除法，整数的素数分解定理。

5。

本章难点求最大公因子的方法.第二章不定方程1. 教学目标理解不定方程的概念，理解和掌握元不定方程有整数解的条件，会求一次不定方程的解。

2. 教学内容（1）一次不定方程，多元一次不定方程的形式，多元一次不定方程有解条件,求简单的多元一次不定方程的解。

(2) 二元一次不定方程有整数解的条件,求一次不定方程的解.3. 教学方法讲解教学。

4。

本章重点多元一次不定方程有解条件，二元一次不定方程有整数解的条件。

5. 本章难点不定方程的整数解的形式，求多元不定方程的整数解。

第三章同余、同余式1. 教学目标理解整数同余的概念，理解和掌握同余的基本性质、整数具有素因子的条件函数相关性质；理解剩余类与完全剩余系的概念，理解欧拉函数的定义及性质；掌握欧拉定理、费马定理、孙子定理.2. 教学内容（1）整数同余:整数同余的概念、同余的基本性质；整数具有素因子的条件；利用同余简单验证整数乘积运算的结果。

3
知
s
l
时
a
a
三 1 ( m
2时
,
二 i ( m
d 4
.
二
,
3
,
时
’
,
二 z
( mo d
,
)
.
<
a
(
m
o
一 d pi
为p
:
p
:
,
p
,
_
剩余平 方
, ,
由2 知
a
:
上 、
。
,
瓜 x r
i 为 p孚 的平方 剩余
人
,
从而
3
。
x
Z
二
a
a `
) 有解
三
i
气
m
0 Q
Pi
夕
=
1
,
2
,
“
`
,
k
.
,
根据
二
r
a
为
2仪
.
)
a
,
即
m )
,
r
+
2 适合
二
。
( m
d
因此
a
对 a 也 成立 证 完
.
.
(
二
1,
m
二
=
Za
p
:
a
`
p
:
“
2
… Pk
;
仪
k
二
.
为 m 的 平方 剩余 (
,
一
a
,
p k
的平方 剩余
m
o

余xuan定理余玄定理是数论中一个重要的定理，以法国数学家余玄（Adrien-Marie Legendre）命名。

这个定理是关于平方剩余的性质的，它在数论中有着广泛的应用。

本文将介绍余玄定理的概念，以及它在数论中的具体应用。

余玄定理是关于平方剩余的性质的一个定理。

在数论中，平方剩余是指一个数除以一个素数后的余数是该素数的一个平方数。

例如，对于素数p，如果存在整数x，使得x² ≡ a (mod p)，其中a是一个整数，那么a被称为模p的平方剩余。

否则，a被称为模p的非平方剩余。

余玄定理给出了判断一个数是否是模p的平方剩余的方法。

具体来说，如果p是一个奇素数，x是任意整数，那么存在一个整数y，使得y² ≡ x (mod p)成立的充分必要条件是x^((p-1)/2) ≡ 1 (mod p)。

根据余玄定理的性质，可以推导出一些重要的结论。

首先，根据费马小定理（Fermat's Little Theorem），如果p是一个素数，那么对于任意整数a，a^(p-1) ≡ 1 (mod p)成立。

根据余玄定理，可以推导出如果a是p的平方剩余，那么a^((p-1)/2) ≡ 1 (mod p)；如果a是p的非平方剩余，那么a^((p-1)/2) ≡ -1 (mod p)。

这个结论在数论中的应用非常广泛。

余玄定理还与二次互反律（Law of Quadratic Reciprocity）密切相关。

二次互反律是一个关于两个不同素数p和q的交换平方剩余的定理。

根据二次互反律，如果p和q是不同的奇素数，那么p模q的平方剩余与q模p的平方剩余有相同的数量。

余玄定理可以推广为二次互反律的一个特殊情况，即当一个素数是4k+1形式时，其平方剩余的数量比非平方剩余的数量多。

除了在数论中的应用，余玄定理还有着其他数学领域的应用。

例如，在密码学中，余玄定理被用于构造安全的公钥密码算法。

其原理是基于模p的平方剩余的性质来实现加密和解密的过程。