初等数论总复习

初等数论学习总结

本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的．一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的．正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。

最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排

第一章：整数的可除性（6学时）自学18学时

整除的定义、带余数除法 最大公因数和辗转相除法

整除的进一步性质和最小公倍数 素数、算术基本定理

[x]和{x}的性质及其在数论中的应用

习题要求p3：2，3 ； p8：4 ；p12：1；p17：1，2，5；p20：1。

第二章：不定方程（4学时）自学12学时

二元一次不定方程ax?by?c

多元一次不定方程a1x1?a2x2??anxn?c 勾股数

费尔马大定理。

习题要求p29：1，2，4；p31：2，3。

第三章：同余（4学时）自学12学时

同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系

欧拉定理、费尔马小定理及在循环小数中的应用

习题要求p43：2，6；p46：1；p49：2，3；p53 1，2。

第四章：同余式（方程）（4学时）自学12学时

同余方程概念 孙子定理

高次同余方程的解数和解法

素数模的同余方程 威尔逊定理。

习题要求p60：1；p64：1，2；p69：1，2。 第五章：二次同余式和平方剩余（4学时）自学12学时

二次同余式

单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、

素数模同余方程的解法

习题要求p78：2； p81：1，2，3；p85：1，2；p89：2；p93：1。 第一章：原根与指标（2学时）自学8学时

指数的定义及基本性质 原根存在的条件 指标及n次乘余

模2

?及合数模指标组、

特征函数

习题要求p123：3。

第一章 整除

一、主要内容

整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、Eratosthesen筛法、[x]和{x}的性质、n！的标准分解式。

二、基本要求

通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。能熟练求出二个整数的最大公因数和最小公倍数，掌握高斯函数[x]的性质及其应用。

三、重点和难点

（1）素数以及它有关的性质，判别正整数a为素数的方法，算术基本定理及其应用。 （2）素数有无穷多个的证明方法。 （3）整除性问题的若干解决方法。

（4）[x]的性质及其应用，n！的标准分解式。

四、自学指导

整除是初等数论中最基本的概念之一，b∣a的意思是存在一个整数q，使得等式a=bq成立。因此这一标准作为我们讨论整除性质的基础。也为我们提供了解决整除问题的方法。即当我们无法用整除语言来叙述或讨论整除问题时，可以将其转化为我们很熟悉的等号问题。

对于整除的若干性质，最主要的性质为传递性和线性组合性，即 （1） a∣b, b∣c, 则有a∣c （2） a∣b, a∣c, 则有a∣mb+nc 读者要熟练掌握并能灵活应用。特别要注意，数论的研究对象是整数集合，比小学数学中非负整数集合要大。

本章中最重要的定理之一为带余除法定理，即为 设a是整数，b是非零整数，则存在两个整数q，r，使得 a=bq+r （0?r?b） 它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性，（即当余数r=0时）。带余除法可以将全体整数进行分类，从而可将无限的问题转化为有限的问题。这是一种很重要的思想方法，它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了基础。读者应熟知常用的分类方法，例如把整数可分成奇数和偶数，特别对素数的分类方法。例全体奇素数可以分成4k+1，4k+3；或6k+1，6k+5等类型。

和整除性一样，二个数的最大公约数实质上也是用等号来定义的，因此在解决此类问题时若有必要可化为等式问题，最大公因数的性质中最重要的性质之一为 a=bq+c，则一定有（a，b）=（b，c），就是求二个整数的最大公约数的理论根据。也是解决关于最大公约数问题的常用方法之一。读者应有尽有认真体会该定理的证明过程。

互素与两两互素是二个不同的概念，既有联系，又有区别。要认真体会这些相关的性质，例如，对于任意a ,b∈Z，可设（a ,b）=d，则a=da1 ,b=db1，则（a1 ,b1）=1，于是可对a1 ,b1使用相应的定理，要注意，相关定理及推论中互素的条件是经常出现的。读者必须注意定理成立的条件，也可以例举反例来进行说明以加深影响。顺便指出，若a∣c，b∣c，（a ,b）=1，则ab∣c是我们解决当除数为合数时的一种方法。好处是不言而喻的。

最小公倍数实际上与最大公因数为对偶命题。特别要指出的是a和b的公倍数是有无穷多个。所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数中的最小的正整数。这一点实际上是应用自然数的最小自然数原理，即自然数的任何一个子集一定有一个最小自然数有在。最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题。两者的关系为

a ,b∈N， [a ,b]=ab ?a,b?上述仅对二个正整数时成立。当个数大于2时，上述式子不再成立。证明这一式子的关键是寻找a , b的所有公倍数的形式，然后从中找一个最小的正整数。

解决了两个数的最小公倍数与最大公因数问题后，就可以求出n个数的最小公倍数与最大公因数问题，可以两个两个地求。即有下面定理 设a1,a2,?an是n个整数，(a1,a2)?d2,(d2,a3)?d3,?(dn?1,an)?dn,则（a1,a2,?an）=dn, 设[a1,a2]?m2,(m2,a3)?m3,?(mn?1,an)?mn,则有[a1,a2,?an]=mn, 素数是数论研究的核心，许多中外闻名的题目都与素数有关。除1外任何正整数不是质数即为合数。判断一个已知的正整数是否为质数可用判别定理去实现。判别定理又是证明素数无穷的关键。实际上，对于任何正整数n>1，由判别定理一定知存在素数p，使得p∣n 。即任何大于1的整数一定存在一个素因数p 。素数有几个属于内在本身的性质，这些性质是在独有的，读者可以用反例来证明：素数这一条件必不可少。以加深对它们的理解。其中p∣ab?p∣a或p∣b也是常用的性质之一。也是证明算术基本定理的基础。 算术基本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘积，而且分

