初等数论总复习题及知识点总结

初等数论学习总结

本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有

着密切的关系，因此初等数论对于中学的数学教师和数学系（特别是师范院校）的本科生

来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的.一

方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，

也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的.正因为如此,

许多高等院校，特别是高等师范院校，都开设了数论课程。

最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理

解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题

的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在

辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排

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

整除的定义、带余数除法

最大公因数和辗转相除法

整除的进一步性质和最小公倍数

素数、算术基本定理

[x]和｛x｝的性质及其在数论中的应用

习题要求〃3：2,3；4；P[2：1；Pl7：1，2,5；p20：1o

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

二元一次不定方程ox+by=c

多元一次不定方程。丙+。2%2+…=c

勾股数

费尔马大定理。

习题要求P29：1，2,4；p31：2,3o

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

同余的定义、性质

剩余类和完全剩余系

欧拉函数、简化剩余系

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

习题要求“43：2,6；〃46：1；“49：2,3；p531,2o

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

同余方程概念

孙子定理

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

素数模的同余方程

威尔逊定理。

习题要求/%：1;/%：1,2；〃69：1，2。

第五章：二次同余式和平方剩余（4学时）自学12学时

二次同余式

单素数的平方剩余与平方非剩余

勒让德符号

二次互反律

雅可比符号、

素数模同氽方程的解法

习题要求〃78：2；P81：1,2,3；“85：1,2；〃89：2；〃93：1。

第一章：原根与指标（2学时）自学8学时

指数的定义及基本性质

原根存在的条件

指标及n次乘余

模2a及合数模指标组、

特征函数

习题要求/%3：3。

＞第一章整除

一、主要内容

整除的定义、卜带余除法定理|、余数、最大公因数、最小公倍数、辗转相除法、互素、两

两互素、素数、合数、|算术基本:西|、|Eratosthesen筛法|、［x］和｛x｝的性质、n!的标准分

解式。

二、基本要求

通过本章的学习，能了解引进整除概念的意义，熟练掌握整除整除的定义以及它的基本

性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理:

芍余除法定理和算术基本定理。认真体会求二个数的最大公因数的求法的理论依据，掌握素

数的定义以及证明素数有无穷多个的方法。能熟练求出二个整数的最大公因数却最小公倍

数，掌握高斯函数［x］的性质及其应用。

三、重点和难点

（1）素数以及它有关的性质，判别正整数a为素数的方法，算术基本定理及其应用。

（2）素数有无穷多个的证明方法。

（3）整除性问题的若干解决方法。

（4）［x］的性质及其应用，n!的标准分解式。

四、自学指导

整除是初等数论中最基本的概念之一，b|a的意思是存在一个整数q,使得等式a二bq

成立。因此这一标准作为我们讨论整除性质的基础。乜为我们提供了解决整除问题的方法。

即当我们无法用整除语言来叙述或讨论整除问题时，可以将其转化为我们很熟悉的等号问

题。

对于整除的若干性质，最主要的性质为传递性和线性组合性，即

的问题

O两者的关系为

a,beN,[a,b]=-^v

上述仅对二个正整数时成立。当个数大于2时，上述式子不再成立。证明这一式子的关

键是寻找a,b的所有公倍数的形式，然后从中找一人最小的正整数。

解决了两个数的最小公倍数与最大公因数问题后，就可以求出n个数的最小公倍数与最

大公因数问题，可以两个两个地求。即有下面定蚀

设％,〃2,…%是n个整数，（41,〃2）="2,32,。3）="3,…（41TM则…）

设[4],〃2]=〃22,（〃?2，%）=用3,…（犯1，/）=〃％则有[卬，々2,…

素数是数论研究的核心，许多中外闻名的题目都与素数有关。除1外任何正整数不是质

数即为合数。判断一个已知的正整数是否为质数可用判别定理去实现。判别定理又是证明素

数无穷的关键。实际上，对于任何正整数n>l,由判别定理一定知存在素数p,使得pino

即任何大于1的整数一定存在一个素因数PO素数有儿个属于内在本身的性质，这些性质是

在独有的，读者可以用反例来证明：素数这一条件必不可少。以加深对它们的理解。黑中P

Iabnp|a或p|b也是常用的性质之一|。也是证明算术基本定理的基础。

算术基本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘

积，而且分解是唯一的，不是任何数集都能满足算术基本定理的，算术基本定理为我们提供

了解决其它问题的理论保障。它有许多应用，由算术基本定理我们可以得到百然数的标准分

解问题。

设行,xpp…pfk，则有

（a,b）=…p2k%=

[a,b]=p[…P葭£=maxQ，A）

例如可求最大公约数，正整数正约数的个数等方面问题，对具体的n,真正去分解是件

大容易的事。对于较特殊的n,例如切分解还是容易的。应用[x]的性质，n!的标准分解

式可由一个具体的公式表示出来

,这一公式结合［x］的性质又提供了解决带有乘除符号的整除问题的方法。

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

五、例子选讲

补充知识

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

②抽屉原理：

(1)设刀是一个自然数，有4个盒子，加1个物体，把91个物体放进〃个盒子，至少

有一个盒子放了两个或两个以上物体；

(2)范汁1个元素，分成A组，至少有一组元素其个数大于或等于炉1；

(3)无限个元素分成有限组，至少有一组其元素个数为无限。

③梅森数：形如叵口的数叫梅森数，记成八=2〃

④费尔马数：刀为非负整数，形如三五的数叫费尔马数，记成卜=22"+1|。

⑤设小Pe…口公，设〃的正因子个数为d®,所有正因子之和为。(几)，则有

d(n)=Q+1)•(%+1)…(综+1)

⑥有关技巧

1.整数表示a=aoX10n+aiX10

一2%仍为奇数一

2.整除的常用方法

a.用定义

b.对整数按被刀除的余数分类讨论

c.连续刀个整数的积一定是n的倍数

d.因式分解

a-b"=S；M,

H+」=(a+b)场21/

e.用数学归纳法

f.要证明a/8只要证明对任意素数Da中0的塞指数不超过6中。的寨指数即可,

用p(a)表示a中夕的幕指数，则|a/6o夕(a)&p(6)

例题选讲

例1.请写出10个连续正整数都是合数.

解：11!+2,11!+3,.......,11!+11。

例2.证明连续二个整数中，必有一个被3整除.

证：设三个连续正数为a,K1,<3+2,而a只有3A,34+1,3a2三种情况，令炉3〃，显然

成立，折34+1时，a+2=3(k+l),折3攵+2时，>1=3(4+1)。

例3.证明lg2是无理数。

证：假设lg2是有理数，则存在二个正整数〃，0,使得lg2="，由对数定义可得10〃=23

Q

则有2"-5”二2工则同一个数左边含因子5,右边不含因子5,与算术基本定理矛盾。・・・lg2

为无理数。

例4.求(21n+4,14n+3)

解：原式原21n+4,14n+3)=(7n+l,14n+3)=(7n+l,7n+2)=(7n+l,1)=1

