下载文档原格式
初等数论初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。
第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++Λ2211 勾股数 费尔马大定理。
习题要求29p ：1，2，4；31p ：2，3。
第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。
第四章：同余式（方程）（4学时）自学12学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。
习题要求60p ：1；64p ：1，2；69p ：1，2。
第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、素数模同余方程的解法习题要求78p ：2； 81p ：1，2，3；85p ：1，2；89p ：2；93p ：1。
第六章：原根与指标（2学时）自学8学时指数的定义及基本性质 原根存在的条件 指标及n 次乘余 模2 及合数模指标组、 特征函数习题要求123p ：3。
➢ 第一章 整除 一、主要内容筛法、[x]和{x}的性质、n ！的标准分解式。
二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。
认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。
《初等数论》总结姓名 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-=-=-，然后用公式写出一切解。
第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++ 是m 得倍数．证明： 12,,n a a a 都是m 的倍数。
∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n n q a q a q a ∴+++ 1122n n q p m q p m q p m =+++ 1122()n n p q q p q p m =+++即1122n n q a q a q a +++ 是m 的整数 2．证明 3|(1)(21)n n n ++ 证明 (1)(21)(1)(2n n n n n n n ++=+++-(1)(2)(1)(n n n n n n =+++-+又(1)(2)n n n ++ ，(1)(2)n n n -+是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证： ,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？证：作序列33,,,,0,,,,2222b b b bb b --- 则a 必在此序列的某两项之间 即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t < ()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b ---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b rq r -=，┄, d '|21(,)n n n n r r q r a b --=+=, 即d '是(,)a b 的因数。
第二章不定方程二元一次不定方程中国古代数学家张丘建在《张丘建算经》中解答了下面的题目：“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。
百钱买百鸡，问鸡翁母雏各几何？”设，，分别代表鸡翁、鸡母、鸡雏的数目，就可得到下面的方程组消去，再化简，即得（*）像（*）这种含有未知数的个数大于1的方程就是不定方程。
在数论中我们主要讨论（*）这种不定方程的整数解。
因由高等代数的知识我们知道在实数或复数范围内（*）总是有解的，但一个整系数不定方程不一定有整数解，比如就无整数解。
二元一次不定方程的一般形式本部分讨论二元一次不定方程，其一般形式为：（１）其中，，是整数，，不为零，，为未知量。
对二元一次不定方程（1），我们主要讨论它有整数解的判别条件，以及在它有整数解时，如何求出它的全部整数解。
二元一次不定方程有整数解的判别定理1二元一次不定方程（1）有整数解的充要条件是。
证若（1）有整数解，设为，则但，，因而，必要性得证。
反之，若，则，为整数。
由最大公因式的性质，存在两个整数，满足下列等式于是。
令，则，故为（1）的整数解，从而（1）有整数解二元一次不定方程的解法定理2设二元一次不定方程（1）有整数解，是其中一个整数解，又设，则（1）的一切整数解可表成（２）其中。
证因是（1）的解，故有，因此，这说明（2）是（1）的整数解。
设是（1）的任一整数解，则，从此式减去得将，代入上式，移项并消去（注意)，得到又，故。
由整除的性质知，所以存在整数使，亦即。
将代入即得。
故可表成（2）的形状。
由上面两方面的证明知（2）表示（1）的一切整数解。
给定二元一次不定方程（1），可先由定理（1）判别其是否有整数解，在有整数解时，由定理2，要先求出其一特殊解，再用公式（2）即可写出其一切整数解的表达式，即所谓通解。
下面重点讨论(1)的特解（即一个固定解）的求法。
由定理1的证明知，只须求出整数，使，则即为（1）的一个解。
为求，我们先用最大公因数的计算方法—辗转相除法，求出各个商，最后一个商不要，按下表排列，并按所给式子计算出。
第二章不定方程例题分析例1：利用整数分离系数法求得不定方程15x +10y +6z =61。
解：注意到z 的系数最小，把原方程化为z =)()(12361102261101561++-++--=+--y x y x y x 令t 1=z y x ∈++-)(12361，即-3x +2y -6t 1+1=0此时y 系数最小，)()(12131632111-++=-++=∴x t x t x y 令t 2=z x ∈-)(121,即122+=t x ,反推依次可解得y =x +3t 1+t 2=2t 2+1+3t 1+t 2=1+3t 1+3t 2z =-2x -2y +10+t 1=6-5t 1+10t 2∴原不定方程解为⎪⎩⎪⎨⎧--=++=+=21212105633121t t z t t y t x t 1t 2∈z.例2:证明2是无理数证：假设2是有理数，则存在自数数a,b 使得满足222y x =即222b a =，容易知道a 是偶数，设a =2a 1，代入得2122a b =,又得到b 为偶数，a b a <<1，设12b b =，则21212b a =,这里12a b <这样可以进一步求得a 2，b 2…且有a>b>a 1>b 1>a 2>b 2>…但是自然数无穷递降是不可能的，于是产生了矛盾，∴2为无理数。
例3：证明：整数勾股形的勾股中至少一个是3的倍数。
证：设N =3m ±1(m 为整数)，∴N 2=9m 2±6m +1=3(3m 2±2m )+1即一个整数若不是3的倍数，则其平方为3k +1,或者说3k +2不可能是平方数，设x,y 为勾股整数，且x,y 都不是3的倍数，则x 2,y 2都是3k +1，但z 2=x 2+y 2=3k +2形，这是不可能，∴勾股数中至少有一个是3的倍数。
例4：求x 2+y 2=328的正整数解解：∵328为偶数，∴x,y 奇偶性相同，即x ±y 为偶数，设x+y =2u ,x -y =2v ，代入原方程即为u 2+v 2=164,同理令u +v =2u 1,u -v =2v 1有21121121212282v v u u v u v u =-=+=+,,,412222=+v u 22v u ,为一偶一奇，且0<u 2<6u 2=1，2，3，4，5代方程，有解（4，5）（5，4）∴原方程解x =18,y =2,或x =2,y =18。
第二章 不定方程数学中的许多问题都可以产生不定方程，如张丘建的“百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁母雏各几何？设鸡翁、鸡母、鸡雏各有x , y , z 只，根据题意可得下面方程⎪⎩⎪⎨⎧=++=++1001003135z y x z y x 消去z ，可得7x +4y =100 ，于是百鸡问题就化为上述方程求非负整数解的问题。
§1 一次不定方程都不等于零。
可以假定并且不失一般性地我们，，其中式为一次不定方程的一般形n n n n a a a n Z N a a a N x a x a x a ,,,)1(2,,,,21212211 ≥∈=+++有整数解。
的整线性组合，即是可知节定理的倍数，由第一章第二是，则若”“。
，即则，使得式有解，即有若”“。
件是有整数解的充分必要条的整数，是全不为零，其中不定方程)1(,,,4|),,,(||),,,(,,,)1(|),,,(2,,,212122112122112121212211n n n n n n n n n n n n a a a N d N N a a a N d x a x a x a a a a d Nx a x a x a Z x x x N a a a n a a a N x a x a x a ⇐'++'+'∆='++'+'∈'''⇒≥=+++证明定理1。
，，为的全部整数解（通解），则方程的一个整数解（特解）是不定方程，，，，设Z t t b a a y y t b a b x x c by ax y y x x c b a b a Z c b a ∈-=+==+==≠≠∈),(),()2()2(,|),(00,,00002定理，于是有的解，所以是因为c by ax y x =+0000)2(,证明的全部整数解。
表示，因此，，代入上式，得，将，也即即，，故，又于是，，得，两边除以，得到，减去的任一解，则是设的解。
是，表明)2(),(),(),(),(),()(|),(1)),(,),(()(),(|),()(),()(),(),(0)()()2(,)2(),(),()),(),(()),(()),((00000000000000000t b a a y y t b a b x x t b a a y y x t b a b x x t b a b x x x x b a b b a b b a a x x b a a b a b y y b a b x x b a a b a y y b x x a c by ax c y b x a y x t b a a y y t b a b x x c t b a ba b a ab c t b a a y b t b a b x a -='+='-=''+='=-'-'=-'-'-=-'=-'+-'=+='+'''-=+==-+=-++ 辗转相除。
一个特解。
求解的关键是求方程的就得到了，因此，解，那么方程的通解也可知，只要求得一个特由定理−−−−−→−=+−→−=+−−→−=+=1)),(,),((|),(1),(),(),(),(),(2b a b b a a c b a y b a b x b a a b a c y b a b x b a a c by ax 法二元一次不定方程的解 。
，，因此，方程的通解为，为从而原方程的一个特解），（其实通过观察也可得的一个整数解为故）（，的一个整数解。
适合求出下面先通过辗转相除法，所以方程有整数解。
因为的通解。
求Z t t y t x y x y x y x r r q b a q y x y x ∈-=+-==-==-==+⨯+-=--=-========+==+72004100200,1002,114742747434113341471147100|1)4,7(10047001010解例1。
，，，从而得到四组解：，，故，于是，回到百鸡问题，则要求⎪⎩⎪⎨⎧===⎪⎩⎪⎨⎧===⎪⎩⎪⎨⎧===⎪⎩⎪⎨⎧====≤≤≥≥8441281118781847525028,27,26,2572002500z y x z y x z y x z y x t t y x。
，因此，原方程的通解为，，从而原方程的特解为，，的一个整数解为故，的特解先通过辗转相除法求同解。
方程，所以方程有解，且与因为的通解。
求Z t tt y t t x y x y x y x y x y x y x ∈--=-⨯-=--=-⨯-=⨯-=⨯-==-==+⨯+⨯-=⨯-⨯+⨯-=⨯+⨯-=-⨯-=⨯-==+=-==-3733725910781072526259252692611073710793726)372107(9378339378)3337(83348331132433833741371072,110737251073775|3)321,111(7532111100解例2即可。
通解，然后消去常数，求出各个方程的看成中，我们可以把当然，在实际求解过程的通解。
，最后得出出上面一些方程的通解通解，然后代入依次求先求出最后一个方程的有解。
作方程时，，则当，，，先顺次求出i n n n n i n n n n t N x a t d t t d x a t d t d x a x a N d d a d d a d d a a =+=+=+===---113333222222111332221)1()1(|),(),(),(法多元一次不定方程的解100053)83(32491000|1)5,3(3)24,9(10005249=-=+=+=-==-+z t t y x t y x z y x ，考虑方程，所以方程有解。
，因为的通解。
求解例3。
，，得消去，，，解得Z v u v z v u y v u x t Z v u v z v t u t y u t x ∈⎪⎩⎪⎨⎧-=+--=-+=∈⎩⎨⎧-=-=⎩⎨⎧--=+=,310005320001586000,3100052000383 习题：P29，1、4。
；方程的通解补充习题：求下列不定2315206)2(1032)1(=-+=++z y x z y x§2 勾股数该方程的全部整数解。
组整数解，本节将求出的很多已经知道了不定方程，由此可知，我国古代，，，年）又载有刘徽九章注（。
，，：上给出了方程的一组解修四、径隅五”。
事实有记载：“句广三、股中已国古代的《周髀算经》的一个直角三角形。
我于存在三边长为整数相当，方程的一组正整数解次不定方程本节研究一种特殊的二222222222222222222292120252471715813125263543,,z y x z y x z y x =+=+=+=+=+=+，故矛盾。
要么要么，但，从而，矛盾，若全为奇数，则全为偶数，则与必然一奇一偶，否则若是偶数。
因为、假定。
由它可以求得也是方程的一组解，而，则，，，令，则，称为本原解。
因为若、假设。
求出它的全部正整数解零解，只需包含零。
而要求全部非，此外的每一组解都不，；，；，，。
因为方程显然有解，，、假定作一些约定：首先对二次不定方程1442)(414141),(,3,,,,|),(1),(200000000122222222+++=++=+==''''='='===±==±=====>>>=+N N z n m y x n y m x y x y x x z y x z y x z d z y d y x d x z d d y x y x z x y z y x z y x z y x z y x 下面我们求出满足三个约定的全部整数解。
式。
满足，，，，，很显然，。
，，，，，，从而故，，，，又，矛盾，故的定义及这与，，于是，满足，则有一质数，若可得代入，，设，因而，从而，故又，，，于是，外），则除（除不再被任何数的平方整，其中，，，的一解，令是设。
，，，，，成公式的全部正整数解可以写，，，，不定方程)1(1),(00)2(1),(001000111),(,||1)1(|1),(1),(1),(||||1,00)1(,,)1(1),(00)1(1),(0002222111111112111111122122121111222222111212222=>>====>>======>>>===≠=====>>===>>====>>>=b a b a ab w b v a u b a b a ab w b v a u v u w v u w v u w v u v u v u p w p p w w v u abw w w ab b a b a v u w b w a w b w a v u b a v b v u a u w v u b a b a ab w b v a u v u v u w w uv 证明引理。
为奇数可知，再由或，从而，故又因，，从而，，于是，，则设，，，，，，因为一奇一偶。
是奇数，可知，由可得而且由，，，，，，即，，，，，使得由引理，有整数），故，于是，，则（因为若，，其中都是奇数，而且故，，的解，由于是适合条件的不定方程设一奇一偶。
，，，，，下面公式来表示：的全部正整数解可以用，，，，的适合条件不定方程1211),(1),(),(2|||||),(|2|2000)()()2()2(,01),(0021),(00222,1|||)2,2(1)2,2(22)2(,1),(|2,,)1(,1),(02|21),(0002222222222222222222222222222222====-+=/>>>+=-+>>=>>+=-===>>==-=+==-+=-+-⋅+===>>+=-===>>>=+d y d b a b a b a d b a d b a d z d z d y x d y x z y x b a b a ab b a y b a y b a b a b a z b a y ab x b a b a ab x b y z a y z b a d x d y d z d d y z y z y z y z y z y z x z y y x x z y x b a b a b a b a z b a y ab x x y x z y x z y x 证明定理号可以任意取。