解是唯一的，不是任何数集都能满足算术基本定理的，算术基本定理为我们提供了解决其它问题的理论保障。它有许多应用，由算术基本定理我们可以得到自然数的标准分解问题。

k1设a=p1...pk，b=???k?1p1...pk，?i?0,?i?0则有 （a，b）=[a，b]= ?k?1p1...pk ?i?min?(i,?i) ?k?1p1...pk ?i?max(?i,?i) 例如可求最大公约数，正整数正约数的个数等方面问题，对具体的n，真正去分解是件不容易的事。

对于较特殊的n，例如n！分解还是容易的。应用[x]的性质，n！的标准分解式可由一个具体的公式表示出来，这一公式结合[x]的性质又提供了解决带有乘除符号的整除问题的方法。

本章的许多问题都围绕着整除而展开，读者应对整除问题的解决方法作一简单的小结。

五、例子选讲

补充知识

①最小自然数原理：自然数的任意非空子集中一定存在最小自然数。 ②抽屉原理：

（1）设n是一个自然数，有n个盒子，n+1个物体，把n+1个物体放进n个盒子，至少有一个盒子放了两个或两个以上物体；

（2）km+1个元素，分成k组，至少有一组元素其个数大于或等于m+1； （3）无限个元素分成有限组，至少有一组其元素个数为无限。 ③梅森数：形如2n-1的数叫梅森数，记成Mn=2-1。 ④费尔马数：n为非负整数，形如2⑤设n=

2nn?1的数叫费尔马数，记成Fn=22n?1。

?k?1p1...pk，设n的正因子个数为d(n)，所有正因子之和为?(n)，则有

d(n)?(?1?1)?(?2?1)...(?k?1) ?1?12?1pkk?1p1?1p??12?(n)??...P1?1P2?1Pk?1 ??1⑥有关技巧

1. 整数表示a=a0×10n+a1×10n-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. 用数学归纳法

f. 要证明a|b，只要证明对任意素数p，a中p的幂指数不超过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=

ppqp，由对数定义可得10=2，则有2·5p q=2,则同一个数左边含因子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的幂指数，即

2004??2004??2004??2004??2004?5（2004！）=???????????4???5??499

?5??25??125??5??5?q

例6.证明（n!）(n-1)!|(n!)!

证：对任意素数p,设（n!）(n-1)!中素数p的指数为?， （n!）!中p的指数β，则

?n???n!??，??(n?1)!???(n?1)!?????k??k?,?(nx)?n(x) k?1?p?k?1?p????n!???kk?1??p???n(n?1)!??????????(n?1)!?n!?k?1?pk?k?1?pk?????????(n?1)!??n!k?k?1???p???? ??即???，即左边整除右边。

例7. 证明2003|（20022002+20042004-2005） 证：∵ 20022002=（2003-1）2002=2003M1+1

20042004=（2003+1）2002=2003M2+1 ∴20022002+20042004-2005=2003（M1+M2-1） 由定义2003|（20022002+20042004-2005）

......1被7除的余数。 例6：求11?????50......1≡11（mod 7）≡4（mod 7）解：∵111111被7整除，∴11，即余数为4。 ?????50

例7：把0.04263化为分数。 解：设b=0.04263，从而1000b=42.63,

100000b=4263.63，99000b=4263-42 b=?4221469=。 9900011000........当然也可用直化分数的方法做。

例8：设一个数为62XY427是9，11的倍数，求X，Y 解：因为9|62XY427

所以9|6+2+X+Y+4+2+7， 即9|21+X+Y

又因为11|62XY427， 有11 |（7+4+X+6-2-Y-2） 即11|（X-Y+13）

因为0?X，Y?9， 所以有21? 21+X+Y?39， 4 ? X-Y+13 ?22，由此可知 21+X+Y=27，X-Y+13=11 或21+X+Y=36，X-Y+13=22 X+Y=6，X-Y=-2

或X+Y=15，X-Y=9，解得X=2，Y=4。

例9：证明：8a+7不可能是三个整数的平方和。

证：由于每一个整数对于8，必同余于0，1，2，3，4，5，6，7这八个数之一

注意到对于模8，有

02?0,12?1,22?4,32?1, 42?0,52?1,62?4,72?1,

因而每一个整数对于模8，必同余于0，1，4这三个数

不能x,y,z如何变化，只能有x?y?z?0,1,2,3,4,5,6(mod8) 而8a?7?7mod8)，故8a?7不同余于x?y?z关于模8

2222222228a?7?x2?y2?z2，从而证明了结论。

第二章 不定方程

一、 主要内容

一次不定方程有解的条件、解数、解法、通解表示，不定方程x2+y2=z2通解公式、无穷递降法、费尔马大定理。 二、 基本要求

1、 了解不定方程的概念，理解对“解”的认识，掌握一次不定方程ax?by?c有解的条件，能熟

练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程a1x1?a2x2??anxn?c有解的条件，在有解的条件下的解法。

2、掌握不定方程x2+y2=z2在一定条件下的通解公式，并运用这个通解公式作简单的应用。 3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x4+y4=z2无解的方法。 4、掌握证明不定方程无解的若干方法。

三、难点和重点

（1）重点为求解一次不定方程的方法 （2）掌握第二节中引证的应用。 （3） 费尔马无穷递降法。

四、自学指导