例5.求2004!末尾零的个数。

解：因为10=2X5,而2比5多，

所以只要考虑2004!中5的幕指数，即

5(20041)二(等)+(等)+(甯卜(繁卜(孝)=499

例6.证明(〃！)人-(〃!)！

证：对任意素数〃设(加)33中素数〃的指数为a,

"!)!中夕的指数氏则

n!

a=(n-1)!Z,Z?=(n-1)!Ek,v(nx)>n(x)

k=\P

00n!O0n(n-1)!、nJ!幻(川

=a

山外=去>S(n-l)!7=(n-l)!Z—

即Z^a,即左边整除右边。

例7.证明2003|(ZOOZ的+ZCK^ow-zOOS)

证：:200220O2=(2003-1)^OOBM.+l

2004^=(2003+1)2OO2=2003M,+l

・・・20022(K,2+20042W>,-2005=2003(此+此一1)

由定义20031(20022OO2+20042OO,-2005)

例8.设d(力为〃的正因子的个数，。(〃)为〃的所有正因子之和，求4(1000),b(1000)o

解：1000=23•53

・・・(7(1000)=(3+1)(3+1)=16,o-(1000)=；二•[二

例9.设。不能被素数平方整除，若才|斤°,则a%

证：由已知己c)Wl,且夕(才)W夕(加c)

22(a)W2夕(。)+夕(c),夕(QW夕(。)+四

即p(ct)W〃⑷,a/b

例10.若机为素数，则〃一定为素数。

证：若〃为合数，则设炉司瓦(1<4伏，)

・・・2也1=(2")也1=(2"-1)材为合数，与极为素数矛盾,

・・・〃为素数。

例11.证明对任意〃，,〃，代n,(此项=1。

证：不妨设〃)勿,则一不二(王1—1)(22"'+1)=(7^-2)(2-+妨

=F,『\F"...FT芯

设(七£)=d则H凡H-2

但Fn为奇数，，由1,即证。

例12.设亚是正整数。证明

证：不妨设小之八。由带余数除法得

m-qxn+rp0<r(<n,

我们有

2^-1=2g'n+r,-2r,+2r,-1=2r,(2q,n-1)+2r,-1

由此及2"-l|2qin-1得，(2m一1,2"-1)=(2八-l,2r'-1)

注意到(m,n)=(n,rj,若八=D,则(m,n)=n,结论成立.若八>0,则继续对(2“-1,2rl-I)作同样的

讨论，由辗转相除法知，结论成立。显见，2用任一大于1的自然a代替，结论都成立。

例13.证明：对任意的正整数*成立如下不等式lgnNklg2。

其中Igri是数n的以10为底的对数，k是八的不同的素因数(正的)的个数。

证：设n是大于1的整数(如果八二1,上述不等式显然成立，因k=0),出，Pz，..,Pk是八的k个

相异的素因素。八的素因数分解式为

n=p?p，...p2.&中:12…,k),由于R/2,(i=iz..,k),从而

1Z,lk

n=p；P?.・.P3>2-2%.….2=2/6+……k,

而4+4+…+疑3故/2,2J

将上述不等式取对数(设底a>l),则有log。心kloga2。

特别有'lgn?klg2。

例14.试证明任意一个整数与它的数字和的差必能被9整除，并且它与它的数字作任意调后

换后所成整数的差也能被9整除。

证：设整数m的个位、十位、百位…的数字分别为4,a2，…，册，则m可表作：

n-,

m=a}+10a2+IOOa3+...+10an

〃一I个

=(O)+a2+a3+...+an)+(9a2+99a3+...+99...9an)

n-l个

=(a।+a2+a3+...+an)+9(a,+1la3+...+11...Ian)

n-l个

所以m-(q+a2+a3+...+=9(%+1la5+...+11...lan)

因为。2，%,…，Q”都是整数，所以任一整数与其数字之和的差必能被9整除。

再设将火,…，4按任一种顺序排成外，心，…，口，并令

n-1

<7=ai+a2+...+an,<T'=a'|+a'2+...+a'n,m=at+10a2+...+10an>

ni

m'=a']+\Oa,2+...^\O-a'no

根据前面证明的结果，知存在整数A,B,使m-b=9A加七=98

因为b=h,所以机一加=b+9A-h-9B=9(A-B)。

由于A-B是整数，这就证明了m-加能被9整除。

注：若对某个整数WKkKn),有“小。，但当时，*=0,则此时加为整数：

fc_|

m'=a'l+10a'2+...+IOa\,即m'=a1…"2H。

如前证，此时结论正确。又当m为负整数及零时，结论显然正确。

>第二章不定方程

一、主要内容

一次不定方程有解的条件、解数、解法、通解表示，不定方程x?+y2=z?通解公式、无穷

递降法、费尔马大定理。

二、基本要求

1、了解不定方程的概念，理解对“解”的认识，掌握一次不定方程OT+勿=。有解的条

件，能熟练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程

4内+a2x2+…4”招=c有解的条件,在有解的条件下的解法。

2、掌握不定方程x2+y'z2在一定条件下的通解公式，并运用这个通解公式作简单的应用。

3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x'+yJ/无解的方

法。

4、掌握证明不定方程无解的若干方法。

三、难点和重点

(1)重点为求解一次入定方程的方法

(2)掌握第二节中引证的应用。

(1)费尔马无穷递降法。

四、自学指导

不定方程主要讲解以下儿个问题

(i)给定一类不定方程，判别在什么条件下有偏丁

(ii)在有解的条件下，有多诵

(iii)在有解的条件下，求出所给的不定方程的所有解。

二元一次不定方程的一般形式为bx+by=c。若(a,b)|c|,则该二元一次不定方程一定

有解，若已知一个特解，则一切解可以用公式表示出来，因此求它的通解只要求出一个特解

即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有

独到之处。特别要指出用最大公因数的方法。它的根据是求(a,b)时所得的结果。由于注

意通解公式x=x(rbit,y=yo+&t中a”E的意义和位置。以免出错。

多元一次不定方程。内%也有类似的结果，但在求解的过程中将它转化

二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出XI,X2,……Xno所

月的方法一般选择最大公因数的方法。由于n元一次不定方程可转化为n-1个二元一次不定

方程组，故在通解中依赖于nT个任意常数。但不象二元一次不定方程那样有公式来表示。

x?+y2=Z?的正整数解称为勾股数，在考虑这个方程时，我们对(x,y)作了一些限制，

而这些限制并不影响其一般性。在条件x>0,y>0,z>0,(x,y)=L2Ix的条件可以给出

x'y'z'的通解公式，x=2ab,y=a2-b2,z2=a2+b2,a>b>0,(a,b)=l,a,b一奇一偶。

若将2|x限为2|y,则也有相应的一个通解公式。在证明这个通解公式的过程中，用到了

引理uv=w2,u>0,v>0,(u,v)=1,则u=a2,v=b2,w=ab。a>0,b>0,(a,b)=10利用

这个结论可以求解某些不定方程。特别当w=l或素数p。则由uv=l或uv=P可将原不定方

程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫恒邈法。

希望读者能掌握这种方法。

为了解决著名的费尔马大定理：xn+y=zn,n23无正整数解时，当n=4时可以用较初等

的方法给出证明。证明由费尔马本人给出的，一般称为费尔马无穷递降法。其基本思想为由

一组解出发通过构造得出另一组解，使得两组解之间有某种特定的关系，而且这种构造可以

无限重复的。从而可得到矛盾。因此无穷递降法常用*证明某些不定方程无整数解。

证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证

明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：(反证法)

若A有解=Ai有解nA：有解n……有解，而A”本身无解，这样来构造矛盾。从而

说明原不定方程无解。

对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。特别要求

掌握：简单同余法、因子分解法、不等式法，以及中学数学中所涉及的判别式法。

五、例子选讲

例1：利用整数分离系数法求得不定方程15^10JH-6Z=61O

解：注意到z的系数最小，把原方程化为

Z=-(-\5x-l()y+61)=-2x-2y+10+-(-3x+2t/+I)

66

4,t=-(-3x+2y+\)GZ,即一3户2广6Z.+1=0

i6

此时y系数最〃、，y=g(3x++6t(-1)=x+3tj+g(x-I)

令t2=1(x-l)€z,即x=2^+1,反推依次可解得

尸产312=2£2+1+3&+)=1+3J+312

Z=~2A~27+IO+。=6-5Zi+1012

x=1+2（,

，原不定方程解为.y=l+3%+3t2tit2^Z.

z=6-5t）-10t2

例2:证明后是无理数

证：假设也是有理数，则存在自数数为〃使得满足炉=2才即/=2〃，容易知道〃是偶数,

设归2国，代入得公=24，乂得到6为偶数，q<b<a,设b=2*则a；=2b；,这里

这样可以进一步求得及，良…且有@>力>句>6>a〉b>…

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

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

证：设八三3m土1（m为整数），/.八'=9/±6〃升1=3（3#±+1

即一个整数若不是3的倍数，则其平方为3依1,或者说3人2不可能是平方数，设为勾

股整数，且为y都不是3的倍数，则都是3介1,但/=/+4二3代2形，这是不可能，

・••勾股数中至少有一个是3的倍数。

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

解：•・・328为偶数，・・・x,y奇偶性相同，即x±y为偶数，设尸户2〃，片产2v,代入原方程

即为

）+/=164,同理令加k2出心-2匕有

〃；十齿=82,%+%=2U2,1/）-%=2V2

诏+>=41,如的为一偶一奇,且0<止<6

〃2二1,2,3,4,5代方程，有解（4,5）（5,4）

，原方程解产18,尸2,或尸2,尸18。

例5：求三+才厂6=0的正整数解。

解：原方程等价于x（户。=2・3,故有

.../=2,俨=3,俨=1,俨=6,,即有尸2,尸1;尸1,尸5.

例6：证明不定方程产-24+5>3=0无整数解。

解：若不定方程有解，则x=y2±Jy-5z-3

但/三o,1(mod5),・•・对MZ,4-5^3三2,3(mod5)

而一个平方数三0,1,4(mod5)

・・・〃-5小3不可能为完全平方，即一J5Z-3不是整数,所以原不定方程无解。

例7：证明：/+)/+z?=必+7无整数解

证：若原方程有解，则有/+z?三8a+7(mod8)

注意到对于模8,有

02=0,I2=1,22=4,32=1,4"=0,5~=1,6~=4,7*=1,

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

不论一,),2,z2如何变化，只能有/+y2+z2三0j,2,3,4,5,6(mod8)

而8。+7三7(mod8),故8〃+7不同余于/+)/+z?关于模8,所以假设错误，即

8〃+7。/+./+22,从而证明了原方程无解。

例8:某人到银行去兑换一张d元和。分的支票，出纳员出错，给了他c元和"元，此人直

到用去23分后才发觉其错误，此时他发现还有2d元和2c分，问该支票原为多少钱？

解：由题意立式得：IOQ?+d-23=1OOx2d+2c

即980-19以=23.

令口=。-2d得98口-必=23,

令i?=33u-d得初-iz=23

所以〃=Q-23(^为任意整数)，代入得：

d=33u-"98”33x23,(1)

c=u+2d=I99u-67x23,

其中『是任意整数。又根据题意要求；d>0,0<c<I00.

根据（1）,仅当片8时满足此要求，从而d=25,c=51.

因此该支票原为25元51分.

＞第三章同余

一、主要内容

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

小定理、循环小数、特殊数2,3,4,5,6,7,8,9,11,13的整除规律

二、基本要求

通过本章的学习，能够掌握同余的定义和性质，区别符号：“三”和二”之间的差异。能

利用同余的一些基本性质进行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质及

构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的

值，掌握欧拉定理、费尔马小定理的内容以及证明方法.能应用这二个定理证明有关的整除

问题和求余数问题。能进行循环小数与分数的互化。

三、难点和重点

（1）同余的概念及基本性质

（2）完全剩余系和简化剩余系的构造、判别

（3）欧拉函数计算、欧拉定理、费尔马小定理的证明及应用

（4）循环小数与分数的互化

（5）特殊数的整除规律。

四、自学指导

同余理论是初等数论中最核心的内容之一，由同余定义可知，若a三b（modn）,则a和

b被m除后有相同的余数。这里m为正整数，一般要求m大于1,称为模，恂余这一思想本

质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的霸第

一章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例

子。从同余的定理上看，同余和整除实际上是同一回事，故悯余还有二个等价的定义：①用

整除来定义即m|a-bo②用等号来定义a=b+mt。值得注意a和b关于m同余是个相对

概念。即它是相对于模

m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模叫，a和b未必

会同余。

从定义上看，同余和整除是同一个事情•，但引进了新的符号“三”后，无论从问题的叙

述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引

进了同余的代数性质和自身性质后，同余符号“三”和等号“二”相比，在形式上有几手一

致的性质，这便于我们记忆。事实1.在所有等号成立的运算中，只有除法运算是个例外，即

除法的消去律不成立。为此对于同余的除法运算我们有二种除法：

(i)模不改变的除法，若ak三bkGnodm),(k,m)=L贝!Ja三b(modm)

(ii)模改变的除法，若ak三bk(modm)(k,m)=d,则a三bQnod

这一点读者要特别注意。

完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为

同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对

二更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，

在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，由于

二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模/〃的一个完全剩余

系的条件有二条为

(1)个数

(2)关于m两两不同余

另外要能用已知完全剩余系构造新的完全剩余系。即有定理

设(a,m)=1,x为m的完全剩余系，则ax+b也是m的完全剩余系。

当(叫，加2)=1时，能由犯的完全剩余系和吃的完全剩余系，构造〃书内完全剩余系。

为讨论简化剩余系，需要引进欧拉函数0(〃》，欧拉函数。(血定义为不超过m且与m互

素的正整数的个数，记为。(/〃)，要掌握血的计算公式，了解它的性质。这些性质最主要

的是当(a,b)=1时，。(.)=。®。(份,和Mp")=pa—pfxX

现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模

m的一个简化剩余系。另一方面，简化剩余数也可从模小的一个完全剩余系中得到简化

剩余系，一组完全剩余系中与m互素的的数组成的。®个不同数的集合称为m简化剩余系。

同样简化剩余系也有一个判别条件。

判别•组整数是否为模m的简化剩余系的条件为

（2）个数二。（加）

（3）关于m两两不同余

（3）每个数与m互素

关于m的简化剩余系也能用已知完全剩余系构造新的简化剩余系。

设（a,m）=1,x为ni的简化剩余系，则ax也是m的简化剩余系。

当（帆]，加2）=1时，能由町的简化剩余系和in2的简化剩余系，构造简化剩余系。

欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意欧拉定理和费尔马定

理的条件和结论。

欧拉定理：设m为大于1的整数，（a,m）=1,则有

三i（nioc]⑼

费尔马小定理：若P是素数，贝而

ap=a（modp）

除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。|就欧拉定理、费

尔马小定理来讲，它在某些形如a”数的整除问题应用起来显得非常方便|。同余方法也是解

决整除问题的方法之一。

另外同余方法在证明不定方程时也非常有用，即要掌握同余“三”和相等“二”的关系:

相等必同余，同余未必相等，不同余肯定不相等。

对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律

1、一个整数被2整除的充要条件是它的末位丽薮广

2；一个整数被3整除的充要条件是它的各位数字之和能被3整除。

3、一个整数被9整除的充要条件是它的各位数字之和能被9整除。

4、一个整数被5整除的充要条件是它的末位为0或5。

5、一个整数被4,25整除的充要条件是它的末二位能被4,25整除。

6、一个整数被8,125整除的充要条件是它的末三位能被8,125整除。

7、设a=/1000"+/J000"T+…询，则7或11或13整除a的充要条件是7或11

或13整除(%+生+…)一(。1+…)

五、例子选讲

例1：求3视的末二位数。

解：,/(3,100)=1,・・・3SS°°)三1(mod100)

(P(100)=。(22-52)=40,・•・3,°三l(mol100)

...3W6=(340)10・3°=(32)2•32^-19X9=-171=29imod100)

・•・末二位数为29。

例2：证明(。地)°三办〃(inodp)

证：由费尔马小定理知对一切整数有："三a(p),BS

由同余性质知有：丁+8>三a+b1a

又由费尔马小定理有(a+b)°三a+b(p)

(”6)〃三夕)

例3：设素数成2,则2"-1的质因数一定是29+1形。

证：设q是2"-1的质因数，由于2，-1为奇数，，gW2,

Z.(2・q)=1,由条件q|2Jl,即2"三1(modq),又,:(q,2)=1,2P=1(modq)

设，是使得2、三1(modp)成立最小正整数

若l<i<p,则有/|.则与,为素数矛盾

i=p,p\Q-\

又•・・为偶数，2|小1,

2p\q~\,(厂\=2pk,即(f=2pk+\

例4：证明13142口

证：’.q叫3/2三4・16"+9・3〃

三3"(4+9)三13义3”.三0(13)

・•・13|4力43"

例5：证明5刀3二义无解

证明：若5六3二系有解，则两边关于模5同余

有5j+3=y(mod5)

即3=x(mod5)

而任一个平方数/三0,1,4(mod5)

,3^0,1,4(mod5)

・・・即得矛盾,即5尹3二即无解

例6：求比3被7除的余数。

~50~

解:被7整除,An……1=11(mod7)=4(mod7),即余数为4。

50~

例7：把0.04263化为分数。

解：设ZF0.04263,从而1000b=42.63,

100000b=4263.63,99003b=4263-42

_4221_469

kD——____-°

~9900011000

当然也可用直化分数的方法做。

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

解：因为9|62XY427

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

又因为11I62XY427,有11|(7+4+X+6-2-Y-2)

BP111(X-Y+13)

因为OWX,Y<9,所以有21W21+X+YW39,

4<X-Y+13<22,由此可知

21+X+Y=27,X-Y+13=ll

或21+X+Y=36,X-Y+13=22

X+Y=6,X-Y=-2

或X+Y=15,X-Y=9,解得X=2,Y=4o

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

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

注意到对于模8,有

02三0,I2=1,22=4,32=1,

42三0,5?三1,62三4,7?三1,

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

不能x\y2,z2如何变化，只能有/+),2+22三o,i,2,3,4,5,6(niod8)

而+7=7mod8),故8。+7不同余于/+)/+z?关于模8

&Z+7W/+),2+Z2,从而证明了结论。

