1、1 初等数论学习总结 本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系 (特别是师范院校 )的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。 最后，给大家提一点数论的学习方法，即一 定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意
2、到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。 数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。 初等数论自学安排 第一章：整数的可除性（ 6 学时）自学 18 学时 整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理 x和 x的性质及其在数论中的应 用 习题要求 3p ： 2， 3 ； 8p ： 4 ； 12p ： 1； 17p ： 1， 2， 5； 20p ： 1。 第二章：不定方程（ 4 学时）自学 12 学时 二元一次
3、不定方程 cbyax 多元一次不定方程 cxaxaxa nn 2211 勾股数 费尔马大定理。 习题要求 29p ： 1， 2， 4； 31p ： 2， 3。 2 第三章：同余（ 4 学时）自学 12 学时 同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系 欧拉定理、费尔马小定理及在循环小数中的应用 习题要求 43p ： 2， 6； 46p ： 1； 49p ： 2， 3； 53p 1， 2。 第四章：同余式（方程）（ 4 学时）自学 12 学时 同余方程概念 孙子定理 高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。 习题要求 60p ： 1； 64p ： 1， 2； 69
4、p ： 1， 2。 第五章： 二次 同余式和平方 剩余 （ 4 学时）自学 12 学时 二次同余式 单素数的平方剩余与平方非剩余 勒 让德符号 二次互反律 雅可比符号、 素数模同余方程的解法 习题要求 78p ： 2； 81p ： 1， 2， 3； 85p ： 1， 2； 89p ： 2； 93p ： 1。 第一章： 原根与指标 （ 2 学时）自学 8 学时 指数的定义及基本性质 原根存在的条件 指标及 n次乘余 模 2 及合数模指标组、 3 特征函数 习题要求 123p ： 3。 第一章 整除 一、主要内容 整除的定义、 带余除法定理 、余数、最大公因数、最小公倍数、辗转 相除法、互素、两两
5、互素、素数、合数、 算术基本定理 、 Eratosthesen 筛法 、 x和 x的性质 、 n！的标准分解式 。 二、 基本要求 通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中 二个著名的定理：带余除法定理和算术基本定理 。认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。能熟练求出二个整数的最大公因数和最小公倍数，掌握高斯函数 x的性质及其应用。 三、重点和难点 （ 1）素数以及它有关的性质，判别正整数 a 为素数的方法，算术基本定理及其应用。 （ 2）
6、素数有无穷多个的证明方法。 （ 3）整除性问题的若干解决方法。 （ 4） x的性质及其应用， n！的标准分解式。 四、自学指导 整除是初等数论中最基本的概念之一， b a 的意思是存在一个整数 q，使得等式 a=bq成立。因此这一标准作为我们讨论整除性质的基础。也为我们提供了解决整除问题的方法。即当我们无法用整除语言来叙述或讨论整除问题时，可以将其转化为我们很熟悉的等号问题。 对于整除的若干性质，最主要的性质为传递性和线性组合性，即 （ 1） a b, b c, 则有 a c 4 （ 2） a b, a c, 则有 a mb+nc 读者要熟练掌握并能灵活应用。特别要注意，数论的研究对象是整数集
7、合，比小学数学中非负整数集合要大。 本章中最重要的定理之一为 带余除法定理 ，即为 设 a 是整数， b 是非零整数，则存在两个整数 q， r，使得 a=bq+r （ 0 br ） 它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性，（即当余数 r=0时）。 带余除法可以将全体整数进行分类，从而可将 无限的问题 转化为有限的问题 。这是一种很重要的思想方法，它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了基础。读者应熟知常用的分类方法，例如把整数可分成奇数和偶数，特别对素数的分类方法。例全体奇素数可以分成 4k+1， 4k+3；或 6k+1， 6k+5 等类
8、型。 和整除性一样，二个数的最大公约数实质上也是用等号来定义的，因此在解决此类问题时若有必要可化为等式问题， 最大公因数的性质中最重要的性质之一为 a=bq+c，则一定有（ a， b） =（ b， c），就是求二个整数的最大公约数的理论根据 。也是解决关于最大公 约数问题的常用方法之一。读者应有尽有认真体会该定理的证明过程。 互素与两两互素 是二个不同的概念，既有联系，又有区别。要认真体会这些相关的性质，例如，对于 任意 a ,b Z，可设（ a ,b） =d，则 a=da1 ,b=db1，则（ a1 ,b1） =1，于是可对 a1 ,b1使用相应的定理，要注意，相关定理及推论中互素的条件是经
9、常出现的。读者必须注意定理成立的条件，也可以例举反例来进行说明以加深影响。顺便指出，若 a c， b c，（ a ,b）=1，则 ab c 是我们解决当除数为合数时的一种方法 。好处是不言而喻的。 最小公倍 数实际上与最大公因数为对偶命题。特别要指出的是 a和 b 的公倍数是有无穷多个。所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数中的最小的正整数。这一点实际上是应用 自然数的最小自然数原理 ，即自然数的任何一个子集一定有一个最小自然数有在。 最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题 。两者的关系为 5 a ,b N， a ,b= baab,上述仅
10、对二个正整数时成立 。当个数大于 2 时，上述式子不再成立。证明这一式子的关键是寻找 a , b 的所有 公倍数的形式，然后从中找一个最小的正整数。 解决了两个数的 最小公倍数与最大公因数问题后，就可以 求出 n 个数的 最小公倍数与最大公因数问题，可以两个两个地 求 。即有下面定理 设 naaa , 21 是 n 个整数， ,),( 221 daa ,),( 332 dad ,),( 1 nnn dad 则（ naaa , 21 ）= ,nd 设 , 221 maa ,),( 332 mam ,),( 1 nnn mam 则有 naaa , 21 = ,nm 素数是数论研究的核心，许多中外闻
11、名的题目都与素数有关。除 1 外任何正整数不是质数即为合数。判断一个已知的正整数是否为质数可用判别定理去实现。判别定理又是证明素数无穷的关键。实际上，对于任何正整数 n1，由判别定理一定知存在素数 p，使得 p n 。即 任何大于 1 的整数一定存在一个素因数 p 。素数有几个属于内在本身的性质， 这些性质是在独有的，读者可以用反例来证明： 素数这一条件必不可少。以加深对它们的理解。 其中 p abp a 或 p b 也是常用的性质之一 。也是证明算术基本定理的基础 。 算术基本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘积，而且分解是唯一的，不是任何数集都能满足算术基
12、本定理的，算术基本定理为我们提供了解决其它问题的理论保障。它有许多应用，由算术基本定理我们可以得到 自然数的标准分解问题 。 设 a= kkpp .11 ， b= kkpp .11 ， 0,0 ii 则有 （ a， b） = kkpp .11 ),min( iii a， b= kkpp .11 maxi ),( ii 例如可求最大公约数，正整数正约数的个数等方面问题，对具体的 n，真正去分解是件不容易的事。对于较特殊的 n，例如 n！分解还是容易的。应用 x的 性质， n！的标准分解式可由一个具体的公式表示出来 ，这一公式结合 x的性质又提供了解决带有乘除符号的整6 除问题的方法。 本章的许多
13、问题都围绕着整除而展开，读者应对整除问题的解决方法作一简单的小结。 五、例子选讲 补充知识 最小自然数原理：自然数的任意非空子集中一定存在最小自然数。 抽屉原理： （ 1）设 n是一个自然数，有 n个盒子， n+1 个物体，把 n+1 个物体放进 n个盒子，至少有一个盒子放了两个或两个以上物体； （ 2） km+1 个元素，分成 k 组，至少有一组元素其个数大于或等于 m+1； （ 3）无限个元素分成有限 组，至少有一组其元素个数为无限。 梅森数：形如 2n-1 的数叫梅森数，记成 Mn=2n-1。 费尔马数： n 为非负整数，形如 122 n 的数叫费尔马数，记成 Fn= 122 n 。 设
14、 n= kkpp .11 ，设 n 的正因子个数为 d(n)，所有正因子之和为 )(n ，则有 ).()()( 111 21 knd 1 11 11 11212111 21 kkPpPpPpn k .)( 有关技巧 1. 整数表 示 a=a010n+a110n-1+ an， a=2kb(b 为奇数 ) 2.整除的常用方法 a. 用定义 b. 对整数按被 n 除的余数分类讨论 c. 连续 n 个整数的积一定是 n 的倍数 d. 因式分解 an-bn=(a-b)M1, an+bn=(a+b)M2, 2 n e. 用数学归纳法 7 f. 要证明 a|b，只要证明对任意素数 p， a 中 p 的幂指数
15、不超过 b 中 p 的幂指数即可，用 p(a)表示 a 中 p 的幂指数，则 a|b p(a) p(b) 例题选讲 例 1.请写出 10 个连续正整数都是合数 . 解 : 11!+2， 11!+3， 11！ +11。 例 2. 证明连续三个整数中，必有一个被 3 整除。 证：设三个连续正数为 a， a+1， a+2，而 a 只有 3k， 3k+1， 3k+2 三种情况，令 a=3k，显然成立， a=3k+1 时， a+2=3(k+1)， a=3k+2 时， a+1=3(k+1)。 例 3. 证明 lg2 是无理数。 证：假设 lg2 是有理数，则存在二个正整数 p， q，使得 lg2=qp，由
16、对数定 义可得 10p =2q ，则有 2p 5 p =2q ,则同一个数左边含因子 5，右边不含因子 5，与算术基本定理矛盾。 lg2为无理数。 例 4. 求 (21n+4， 14n+3) 解：原式 =(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1 例 5. 求 2004!末尾零的个数。 解：因为 10=2 5，而 2 比 5 多， 所以只要考虑 2004！中 5 的幂指数，即 5（ 2004！） = 4995200452004125200425200452004 54 例 6.证明（ n!） (n-1)!|(n!)! 证：对任意素数 p,
17、设（ n!） (n-1)!中素数 p 的指数为 ， （ n!） !中 p 的指数 ，则 8 11 k kpnn )!( ， 11 k kpnn !)!( , )()( xnnx 1111 111 k kk kk kk k pnnpnnpnnpn !)!(!)!()!(! 即 ，即左边整除右边。 例 7. 证明 2003|（ 20022002+20042004-2005） 证： 20022002=（ 2003-1） 2002=2003M1+1 20042004=（ 2003+1） 2002=2003M2+1 20022002+20042004-2005=2003（ M1+M2-1） 由定义 20
18、03|（ 20022002+20042004-2005） 例 8. 设 d(n)为 n 的正因子的个数， (n)为 n 的所有正因子之和，求 d(1000)， (1000)。 解： 1000=23 53 d(1000)=(3+1)(3+1)=16， (1000)=15 1512 12 44 例 9. 设 c 不能被素数平方整除，若 a2|b2c，则 a|b 证：由已知 p(c) 1，且 p(a2) p(b2c) 2p(a) 2p(b)+p(c) , p(a) p(b)+2)(cp即 p(a) p(b) , a|b 例 10. 若 Mn 为素数，则 n 一定为素数。 证：若 n 为合数，则设 n
19、=ab，（ 1m，则 Fn-2=（ 12 12 n ）（ 12 12 n ） =(Fn-1-2) （ 12 12 n ） 9 = Fn-1Fn-2 Fm- F0 设（ Fn,Fm） =d,则 d|Fn, d|Fm d|2 但 Fn 为奇数， d=1, 即证。 例 12. 设 m,n 是正整数。证明 ( , )( 2 1, 2 1) 2 1m n m n 证 : 不妨设 nm 。 由带余数除法得 ,11 rnqm .nr10 我们有 12122122212 1111111 rnqrrrrnqm )( 由此及 1212 1 nqn | 得 , ),( 1212 nm = ),( 1212 1 rn
20、 注意到 ),(),( 1rnnm ,若 01r ,则 nnm ),( ,结论成立 .若 01r ,则继续对 ),( 1212 1 rn 作同样的讨论，由辗转相除法知，结论成立。显见， 2 用任一大于 1 的自然 a 代替，结论都成 立。 例 13. 证明：对任意的正整数 n ，成立如下不等式 2lglg kn 。 其中 nlg 是数 n 的以 10 为底的对数， k 是 n 的不同的素因数（正的）的个数。 证：设 n 是大于 1 的整数（如果 n =1，上述不等式显然成立，因 k =0）， kppp ,., , 21 是 n 的 k 个相异的素因素。 n 的素因数分解式为 klkll ppp
21、n .21 21 .( kili ,., 211 ) , 由于 ),.,(, kipi 212 ， 从而 kkk lllllllkll pppn . . . 212121 222221 ， 而 klll k .21 ，故 kn 2 。 将上述不等式取对数（设底 1a ） ,则有 2aa kn loglog 。 特别有 2lglg kn 。 例 14. 试证明任意一个整数与它的数字和的差必能被 9 整除，并且它与它的数字作任意调后10 换后所成整数的差也能被 9 整除。 证： 设整数 m的个位、十位、百位的数字分别为 1a , 2a ， na ，则 m 可表作： nn aaaam 1321 10
22、1 0 010 . ).().( nnn aaaaaaa 个132321 999999 ).().( nnn aaaaaaa 个132321 111119 所以 ).( naaaam 321 ).( nn aaa 个132 111119 因为 2a ， 3a ,， na 都是整数，所以任一整数与其数字之和的差必能被 9 整除。 再设将 1a , 2a ， na 按任一种顺序排成 1a , 2a ， na ，并令 naaa .21 ， naaa . 21 ， nn aaam 121 1010 .， nn aaam . 121 1010 。 根据前面证明的结果，知存在整数 A， B，使 ., Bm
23、Am 99 因为 ，所以 )( BABAmm 999 。 由于 A-B 是整数，这就证明了 mm 能被 9 整除。 注：若对某个整数 )( nkk 1 ，有 0ka ，但当 nik 时， 0ia ，则此时 m 为整数： ,. kk aaam 121 1010 即 12 . aam k 。 如前证，此时结论正确。又当 m 为负整数及零时，结论显然正确。 第二章 不定方程 一、 主要内容 一次不定方程有解的条件、解数、解法、通解表示，不定方程 x2+y2=z2 通解公式、无穷递降法、费尔马大定理。 二、 基本要求 1、 了解不定方 程的概念，理解对“解”的认识，掌握一次不定方程 cbyax 有解的条件，能熟练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程