不定方程主要讲解以下几个问题 （i）给定一类不定方程，判别在什么条件下有解。 （ii）在有解的条件下，有多少解 （iii）在有解的条件下，求出所给的不定方程的所有解。 二元一次不定方程的一般形式为ax+by=c 。若(a ,b)∣c，则该二元一次不定方程一定有解，若已知一个特解，则一切解可以用公式表示出来，因此求它的通解只要求出一个特解即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有独到之处。特别要指出用最大公因数的方法。它的根据是求（a ,b）时所得的结果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意义和位置。以免出错。

多元一次不定方程a1x1?a2x2??anxn?c也有类似的结果，但在求解的过程中将它转化二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出x1 ,x2 ,??xn 。所用的方法一般选择最大公因数的方法。由于n元一次不定方程可转化为n-1个二元一次不定方程组，故在通解中依赖于n-1个任意常数。但不象二元一次不定方程那样有公式来表示。

x2+y2=z2的正整数解称为勾股数，在考虑这个方程时，我们对（x ,y）作了一些限制，而这些限制并不影响其一般性。在条件x>0，y>0，z>0，（x，y）=1，2∣x的条件可以给出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，a>b>0 , (a ,b)=1，a ,b一奇一偶。若将2∣x限为2∣y，则也有相应的一个通解公式。

222

在证明这个通解公式的过程中，用到了引理 uv=w，u>0，v>0，（u ,v）=1，则u=a，v=b，w=ab 。a>0，b>0，（a ,b）=1 。利用这个结论可以求解某些不定方程。特别当w=1或素数p 。则由uv=1或uv=P 可将原不定方程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望读者能掌握这种方法。

为了解决著名的费尔马大定理：xn+yn=zn ，n?3无正整数解时，当n=4时可以用较初等的方法给出证明。证明由费尔马本人给出的，一般称为费尔马无穷递降法。其基本思想为由一组解出发通过构造得出另一组解，使得两组解之间有某种特定的关系，而且这种构造可以无限重复的。从而可得到矛盾。因此无穷递降法常用来证明某些不定方程无整数解。

证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：（反证法）

若A有解?A1有解?A2有解????An有解，而An本身无解，这样来构造矛盾。从而说明原不定方程无解。

对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。特别要求掌握：简单同余法、因子分解法、不等式法，以及中学数学中所涉及的判别式法。

五、例子选讲

例1：利用整数分离系数法求得不定方程15x+10y+6z=61。 解：注意到z的系数最小，把原方程化为

z=(?15x?10y?61)??2x?2y?10?(?3x?2y?1) 令t1=(?3x?2y?1)?z，即-3x+2y-6t1+1=0

此时y系数最小，?y?(3x??6t1?1)?x?3t1?(x?1) 令t2 =(x?1)?z,即x?2t2?1,反推依次可解得 y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2 z=-2x-2y+10+t1=6-5t1+10t2

?x?1?2t2∴原不定方程解为??y?1?3t1?3t2t1t2∈z.

?z?6?5t?10t12?121212161616

例2:证明2是无理数

22证：假设2是有理数，则存在自数数a,b使得满足x2?2y2即a?2b，容易知道a是偶数，设a=2a1，

222?2b1代入得b2?2a1,又得到b为偶数，a1?b?a，设b?2b1，则a1,这里b2?a1

这样可以进一步求得a2，b2…且有a>b>a1>b1> a2>b2>…

但是自然数无穷递降是不可能的，于是产生了矛盾，∴2为无理数。

例3：证明：整数勾股形的勾股中至少一个是3的倍数。

证：设N=3m±1(m为整数) ， ∴N2=9m2±6m+1=3(3m2±2m)+1

即一个整数若不是3的倍数，则其平方为3k+1,或者说3k+2不可能是平方数，设x,y为勾股整数，且x,y都不是3的倍数，则x2,y2都是3k+1，但z2=x2+y2=3k+2形，这是不可能，∴勾股数中至少有一个是3的倍数。

例4：求x2+y2=328的正整数解

解：∵ 328为偶数，∴x,y奇偶性相同，即x±y为偶数，设x+y=2u, x-y=2v，代入原方程即为 u2+v2=164,同理令u+v=2u1,u-v=2v1有

22u1?v1?82,u1?v1?2u2,u1?v1?2v2

22u2?v2?41,u2,v2为一偶一奇，且0

u2=1，2，3，4，5代方程，有解（4，5）（5，4） ∴原方程解x=18,y=2,或x=2,y=18。

例5：求x2+xy-6=0的正整数解。 解：原方程等价于x(x+y)=2·3,故有 ∴??x?2,

?x?y?3,?x?3, ??x?y?2,?x?1, ??x?y?6,?x?6, ， ∴ 即有x=2,y=1; x=1,y=5. ??x?y?1.

例6：证明不定方程x2-2xy2+5z+3=0无整数解。 解：若不定方程有解，则x?y2?y4?5z?3

但y4≡0，1(mod5), ∴ 对y,z ，y4-5z-3≡2，3(mod5) 而一个平方数≡0，1，4（mod 5）

∴ y4-5z-3不可能为完全平方，即y4?5z?3不是整数，所以原不定方程无解。

222例7：证明：x?y?z?8a?7无整数解

222证：若原方程有解，则有x?y?z?8a?7(mod8)

注意到对于模8，有

02?0,12?1,22?4,32?1,42?0,52?1,62?4,72?1,

因而每一个整数对于模8，必同余于0，1，4这三个数。

不论x,y,z如何变化，只能有x?y?z?0,1,2,3,4,5,6(mod8)

222而8a?7?7(mod8)，故8a?7不同余于x?y?z关于模8，所以假设错误，即