＞第四章同余式

一、主要内容

同余方程概念及次数、解的定义，一次同余方程ax三b(modm)有解的充分必要条件，一

次同余方程组，|孙子定理|高次同余方程愫数模的同余方程|威尔逊定理。

二、基本要求

通过本章的学习要求掌握同余方程的一些基本概念，例同余方程的次数、解等，能解一次

同余方程，一次同余方程组，理解孙子定理并用它来解一次同余方程组，会解高次同余方程,

对于以素数模的同余方程的一般理论知识能理解。

三、重点和难点

(1)孙子定理的内容与证明，从中学会求出一次同余方程组的解并从中引伸更一般的情

形，即模不二二互素的情形。

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

四、自学指导

同余方程和不定方程一样，我们同样要考虑以下三个问题，货有解的条件,

何求赧一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余

系一一代入验算总解组则所需的结果。因此上述三个问题己基本解决，只不过具体到某一个

同余方程计算起来困难一点而异。但对于解数，传统的结果不再成立。例如|一个同余方程的

解数可以大于其次激。读者可以举出反例来证明这一事实。

要学好同余方程这一章。必须首先弄清同余方程的概念，特别是同余方程解的概念，互

相同余的解是同一个解。其次有使原同余方程和新的同余方程互相等价的若干变换。移项运

