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

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

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

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

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

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

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

或着，则其中；(3)若，则或者，或者，因此若且，则； (4)互质，若，则；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 i i 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 |(5)是质数，若，则能整除中的某一个；特别地，若是质数，若，则；(6)(带余数除法)设为整数，，则存在整数和，使得，其中，并且和由上述条件唯一确定；整数被称为被除得的(不完全)商，数称为被除得的余数。

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

若，即为被整除的情形；易知，带余除法中的商实际上为（不超过的最大整数），而带余除法的核心是关于余数的不等式：。

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

i q 为a,b 作辗转相除时不完全商（3）整数分离法：当a,b 中系数不同时，用绝对值较小的系数后的变量表示另一个变量，通过变量替换得到一个新的不定方程。

如此反复，直到一个参数的系数为1，而得到不定方程的解。

（4）化为同余方程|)|(mod b c ax ≡ 4.多元一次不定方程（1）定义：形如)2(2211≥=++n c x a x a x a n n 的不定方程多元一次不定方程（2）定理：)2(2211≥=++n c x a x a x a n n 有解的充要条件是(x 1，x 2，…x x )|x （3）解法：设n n n d a d d a d d a a ===-),(,),(,),(1332221 ，则)2(2211≥=++n c x a x a x a n n 等价于方程组cx a t d t d x a t d t d x a x a n n n n =+=+=+--11333322222211,,先解最后一个方程的解，得n n x t ,1-然后把其代入倒数第二个方程求得一切解，如此向上重复进行，求得所有方程的解 5．勾股数定义：一般地称x 2+y 2=z 2的正整数解为勾股数定理：在条件x>0，y>0，z>0，（x ，y ）=1，2∣x 的条件下x 2+y 2=z 2的通解公式为 x=2ab ，y=a 2-b 2，z 2=a 2+b 2，a>b>0 , (a ,b)=1，a ,b 一奇一偶第三章 同余1.定义：下列同余述是等价的 (1) a b (mod m )；(2) 存在整数q ，使得a = b qm ；(3) 存在整数q 1，q 2，使得a = q 1m r ，b = q 2m r ，0 r < m 2.性质：(1) (自反性) a a (mod m )；(2) (对称性) a b (mod m ) b a (mod m );(3) (传递性) a b ，b c (mod m ) a c (mod m )。

(4)设a ，b ，c ，d 是整数，并且a b (mod m )，c d (mod m )， 则(ⅰ) a c b d (mod m ) (ⅱ) ac bd (mod m )(5)设a i ，b i （0 i n ）以及x ，y 都是整数，并且x y (mod m )，a i b i (mod m )，0 i n ，则).(mod 0m y b x a ni i i niii ∑∑==≡3. 设m 是一个给定的正整数，()0,1,,1r K r m =-表示所有形如()0,1,2,qm r q +=±±的整数组成的集合，则称011,,,m K K K -为模m 的剩余类（1）设0110,,,,m m K K K ->是模m 的剩余类，则（ⅰ）每一整数必包含于某一个类里，而且只能包含于一个类里； （ⅱ）两个整数,x y 属于同一类的充分必要条件是()mod .x y m ≡ 4. 在模m 的剩余类011,,,m K K K -中，各取一数,0,1,,1j j a C j m ∈=-，此m个数011,,,m a a a -称为模m 的一个完全剩余系（m 个整数作成模m 的一个完全剩余系的充分必要条件是这m 个整数两两对模m 不同余）（1）设m 是一个正整数，,a b 都为整数，(),1a m =，若x 通过模m 的一个完全剩余系，则ax b +也通过模m 的一个完全剩余系（2）设()12120,0,,1m m m m >>=，而12,x x 分别通过模12,m m 的一个完全剩余系，则2112m x m x +通过模12m m 的一个完全剩余系5. 欧拉函数：φ(m )是1, 2, …, m 中与m 互质的个数，称为欧拉函数（1）欧拉函数值的计算公式：若m ＝p 11p22…pnn , 则φ(m )＝m (1－1p 1)(1－1p 2)…(1－1p n )，如30＝2·3·5，则.8)511)(311)(211(30)30(=---=ϕ （2）若p 为素数，则1()1,()(1),k k p p p p p ϕϕ-=-=-若p 为合数，则()2,p p ϕ≤-（3）不超过n 且与n 互质的所有正整数的和为1()2n n ϕ（4）若(,)1()()(),a b ab a b ϕϕϕ=⇒= 若()()a b a b ϕϕ⇒（5）设d 为n 的正约数，则不大于n 且与n 有最大公因数d 的正整数个数为()n dϕ， 同时()()d n d nnd n d ϕϕ==∑∑6.欧拉定理：若(a , m )＝1，则a φ(m )≡1(mod m )7.费马定理：若p 是素数，则a p ≡a (mod p ) 若另上条件(a ，p )＝1，则a p −1≡1(mod p )第四章 同余方程1.定义：设01)(a x a x a x f n n ++= ，+∈∈Z m Z a i ,，则)(mod 0)(m x f ≡叫做模m 的同余方程。

若)(mod 0m a n ≡，则称n 为同余方程的次数。

若)(mod 0)(m c f ≡，则)(mod m c x ≡称为同余式的解；模m 的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数注：对模m 互相同余的解是同一个解2.一次同余方程的一般形式为ax≡b(mod m)，)(mod 0/m a ≡，有解的充要条件是(a,m)|b,若有解则有d=(a,m)个关于模m 的解3.一次同余方程ax≡b(mod m)的解法 （1）化为不定方程ax+my=b（2）利用欧拉定理，若(a,m)=1,则有ax≡b(mod m),两边同乘1)(-m aϕ则有)(mod 1)()(m ba x a m m -≡ϕϕ，因为)(mod 1)(m a m ≡ϕ，因此)(mod 1)(m ba x m -≡ϕ（3）用形式分数当（a ，m ）=1时，若ab ≡1(modm)，则记b a1≡(modm)称为形式分数，根据定义和记号，)(mod 1m c a ac ≡有性质 (a)Z t t m mt a mt c a c∈++≡2121,),(mod (b) （d ，m ）=1，且11,dc c da a ==，则)(mod 11m aca c ≡利用形式分数的性质把分母变成1，从而求出一次同余式的解4.一次同余方程组的解法定义:如下(*)称为一次同余方程组 x≡b 1(mod m 1) x≡b 2(mod m 2)…… （*） x≡b k (mod m k )有解判定定理：同余方程组（*）有解的充要条件是j i b b m m j i j i ≠∀-,|),( 5.孙子定理：设k m m m ,,21，两两互素，则同余式(*)组的解为)(mod ,2,221,11i k k k m b M M b M M b M M x ++≡k m m m m 21=注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的 6.高次同余方程（1）定义：次数大于1的同余方程称为高次同余方程)(mod 0)(m x f ≡，01)(a x a x a x f n n ++=对一般模的高次同余方程我们要通过“小模”和“降次”的方法来得到一般模的高次同余方程的解（2）小模：即把一般模高次同等方程转化为一系列模两两互素的高次同余方程组注：因为k k p p p m ααα2121=，所以)(mod 0)(m x f ≡等价于同余方程组 k i p x f i i 2,1),(mod 0)(=≡α，即原方程可化为解)(mod 0)(αp x f ≡，而若x 是)(mod 0)(αp x f ≡的解，所以理论上只要解素数模)(mod 0)(p x f ≡同余方程即可（3）降次：设p 是素数，01)(a x a x a x f n n ++= ，是整系数多项式，设1x 是)(mod 0)(1-≡αp x f 的一个解，则有○1 )(mod 0)(1,p x f ≡则存在整数t 使得t p x x 11-+=α是)(mod 0)(αp x f ≡的解○2 )(mod 0)(1,p x f ≡且)(mod 0)(1αp x f ≡，则t p x x 11-+=α，当t=0，1，2，……P-1时，都是)(mod 0)(αp x f ≡的解 7.素数模同余方程)(mod 0)(p x f ≡ （*）定理：同余方程（*）或者有P 个解，或者与一个次数不超过p-1次的素数模同余方程等价（注意：同余方程（*）的解数不超过它的次数） （1）p 是素数，对任意的x 有)))(mod 1(()2)(1(11p p x x x x p ----≡-- （2）p 是素数，则有)(mod 01)!1(p p ≡+-（威尔逊定理）（3）,p n ≤同余方程（*）有n 个解的充要条件是存在q （x ）和r （x ），使得)()()(x pr x q x f x x p +=-，r(x)的次数小于n第五章 二次同余式和平方剩余1. 欧拉判别条件定义：m>0,(a,m)=1,若对于整数a ，)(mod 2m a x ≡有解，则称a 是模m 的平方乘余; 否则，称a 是模m 的平方非乘余 2. 欧拉判别定理：p>2,(a,p)=1,则有 (1)a 是模p 的平方乘余的充要条件是)(mod 121p ap ≡- (2)a 是模P 的平方非乘余充要条件是)(mod 121p ap -≡-(3)a 是模p 的平方乘余,则)(mod 2p a x ≡有两个解3.在模P 的简化系中，平方剩余和平方非剩余余各为21-p 个，且21-p 个平方乘余分别与22)21(,2,1-p 之一同余，而且仅与一数一同余4.勒让德符号：p 是一个给定的奇素数，对于整数a 定义勒让德符号⎪⎩⎪⎨⎧-=a p a a p a |,0是平方剩余,1是平方剩余,1)( 5. 勒让德符号的一些性质：(1) )(mod )(21p apap -≡(2) )()(),(mod p bp a p b a =⇒≡(3) )())(()(2121pap a p a p a a a k k = (4) 1)1(=p(5) ⎩⎨⎧+=-+==-=--34,114,1)1()1(21k p k p p p(6)二次互反律：设p ，q 是两个不同的奇素数，则有)()1()(2121qp pqq p -⋅--=6.雅可比符号：给定正奇数m=k p p p 21对任意的整数a 定义)())(()(21k p a p a p a ma =，称)(ma 为雅可比符号（注意：1、雅可比符号是勒让德符号 的推广；2、雅可比符号为1时，)(mod 2m a x ≡不一定有解；3、雅可比符号为-1时，则)(mod 2m a x ≡一定无解） 雅可比符号继承了勒让德符号的所有性质7. 合数模二次同余方程设P 是奇素数，（a ，p ）=1，则有（1）若)(pa =-1，则)(mod 2αp a x ≡无解 （2）若)(pa =1，则)(mod 2αp a x ≡有两解 8.若(a,2)=1，则（1）α=1时，)2(mod 2αa x ≡有一解（2）α=2时，)2(mod 2αa x ≡有解的的充要条件是a=4k+1，且若有解，则有两解（3）3≥α时，则)2(mod 2αa x ≡有解的充要条件是a=8k+1，且若有解，则有四解。