2222228a?7?x2?y2?z2，从而证明了原方程无解。

例8:某人到银行去兑换一张d元和c分的支票，出纳员出错，给了他c元和d元，此人直到用去23分后才发觉其错误，此时他发现还有2d元和2c分，问该支票原为多少钱？ 解：由题意立式得：100c?d?23?100?2d?2c

即98c?199d?23.

令u?c?2d得98u?3d?23,

令v?33u?d得3v?u?23.

所以u?3v?23(v为任意整数），代入得： d?33u?v?98v?33?23,（1） c?u?2d?199v?67?23,

其中v是任意整数。又根据题意要求：d?0,0?c?100. 根据(1)，仅当v=8时满足此要求，从而d?25,c?51. 因此该支票原为25元51分.

第四章 同余式

一、 主要内容

同余方程概念及次数、解的定义，一次同余方程ax≡b(mod m)有解的充分必要条件，一次同余方程组，孙子定理，高次同余方程，素数模的同余方程，威尔逊定理。

二、基本要求

通过本章的学习要求掌握同余方程的一些基本概念，例同余方程的次数、解等，能解一次同余方程，一次同余方程组，理解孙子定理并用它来解一次同余方程组，会解高次同余方程，对于以素数模的同余方程的一般理论知识能理解。

三、重点和难点

（1） 孙子定理的内容与证明，从中学会求出一次同余方程组的解并从中引伸更一般的情形，即模不二

二互素的情形。

（2） 素数模的同余方程的一些基本理论性问题，并能与一般方程所类似的性质作比较。

四、自学指导

同余方程和不定方程一样，我们同样要考虑以下三个问题，即有解的条件，解数及如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入验算总解组则所需的结果。因此上述三个问题已基本解决，只不过具体到某一个同余方程计算起来困难一点而异。但对于解数，传统的结果不再成立。例如一个同余方程的解数可以大于其次数。读者可以举出反例来证明这一事实。

要学好同余方程这一章。必须首先弄清同余方程的概念，特别是同余方程解的概念，互相同余的解是同一个解。其次有使原同余方程和新的同余方程互相等价的若干变换。移项运算是传统的，同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。无论是乘上一数k或除去一个数k，为了保持其同解性，必须（k ,m）=1，这一点和同余的性质有区别。

一次同余方程的一般形式为ax≡b(mod m)，我们讨论的所有内容都在这标准形式下进行的。总结一次同余方程与二元一次不定方程有相当的联系，一次同余方程的求解可以由二元一次不定方程的求解方式给出。反之亦然。但要注意在对“解”的认识上是不一致的，从而导致有无穷组解和有限个解的区别。为了求ax≡b(mod m)的一个特解，可在条件(a ,m)=1下进行。教材上有若干种求解方式，供读者在同样问题选择使用。

一次同余方程组的标准形式为 x≡b1(mod m1) x≡b2(mod m2)

?? (1) x≡bn(mod mn)

若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求

法方法都是这一标准形式得到的。

同余方程组（1）有解的条件?(mi ,mj) ∣bi-bj ，1?i，j?k 。 在使用时一定要对所有可解进行验算，进行有解的判别

求解一次同余方程组（1）有两种方法：待定系数法和孙子定理。二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是二二互素。孙子定理为下面定理：

（孙子定理）k?2,m1,m2,....,mk两两互素，m?m1m2...mk,m?miMi,i?1,2,...k则一次同余式组 x?b1(modm1),x?b2(modm2),..x?bk(modmk) 的解为 ''x?M1M1'b1?M2M2b2?...MkMkbk(modm), 其中MiMi'?1(modmi),i?1,2,...k. 对待定系数法和孙子定理要有深刻的理解。体会其实质，这样不必死记硬背。

次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理也可求出原同余方程的解。

求高次同余方程解的基本方法有两条，一是小模，二是降次。 设m=?k?1p1?pk；则要求f(x) ≡0(mod m)的解只要求f(x) ≡0(mod pα) (2) 的解即可，其中p为素数。α?1 。

对于（2）的解的求法我们用待定系数法。

设f(x) ≡0(mod p)的解为x≡x1(mod p)为解。则当p├ f′(x)时，

f(x) ≡0(mod p)的一个解x1可求出f(x) ≡0(mod p)的一个解。方法如下：

2

将x=x1+pt1代入 f(x) ≡0(mod p)有

22

f(x1+pt1) ≡0(mod p)?f(x1)+pt1f′(x1) ≡0(mod p)

2

?f?x1?,+t1f(x1) ≡0(mod p) ?t1=t1′+ p t2 p2

2

代入 x=x1+pt1=x1+p(t1′+t2p)=x2+ pt2

则 x≡x2(mod p)即为f(x) ≡0(mod p)的解。然后重复上述过程，即可由x2得f(x) ≡0(mod pα)的解 x3 。最后求出f(x) ≡0(mod pα)的解x?

从上所述，关键是求素数模的同余方程f(x) ≡0(mod p)的解。 f(x) ≡0(mod p)的性质 （1）同余方程的解与f(x)的分解之间的关系，这一点和代数方程几乎一样。注意素数p的条件必不可少。 （2）同余方程的解数与次数之间有关系 解数?次数。这一点和代数方程也一样。此时，素数p的条件

也必不可少

本节的辅产品是著名的wilsom定理。 P为素数，则有(p-1)！≡-1(mod p)， 实际上wilsom定理的逆定理也成立。故wilsom定理可以作为素数成立主要条件。

2

2

五、例子选讲

补充知识

定义1：当（a，m）=1时，若ab?1(modm)，则记b?根据定义和记号，则

1(modm)，称为形式分数。 ac1表示c?关于模m，则有下列性质 aa1、

cc?mt1?(modm),t1,t2?Z. aa?mt2cc1?(modm). aa12、若（d，m）=1，且a?da1,c?dc1,则利用形式分数的性质把分母变成1，从而一次同余式的解。

例1：解一次同余式17x?19(mod25)

解：∵（17，25）=1，原同余方程有解，利用形式分数的性质，

同余方程解为 x?

19?618?7????7(mod25) 17?824?112)?x??2(mod?10) 例2：解同余方程组?x?6(mod?x?1(mod15)?解：∵（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1

∴ 原同余方程有解，且等位于

?x??2(mod4)?x??2(mod3)??x??2(mod4)?x?6(mod2)????x?1(mod3) 此时变成模两两互素 ??x?1(mod5)?x?6(mod5)??x?1(mod3)???x?(mod5)由孙子定理可求得其解为：x?46(mod60)

例3：解一次同余式组

?51x?57(mod75) ??3x?1(mod4)解: 用常规方法先求每一个一次同余式的解，得到下列一次同余式组

?x?7,32,57(mod75) ?x?3(mod4)?然后用孙子定理求解，所以同余方程组有3个解，且解分别为

x?7(mod300)，x?107(mod300)，x?207(mod300)

例4：设2p+1是素数，则

(P!)2?(?1)p?0(mod2p?1)

证：设n=2p+1,由假设n为素数，于是由威尔逊定理有(n-1)! ≡-1(mod n) 由于(n-1)!+1≡(n-1)(n-2)?(p+2)(p+1)p(p-1)?3·2·1+1 ≡1·(n-1)·2(n-2)·2(n-3)?·(p-1)[n-(p-1)]·p·(n-p)+1

2p≡p!(n-1)(n-2)?(n-p)+1≡(p!)(-1)+1(mod n)

p∴ (p!)2(-1) +1≡0(mod n) ∴ (p!)2+(-1)p≡0(mod 2p+1)

例5：解同余方程28x≡21(mod 35) 解：∵ （28,35）=7|21，

∴ 原同余方程有解，且有7个解 原同余方程等价于4x≡3(mod 5) 而且4x≡3(mod 5)解为x≡2(mod 5)

∴ 原同余方程解为2，7，12，17，22，27，31（mod 35）

第五章 二次剩余理论

一、 主要内容

平方剩余与平方非剩余的概念、欧拉判别条件、勒让德符号、二次互反律、雅可比符号、素数模同余方程的解法

二、基本要求

通过本章的学习，掌握平方剩余与平方非剩余的概念，掌握勒让德符号的定义、性质计算及利用它来判别一个二次同余方程是否有解，对于几个较特殊的勒让德符号的值，要求能掌握它的推导方法。了解推可比符号的定义，性质及功能，会解素数的模的二次同余方程。及证明一些二次不定方程无解中的应用。

三、重点和难点

（1）欧拉判别定理：即a为p的平方剩余的条件。

（2）勒让德符号，二次互反律。 （3）素数模同余方程的解法。

四、自学指导

对于一般的高次同余方程的求解归纳为模为p的情形。对于同余方程f(x)≡0(mod p)的求解依赖于f(x) ≡o(mod p)的解。而且对于一般的f(x)，求解f(x) ≡0(mod p)的解是很困难的。本章讨论f(x)为一个整系数的二次三项式时情形。可得到二次同余式的标准形式

2

x ≡a(mod p) (a ,p)=1 p为奇素数。 （1） 以下内容都是在标准形式下得到的。其中p为奇素数。 平方剩余和平方非剩余是以同余方程（1）是否有解来定义的。因此平方剩余和平方非剩余只要在模p的一个简化剩余系中找即可。实际上，模m的全体平方剩余和全体平方非剩余构成了模p的一个简化剩α

α

p?1?同余。这为我余系。因为平方剩余和平方非剩余各占一半，且平方剩余与下列数列1，2，?????2??222们提供了计算模p的平方剩余的方法，另一个为欧拉判别定理ap?12 ≡1(mod p)，这个定理的证明依赖于高次同余方程的素数模p，次数等于解数的条件，再结合欧拉定理即可得到，但缺点是计算量比较大。

?1?=1或?2?=1为了弥补计算量大的不足，引进了勒让德符号，根据定义可得到一系列性质，其中????p???p??????的p及????1??2?=-1，=-1的p的值需要记忆， ???????p??p?即有

1、 p=4K+1时，-1是p的平方剩余，p=4K+3时，-1是p的平方非剩余。

2、 p=8K+1或8K-1时，2是p的平方剩余，p=8K+3或8K-3时，2是p的平方非剩余。 3、 对一些较小的素数其平方剩余和平方非剩余列表如下：

P 平方剩余 平方非剩余 3 1 2 5 1，4 2，3 7 1，2，4 3，5，6

11 1，3，4，5，9 2，6，7，8，10 13 1，3，4，12，9，10 2，5，6，7，8，11

其余性质要理解，特别是二次互反律的条件为p，g为二个不同的奇素数。勒让德符号计算的最大困难对a要进行素因数分解，往往很烦，也很困难。

为了弥补这个困难，再引进雅可比符号，由雅可比符号的定义出发可建立形式上和勒让德符号完全一致的性质。由于雅可比符号是勒让德符号的推广，因此雅可比符号在这里的主要功能是为了计算勒让德符号的值。

本章主要解决以下三个问题

2

1、已知素数p判别同余方程x≡a(mod p)是否有解。

?a?即计算??=1或-1 。

?p????a??a?2、已知a，求所有使及??=1或??=-1的p的一般形式。

?p??p??????a?2

3、在??=1的条件下，如何求出x≡a(mod p)的解。若x1为一个解，则另一个解为-x1 。

?p???上述已叙述了问题（1）、（2），现在只剩下解（3）解的方法。除了书上介绍的公方法，我们再补充另一个方法即高斯逐步淘汰法。 五、例子选讲

补充知识

pp22高斯逐步淘汰法：首先，不妨设0

24x2?ax2p因解同余方程x≡a(mod p)（1）相当于不定方程x=a+py，故0

pp422

因而在求y的值时，不必考虑大于

p的整数，这就大大缩小了讨论的范围。 4其次，任取素数q≠p，求出q的平方非剩余为a1 ,a2??as并以v1 ,v2,??vs表示同余方程 a+py≡a1 (mod q) ,a+py≡a2(mod q)，??

a+py≡as(mod q)的解，由于平方数一定为任何模的平方剩余，故若取y≡vi(mod q)，则a+py是q的平方

2

非剩余，因而a+py一定不是平方数。而不能有x=a+py这样可淘汰满足y≡vi(mod g)的各个y的值。 取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）的解。

2

例：解同余方程x≡73(mod137) 解 ∵ ?

?73?2

?=1，∴x≡73(mod137)有二个解 ?137?

因为p=137，故0

取q=3，则2为3一平方非剩余。 解同余方程

73+137y≡3(mod3)

得y≡2(mod 3)，从不大于34的正整数中淘汰形如y=2+3t的数，即有下面

1，3，4，6，7，9，10，12，13，15，16，18，19，21，22，24，25，27，28，30，31，33，34。 再取q=5，2，3为g的平方非剩余的同余方程

73+137y≡2(mod5) ，73+137y≡3(mod5)解为y≡2(mod5) ,y≡0(mod5)，再从前面的数中淘汰形如y=2+5t和y=5t，有下面

1，3，4，6，9，13，16，18，19，21，24，28，31，33，34。 又取q=7，3，5，6为g的三个平方非剩余的同余方程 73+137y≡3,5,6(mod7)

的y≡0,4,6(mod7)淘汰y=4+7t,7t,6+7t,就只留下了 1,3,9,16,19,24,31,33 。

22

将上述数代入137y+73=x及137×3+73=484=22 故x≡±22(mod137)为本题同余方程的解。

例1：设p=4n+3是素数，试证当q=2p+1也是素数时，梅素数Mp不是素数。 证：∵ q=8n+7,24n?3?2q?12?2????q???1(modq) ??∴ q|24n+3-1，即q |Mp，∴ Mp不是素数。

例2：若3是素数p平方剩余，问p是什么形式的素数？

?3?解：∵ 由反转定律??p???(?1)??p?12?p????， ?3?p?1(mod4) p??1(mod4)??1p??1注意到p>3，p只能为p??1(mod 3)且??????3??3???∴ ??p???1只能下列情况

?p?1(mod3) ?p?1(mod4)?d)?p??1(mo3 ?d)?p??1(mo4∴ p?1(mod12)或p??1(mod12)

例3：证明形如4m+1的素数有无穷多个。

证：假设形如4m+1的素数只有有限个，设为p1?pk，

显然(2p1?pk)2+1的最小素因数p是奇数，且p与p1?pk不同，

设p为4m+3形的素数，但p整除(2p1?pk)2+1，表明(2p1?pk)2+1≡0（mod p） 即x2

??1???1?≡(-1)(mod p)有解，即?，但????1?p??????p??(?1)p?12?(?1)2m?1??1矛盾，

∴p为4m+1形，这与4m+1的素数只有k个矛盾。

例4：证明不定方程x2+23y=17无解。 证：只要证x2≡17(mod 23)无解即可，

∵ 17≡1(mod 4)

17??23??6??2??3??3??17??2?∴ ?????????????????????????1

?23??17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解，即原方程无解。

例5设x为整数，证明形如x2?1的整数的所有奇因数都有4h+1的形式，（其中h为整数） 证：设2n+1是整数x2?1的任一奇素因数，于是有 x2?1?0(mod2n?1),即x2??1(mod2n?1).

可以证明，这时x2?0(mod2n?1)，否则有1?0(mod2n?1)，这是不可能的。

因此，由2n?1是奇素数，便有(x,2n?1)?1。

2从而(x,2n?1)?1，这样由费马定理，有x2n?1(mod2n?1)。 但是x2n?(x2)n?(?1)n(mod2n?1),因此有(?1)n?1(mod2n?1).

由此可知，n必为偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数x2?1的的所有奇素因数形式必为4h+1形式。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故x2?1形式的数的奇因数必为4h+1形式的数。

证2：由上面可知，-1是模2n+1的平方剩余，即???1???1. 2n?1??其中2n+1是奇素数。由定理3知2n?1?1(mod4)

从而 2n?0(mod4)，故n?0(mod2)，所以n是偶数，其余同上。

例6：证明：形如p?1(mod8)的素数有无穷多个。

证：设N是任意正整数，p1,p2,...,ps是不超过N的一切形如p?1(mod8)的素数。记

q?(2p1p2...ps)4?1。

显然q的任意素因数a异于2，且x?2p1p2...ps是同余式x4?1?0(moda)的解。 由a?1(mod8).又由于是pi(i?1,2,...,s)不是q的因数，

故a?pi(i?1,2,...,s)，从而a?N。因此形如p?1(mod8)的素数有无穷多个。

例7: 解如下二次同余式x2?11(mod125)

解： (1)125=53。先解x2?11?1(mod5)。它的一个解是x=1。

再解x2?11(mod52)。令x?1?5y，

则有(1?5y)2?11(mod52).化简得(1?10y)?11(mod52)，

得到y?1(mod5),从而有5y?5(mod52)，1?5y?6(mod52)， 所以x2?11(mod52)的一个解为x?6,最后解x2?11(mod53)。 设x?6?52z。代入有(6?52z)2?11(mod53)， 化简得12?52z??25(mod53). 即12z??1(mod5).

它的一个解是z?2.因此x?6?25?2?56是同余式x2?11(mod)125的一个解， 所以由定理，x2?11(mod)125的两个解是x?56(mod)125，x??56(mod)125.

例8：判断同余方程x2?286(mod443)是否有解。

解：286=2×143，433是素数，(143，443)=1

奇数143不是素数，但可用判定可比符号计算的生勒让德符号

?286??2??143?????????(?1)?443??243??443??(?1)143?184432?12?(?1)143?1443?1?22?443??14??2??7??????????? ?143??143??143??143??(?1)7?1143?1?22?143??? 7???3??1?????????1 ?7??3?∴原方程有解。

第六章 原根与指标

一、 主要内容

原根、指数的定义及基本性质、原根存在的条件、指标及n次乘余、模2及合数模指标组、特征函数

二、基本要求

理解原根，指数的定义，掌握指数的性质，原根存在的条件以及在一定条件下求已知模的原根。能判断怎样的数为模m的原根，用指数以及指标组能构造模m的简化乘余系。

三、重点和难点：

本章内容都比较抽象，具有一定的理论性。原根与指标是重点。

四、自学指导：

2

上章介绍了x2≡a(modm)的解数。本章主要以解决x≡a(modm)的解而引进原根，指数等概念。 指数是指使?at≡(modm)的最小的正整数d。一般记为?m(a)，上述条件是以(a,m)=1为先决条件。设

m>1， a≡b(mod m)，则δm(a)=δm(b)，对于指数可讨论若干问题，特别当δm(a)=φ(m)时称a为m的一个原根。若a 为m的一个原根，则m的一个简化系为a ,a ,??aααα12φ(m) 。不是任何整正数都有原根存在的，只有当m=2，4，p,2p时，原根存在。反之当m≠2,4, p， 2p时无原根存在。

ααα要弄清p和p的原根之间的关系，及p与2p的原根之间的关系。弄清当m在原根存在时，m的所有原

n

根表达方式s={g 1?n?φ(m)，(n, φ(m))=1}

指标是原根这一种另一个重要的概念，它有类似于对数函数的性质，另用指标可构造适当模m的简化剩余系。

α

五、例子选讲

例1：试10是模17的原根。

证：因?(17)=16，其正因子为d=2,4,8,且10d

∴ 10为模17的原根。

例2：解同余方程x12≡2(mod 31) 解：d=(12,30)=6, 查表ind2=24,

6|24，解且本题有6个解，

x12≡2(mod 31)?12indx=ind2(30) 即indx≡4(mod 5)

∴ indx≡2,7,12,17,22,27(mod 30) 查模31指标表，

∴ x≡9,17,8,22,14,23(mod 31)

1(mod 17),

例3: (1)若p和q=4p+1均为素数，则2是模q的一个原根。

(2)若p和q=6p+1均为奇素数，则3是模q的一个原根。 证 ：(1)由于p和q=4p+1均为素数，故p≠2，从而(2,q)=1。

根据费马定理有 2q?1?24p?1(modq)

因此要证明2是模q的一原根，只需证明

q?122?22p??1(modq)

即可。根据本章定理2，有

22p?q?122?2????q??(modq) ??而q是奇素数，必有p?1,3,5,7(mod8)之一，但不管那一种，

均有4p?4(mod8)，因此q?4p?1?5(mod8) 所以由定理，2是模q的非平方剩余，即??????1。 从而有22p??1(modq)。

故2关于模q的阶为4p=q-1，所以2是模q的一个原根。 (2)由于p和q=6p+1均为奇素数，故3q，从而(3,q)=1， 故由费马定理有

?2??q?3q?1?36p?1(modq)

为了证明3是模q的一个原根，只需证明

q?1233p?3??1(modq)即可

由定理有

33p?3q?12?3????q??(modq) ??由于p是奇素数，故p?1,3,5,7,11(mod12)之一， 不管那一种情况，均有6p?6(mod12)，所以 q?6p?1?7(mod12)。 所以3是模q的非平方剩余，即??????1， 所以33p?3??q???1(modq)

故3关于模q的阶为6p=q-1，所以3是模q的一个原根。

《初等数论》模拟试卷（A）

说明：考生应有将全部答案写在答题纸上，否则作无效处理

一、填空（36分）

1、d（1000）= 。σ（1000）= 。φ（1000）= 。 2、n?1， 若(n?1)!?1?0(modn)则n为 。 3、不能表示成5X+3Y（X、Y非负）的最大整数为 。 4、7在2003！中的最高幂指数是 。 5、（1515 ，600）= 。 6、ax?b(modm)有解的充要条件是 。

7、威尔逊定理是 。

8、写出6的一个简化系，要求每项都是5的倍数 。

9、0.32?化为分数是 。 10、22003的末位数是 。

11、[-2.3]= 。

12、φ（1）＋φ（P）＋?φ（Pn）= 。

13、x?1且能被4、5、7整除，则最小的x是 。 14、888??????88?666?????66?被7除后的余数为 。505015、两个素数的和为31，则这两个素数是 。

16、带余除法定理是 。

二、解同余方程组（12分）

??x?2(mod5)?x?3(mod8) ??x?1(mod7)

三、叙述并且证明费尔马小定理。（12分）

四、如果整系数的二次三项式p(x)?x2?bx?c当x?0,1数根（6分）

五、设Ｐ为奇素数，则有（8分） （1）1p?1?2p?1???(p?1)p?1??1(modp)

（2）1p?2p???(p?1)p?0(modp) 六、证明：对任何正整数ｋ，ｍ，ｎ

时的值都是奇数，证明p(x)?0没有整

有１１|55k?2?45m?4?35n?3 （6分）

七、证明：3是无理数。（8分）

八、试证：对任何的正整数n,n2?2不能被4整除。（6分） 九、解不定方程4x?5y?10 （6分）

《初等数论》模拟试卷（A）答案 一、

1、16，2340，9360 2、 素数

3、 7 4、 331 5、 15 6、 (a,m)|b

7、 (p?1)!?1?0(modp) 8、 5，25 9、

29 908 -3

10、 11、 12、 13、 14、 15、 16、

pn

140 5 2，29 查书

二、孙子定理x?267(mod280) 三、 见书 四、 证：由条件可得c为奇数，b为偶数

如果p（x）=0有根q，若q为偶数，则有q?bq?c为奇数，而p（q）=0为偶数，不可能，若q

2为奇数，则有q?bq?c为奇数，而p（q）=0为偶数，也不可能，所以p(x)?0没有整数根

2五、 证：由欧拉定理

1p?1?2p?1???(p?1)p?1?1?1??1?p?1??1(modp)

由费尔马定理

1p?1?2p?1???(p?1)p?1?1?2??p?1?0(modp)

六、（5，11）=1，（4，11）=1，（3，11）=1由欧拉定理得

510?1(mod11)，310?1(mod11)，410?1(mod11)，进一步有 55?1(mod11)，35?1(mod11)，45?1(mod11)

对任何正整数ｋ，ｍ，ｎ有

55k?2?45m?4?35n?3?52?44?33?0(mod11)即有

１１|55k?2?45m?4?35n?3

七、见例。

八、当n=2k时有n?2=4k?2，不能被4整除

当n=2k+1时有n?2=4k??4k?3，不能被4整除，所以有 对任何的正整数n,n2?2不能被4整除

九、因为（4，5）=1，所以不定方程有解，由观察得有特解x=0，y=5

2222?x?0?5t所以不定方程的解为? t为整数

y?2?4t?《初等数论》模拟试卷（B） 说明：考生应有将全部答案写在答题纸上，否则作无效处理

一、填空（30分）

1、d（1001）= 。σ（2002）= 。φ（5005）= 。 2、梅森数Mn是形如 的数。

3、不能表示成5X+6Y（X、Y非负）的最大整数为 。 4、2003！中末尾连续有 个零。 5、（21a+4，14a+3）= 。 6、x2?y2?z2通解为 。

7、费尔马大定理是 。

8、从1001到2000的所有整数中，13的倍数有 。 9、a1x1?a2x2?....anxn?c有解的充要条件是 。

10、p,q是小于是100的素数，pq- 1=x为奇数，则x的最大值是 。 11、[X]=3，[Y]=5，则[X—2Y]可能的值为 。

12、X能被3，4，7整除，这个最小的正整数是 。 13、两个素数的和是39，这两个素数是 。 二、解同余方程组（12分）

?x?1(mod4)??x?1(mod5) ?x?5?2mod7)?三、 叙述并且证明费尔马定理。 （12分） 四、 证明：设ｄ是自然数ｎ的正因子，则有