算是传统的，同余方程两边也可以加.上模的若干倍。相当于同余方程两边加“零二|无论是

乘上一数k或除去一个数k,为了保持其同解性，必须(k,m)=1,这一点和同余的性质有

一次同余方程的一般形式为ax三b(modm),我们讨论的所有内容都在这标准形式下进行

的。总结一次同余方程与二元一次不定方程有相当的联系，一次同余方程的求解可以由二元

一次不定方程的求解方式给出。反之亦然。但要注意在对“解”的认识上是不一致的，从而

导致有无穷组解和有限个解的区别。为了求ax三b(modm)的一个特解，可在条件(a,m)=l

下进行。教材上有若干种求解方式，供读者在同样问题选择使用。

一次同余方程组的标准形式为

x=bi(modmi)

x=b2(modm2)

...(1)

x=bn(modm„)

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

别定理及求法方法都是这一标准形式得到的。

同余方程组(1)TT解的条件=(叫，*)|b「bj,lWi,jWk。

在使用时一定要对所有可解进行验算，进行有解的判别

求解一次同余方程组(1)有两种方法：|待定系数法捌丽礴。二种方法各有特长。

待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂

亮。但对模要求是二二互素。孙子定理为下面定理：

(孙子定理)k>2,叫,〃％,•…，恤两两互素，tn="也•••〃"，，〃=加幽"=L2,...Z则一次同余式

x三仄(mod犯),x三4(modm2\..x=々(modmk)的解为

x=+M2M\b2+...MkMkbk(mod

其中MM=Urnodmi),i=

对待定系数法和孙子定理要有深刻的理解。体会其实质，这样不必死记硬背。

次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同

余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理也可求出原同余方程

的解。

求高次同余方程解的基本方法有两条，求是小模，二是降次

设卜夕:••♦夕幺［;则要求|f(x)三0(modm)的解只要求f(x)三0(川。€1口。)|(2)

的解即可，其中P为素数。。

对于(2)的解的求法我们用待定系数法。

设f(x)=0(modp)的解为x三x1(modp)为解。则当p|-f'(x)时，

f(x)=0(modp)的一个解Xi可求出f(x)=0(modp?)的一个解。方法如下:

将x=Xi+pt］代入f(x)三O(modp")有

f(Xi+pti)=0(modp2)=>f(xj+ptifz(Xi)=0(modp2)

小)

)=0(modp)t)=ti1+p

P

2

代入X=Xl+pt1=Xi+p(t/+t2p)=X2+p2t2

贝IJx=x2(niodp2)即为f(x)=0(modp?)的解"然后重复上述过程，即可由心得f(x)=

0(modp。)的解x3o最后求出f(x)=0(modp。)的解犬“