?d?ndn1d(n)2 （10分）

五、 设Ｐ为奇素数，则有（10分）

（１）1p?1?2p?1?....(p?1)p?1≡－1（ｍｏｄＰ） （２）1P?2P?....(P?1)p ≡0（ｍｏｄＰ）

六、用初等方法解不定方程x2?20xy?1996?0。 （8分） 七、解不定方程式15x+25y=-100. (6分) 八、试证x3?3y3?9z3 无正整数解。 （6分）

九、请用1到9这九个数中的六个（不重复）写出一个最大的能被15整除的六位数（6分）

《初等数论》模拟试卷（B）答案 一、

1、8，1152，960， 2、2?1 3、19， 4、499， 5，1， 6、见书 7、见书 8、77， 9、(a1,a2,?an)c 10、193， 11、-9，-8，-7， 12、84， 13、2，37

n140) 二、孙子定理x?86(mod三、见书。

四、设d是n的因子，则

nn也是n的因子，而d?n，

dd2d(n)n的因子一共有d（n）个，所以 有(?d)?n，从而证明了结论。

dn五、证：由欧拉定理

1p?1?2p?1???(p?1)p?1?1?1??1?p?1??1(modp)

由费尔马定理

1p?1?2p?1???(p?1)p?1?1?2??p?1?0(modp)

2六、由条件可知x为偶数，令x?2x1，则有x1?10x1y?499?0

即有x1(x1?10y)??499，因499为素数，

七、因为（15，25）=5|-100，所以不定方程有解，由观察得有特解x=0，y=-4

所以不定方程的解为??x?0?5t t为整数

?y??4?3t八、假若不定方程有解，由条件可知x为3的倍数，x?3x1，代入得y也为3的倍数y?3y1代入得 z

也为3的倍数，且有x1?3y1?9z1，这样可不断进行下去，但事实上不可能，所以不定方程无解。 九、987645

333

本文来源：https://www.bwwdw.com/article/k3ha.html