从上所述，关键是求素数模的同余方程f(x)三0：modp)的解。

f(x)=0(modp)的性质

(1)同余方程的解与f(x)的分解之间的关系，这一点和代数方程几乎一样。注意素数p的

条件必不可少。

(2)同余方程的解数与次数之间有关系解数W次数。这一点和代数方程也一样。此时，

素数p的条件也必不可少

本节的辅产品是著本的wilsom定理°

P为素数，则有(pT)!三TGnodp),

实际上wilsom定理的逆定理也成立。故wilsom定理可以作为素数成立主要条件。

五、例子选讲

补充知识

定义1：当(a,m)=1时，若ab三l(mod"。，则记b三，(mod〃z),称为形式分数。

a

根据定义和记号，则£表示c,关于模z/n则有下列性质

aa

icc+ml./］、7

1、一三-----L(modeZ.

aa+mt2

2、若(d,m)=1,且。==1。［,则£三幺(mod机).

aq

利用形式分数的性质把分母变成1,从而一次同余式的解。

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

解：•・・(17,25)=1,原同余方程有解，利用形式分数的性质,

同余方程解为

19=-6=_18

17=^8=24

x=-2(modi2)

例2：解同余方程组x=6(modi0)

x=l(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三Kmod3)此时变成模两两互素

x=6(mod5)

x三l(mod5)

x=l(mod3)

x=(mod5)

由孙子定理可求得其解为：x三46(mod60)

例3：解一次同余式组

5lx三57(mod75)

3x=l(mod4)

解：用常规方法先求每一个一次同余式的解，得到下列一次同余式组

\x=7,32,57(mod75)

[x三3(mod4)

然后用孙子定理求解，所以同余方程组有3个解，且解分别为

x=7(mod300),x=107(mod300),x=207(mod300)

例4：设2加1是素数，则(尸!尸+(—1)。三0(mod2p+l)

证：设炉2加1,由假设〃为素数，于是由威尔逊定理有(片1)!三T(mod〃)

由于(/L1)!+1=(/?~2)…(炉2)(加1)夕(夕1)…3•2•1+1

=1•(/?-1)•2(/?-2)•2(/?-3)••••(p-1)•p•(n~p)+\

=p\(/7-1)(/7-2)(/7-p)+l=(p!)2(-l)p+l(mod〃)

(p!)O+1=0(modn)

(pl)2+(-1)^=0(mod2加4)

例5：解同余方程28x三21(mod35)

解：・・・(28,35)解⑵,

・・・原同余方程有解，且有7个解

原同余方程等价于4x三3(mod5)

而且4x三3(mod5)解为x三2(mod5)

/.原同余方程解为2,7,12,17,22,27,31(mod35)

＞第五章二次剩余理论

一、主要内容

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

素数模同余方程的解法

二、基本要求

通过本章的学习，掌握平方剩余与平方非剩余的概念，掌握勒让德符号的定义、性质计算

及利用它来判别一个二次同余方程是否有解，对于几个较特殊的勒让德符号的值，要求能掌

握它的推导方法。了解推可比符号的定义，性质及功能，会解素数的模的二次同余方程。及

证明一些二次不定方程无解中的应用。

三、重点和难点

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

（2）勒让德符号，二次互反律。

（3）素数模同余方程的解法。

四、自学指导

对于一般的高次同余方程的求解归纳为模为P”的情形。对于同余方程f(x)三O(modp“)

的求解依赖于f(x)=o(modp)的解。而且对于一般的f(x),求解f(x)=0(modp)的解是

很困难的。本章讨论f(x)为一个整系数的二次三项式时情形。可得到二次同余式的标准形式

x"三a(modp)(a,p)=lp为奇素数。(1)

以下内容都是在标准形式下得到的。其中P为奇素数。

平方剩余和平方非剩余是以同余方程(1)是否有解来定义的。因此平方剩余和平方非剩

余只要在模P的一个简化剩余系中找即可|实际上，模m的全体平方剩余和全体平方非剩余

构成了模P的一个简化剩余系。因为平方剩余和平方非剩余各占一半，旦平方剩余V下列数

列匕2、……(与同余。这为我们提供了计算模P的平方剩余的方法，另一个为欧拉判

别定理a0=l(modp),这个定理的证明依赖于高次同余方程的素数模p,次数等于解数

的条件，再结合欧拉定理即可得到，但缺点是计算量比较大。

为了弥补计算量大的不足，引进了勒让德符号，根据定义可得到一系列性质，其中

’£尸或信卜的p及(#T,21二-1的P的值需要记忆,

P)

即有

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

2、p=8K+l或8K-1时，2是p的平方剩余，p=8K-3或8K-3时，2是p的平方非剩余。

3、对一些较小的素数其平方剩余和平方非剩余列表如下：

P平方剩余平方非剩余

312

51,42,3

71,2,43,5,6

111,3,4,5,92,6,7,8,10

131,3,4,12,9,102,5,6,7,8,11

其余性质要理解，特别是二次互反律的条件为p,g为二个不同的奇素数。勒让德符号

计算的最大困难对a要进行素因数分解，往往很烦，乜很困难。

为了弥补这个困难，再引进雅可比符号，由雅可比符号的定义出发可建立形式上和勒让

德符号完全一致的性质。由于雅可比符号是勒让德符号的推广，因此雅可比符号在这里的主

要功能是为了计算勒让德符号的值。

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

1、已知素数p判别同余方程X2三a(modp)是否有解。

即计算⑷或T。

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

P,\P

3、在的条件下，如何求出(三a(niodp)的解。若小为一个解，则另一个解为-x1。

上述已叙述了问题(1)、(2),现在只剩下解(3)解的方法。除了书上介绍的公方法，我

们再补充另一个方法即高斯逐步淘汰法。

五、例子选讲

补充知识

高斯逐步淘汰法：首先，不妨设0〈a〈p是0〈x〈K,故乂2<三，

24

因解同余方程方三a(modp)(15"|相当于不定方程方二a+py,故0<y=-——,

PP4

因而在求y的值时，不必考虑大于K的整数，这就大大缩小了讨论的范围。

4

其次，任取素数qWp,求出q的平方非剩余为a1，a2...a,并以w,、”....X表示同余方程

a+py=ai(modq),a+py=a2(modq),...

a+py=a.Gnodq)的解，由于平方数一定为任何模的平方剩余，故若取y三v,(modq),则a+py

是q的平方非剩余，因而a+py一定不是平方数。而不能有x2=a+py这样可淘汰满足y=v,(mod

g)的各个y的值。

取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出(1)

的解。

例：解同余方程x"三73(modl37)

解f—.・.x2三73(modl37)有二个解

U37；

因为p=137,故0<yW34

取q=3,则2为3—平方非剩余。

解同余方程

73+137y=3(mod3)

得y三2(mod3),从不大于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,34o

再取q=5,2,3为g的平方非剩余的同余方程

73+137y三2(mod5),73+137y三3(n】