2024年自考初等数论复习

初等数论

初等数论自学安持

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

整除的定义、带余数除法

最大公因数和辗转相除法

整除的深入性质和最小公倍数

素数、算术基本定理

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

习题要求入：2,3；出：4；Pi2：1；Pi7：1，2,5；p20：1o

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

二元一次不定方程QK+勿=C

多元一次不定方程卬玉+a2x2十…〃〃%二c

勾股数

费尔马大定理。

习题要求“29：1，2,4；P31：2,3o

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

同余的定义、性质

剩余类和完全剩余系

欧拉函数、简化剩余系

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

习题要求〃43：2,6；/?46：1；氏9：2,3；打3L2。

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

同余方程概念

孙子定理

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

素数模的同余方程

威尔逊定埋。

习题要求/%：1；/%：1,2；/9：1，2。

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

二次同余式

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

勒让德符号

二次互反律

雅可比符号、

素数模同余方程的解法

/要求P,8:2；Pg]:1,2,3；$:1,2；〃89:2；P93*1。

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

指数的定义及基本性质

原根存在的条件

指标及n次乘余

模2a及合数模指标组、

特性函数

习题要求〃⑵：30

＞第一章整除

一、重要内容

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

两互素、素数、合数、|算术基本定理|、B~aloslhesen筛闰、［x］和｛x｝的性质、n!的标准分解

式。

二、基本要求

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

性质，并能应用这些性质，了解处理整除问题的若干措施，纯熟掌握本章中二个知名的定理:

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

数的定义以及证明素数有无穷多个的措施。能纯熟求出二个整数的最大公因数即最小公倍

数，掌握高斯函数区的性质及其应用。

三、重点和难点

(1)素数以及它有关的性质，判别正整数a为素数的措施，算术基本定理及其应用。

(2)素数有无穷多个的证明措施。

(3)整除性问题的若干处理措施。

(4)[x]的性质及其应用，n!的标准分解式。

四、自学指引

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

成立。因此这一标准作为我们讨论整除性质的基础。乜为我们提供了处理整除问题的措施。

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

题。

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

⑴alb,b|c,贝I」有aIc

(2)alb,aIc,贝:有aImb+nc

读者要纯熟掌握并能灵活应用。尤其要注意，数论的研究对象是整数集合，比小学数学

口非负整数集合要大。

本章中最重要的定理之一为带余除法定理，即为

设a是整数，b是非零整数，则存在两个整数qr,使得

a=bq+r(0<r(Z?)

它能够重作是整除的推广。同时也能够用带余除法定理来定义整除性，(即当余数尸0

时)。带余除法能够将仝体整数进行分类，从而可将|无限的问题转化为有限的问题|。这是一

人很重要的思想措施，它为我们处理整除问题提供了又一条常用的措施。同时也为我们建立

同余理论建立了基础。读者应熟知常用的分类措施，例如把整数可提成奇数和偶数，尤其对

素数的分类措施。例全体奇素数能够提成4k+l,4k+3；或6k+l,6k+5等类型。

和整除性同样，二个数的最大条约数实质上也是用等号来定义的，因此在处理此类问题

时若有必要可化为等式问题,最大公因数的性质中最重要的性质之一为a=bq+c,则一定有

（a,b）=（b,c）,就是求二个整数的最大条约数的理论依照也是处理有关最大条约数问

题的常用措施之一。读者应有尽有仔细体会该定理的证明过程。

互素与两两互素|是二个不一样的概念,既有联系，又有区分。要仔细体会这些有关的性

质，例如，对于任意a,b£Z,可设（a,b）=d,则a=dai,b=dbi,则（ai,bi）=1,于是可对

ai,bi使用对应的定理，要注意，有关定理及推论中互素的条件是常常出现的。读者必须注

意定理成立的条件，也能够例举反例来进行阐明以加深影响。顺便指出，若bIc,bIc,（a,b）

=1,则abIc|是我们处理当除数为合数时的一个措施。好处是不言而喻的。

最小公倍数实际上与最大公因数为对偶命题。尤其要指出的是a和b的公倍数是有无穷

多个。因此一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数中

的最小的正整数。这一点实际上是应用百然数而最小自然数原理即自然数的任何一个子集

一定有一个最小自然数有在。最小公倍数的问题一般都能够通过如下式子转化为最大公因数

的问题。二者的关系为

ab

a,beN,la,b]=M

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

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

处理了两个数的最小公倍数与最大公因数问题后，就能够求出又不数的最小公倍数与最

大公因数问题，能够两个两个地求。即有下面定理

设％,生,…%是n个整数，（4],42）=“2,32，%）=4,…=d〃，则（a,。2,…％）

设［6，。2］=小2,(加2，。3)=加3,…(阳则有［%，〃2,…%］=泄”，

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

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

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

即任何不小于1的整数一定存在一个素因数Po素数有几个属于内在自身的性质，这些性质

是在独有的，读者能够用反例来证明：素数这一条件必不可少。以加深对它们的了解。丽

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

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

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

了处理其他问题的理论保障。它有许多应用，由算术基本定理我们能够得到饱然数的标准分

解问题|。

设二「;巧，b=P?'…p£k,4>0血>0则有

(a,b)=p>…pr九=nin(%•,/7,)

⑶b］=P［…PpO=max(aj,⑸)

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

无轻易的事。对于较特殊的n,例如卜！分解还是轻易的。应用［x］的性质，n!的标准分解

式可由一个详细的公式表示出来这一公式结合［x］的性质又提供了处理带有乘除符号的整

除问题的措施。

本章的许多问题都围绕着整除而展开，读者应对整除问题的处理措施作一简单的小结。

五、例子选讲

补充知识

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

②抽屉原理：

(1)设〃是一个自然数，有〃个盒子，〃+1个物体，把〃+1个物体放进〃个盒子，最少

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

(2)+1个元素，提成女组，最少有一组元素其个数不小于或等于m+1;

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

③梅森数：形如叵耳的数叫梅森数，记成船尸

④费尔马数：〃为非负整数，形如122rl+1］的数叫费尔马数,记成卜,产22"+小

⑤设“P丁…PZ，设〃的正因子个数为d(〃)，所有正因子之和为。(几)，则有

d(n}=(%+1)•(a2+1)…+1)

⑥有关技巧

1.整数表示a=aoxlO"+aixlO〃」+…

卜(一为奇数)

2.整除的常用措施

a.用定义

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

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

d.因式分解

产(4+匕)“2,2天二

e.用数学归纳法

f.要证明a\b,只要证明对任意素数p,〃中p的幕指数不超出。中〃的寨指数即可，

用p(4)表示〃中〃的幕指数，则kl-opW)«〃(/?)

例题选讲

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

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

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

证：设三个连续正数为a,a+1,a+2,而a只有3鼠3k+1,3k+2三种情况，令a=3k,显

然成立，以=3k+1时，a+2=3(k+1),a=3k+2时，a+1=3(k+l)。

例3.证明lg2是无理数。

证：假设怆2是有理数，则存在二个正整数p,q,使得］g2="，由对数定义可得10。=23

q

则有2〃・5。=2夕,则同一个数左边含因子5,右边不含因子5,与算术基本定理矛盾。.\lg2

为无理数。

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

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

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

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

因此只要考虑！中5的事指数，即

5(!)二

例6.证明例!)3叫(叫!

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

(/?!)!中〃的指数£,贝1J

nM

「=(几T喑15rJ,4=6-峪17r)‘之

.型辑2加川国心1)1fW-

k=\P)k=\P)k=i{P)k=\PJ

即〃Na,即左边整除右边。

例7.证明|(+-)

证：*.*=(-1)=Mi+l

=(+1)=M?+1

,•.+_=(M1+M2-I)

由定义I(+-)

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

解：1000=23・53

24—154—1

・・・3(1000尸(3+1)(3+1尸16,o-(1000)=^-一9一9

2—15—1

例9.设c不能被素数平方整除，若团/°,则创〃

证：由已知p(c)W1,且p(4)Wp(/c)

***2P(a)W2pS)+p(c),，p(a)Wp(b)+野

即p(〃)WpS),a\b

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

证：若〃为合数，则设n=ab,(1<a,b<n)

.・・2亚1=(2呼-1=(2"-1)M为合数，与M〃为素数矛盾，

・•・〃为素数。

例11.证明对任意m,〃，m力n,(F%Fm)=1。

r

证：不妨设n>m,则Fn-2=(皿2…-1)(2'+1)=(Fn-i-2)(2门+i)

=Fn-\Fn-2.........F,n-F()

设(FnE„)=d，则距，"/

但Fn为奇数，即证。

例12.设机,几是正整数。证明

证：不妨设爪2几。由带余数除法得

m=qIn+rl,0S04几

我们有

2m-1=2qin+r,-2r,+2。-1=2r,(2q,n-1)+2r,-1

由此及2r1—11—1得,(2m-l,2n-I)=(2n-l,2r*-1)

注意到(犯八)=(wj,若n=o,则(i)=九，结论成立.若r00,则继续对p-1,2。-1)作同样的讨

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

例13.证明：对任意的正整数-成立如下不等式1g心klg2。

其中的是数八的以1()为底的对数，k是八的不一样的素因数(正的)的个数。

证：设n是不小于1的整数(假如八二1,上述不等式显然成立，因k-0),P1,p”...，Pk是八的

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

=PlP2-Pkl.(UU=U,...,/C)，因为P22,(i=1,2,…㈤，从而

n=p；'p?…p}>21'-2l2-2%=2ll+l2+-+lk,

而4+。+...+43k,故H、2”。

将上述不等式取对数(设底a>l)，则有logdAklcga2。

尤具有Ign之klg2o

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

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

证：设整数m的个位、十宜、百位…的数字分别为…，Q”，则由可表作：

n-l

m=at+10a2+100a,+...+10an

n-l个

=Q+a2+a5+...+an)+(9a2+99a,+...+99...9a,J

n-1个

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

个,

因此m-(a1+02+a3+...+4)=9(q+1la3+...+11...Ian)

因为%,%，…，4都是整数，因此任一整数与其数字之和的差必能被9整除。

再设将4,.按没一个次序排成a'i，a'2，a，n»并令

n-1

a=at+a2+...+ant<T'=a'|+a'2+...+a'n,m=«)+IOa2+...+10an>

n

m'=a'i+\Oa2+...+\O-'a'no

依照前面证明的成果，知存在整数A,B,使m-b=9Am5=9B

因为b=h,因此m—M=b+9A—b—9B=9(A—B)。

因为A-B是整数，这就证明了巾-6能被9整除。

注：若对某个整数WKkKn),有a"。，但当初k<i的,*=0,则此时加为整数：

fc_|

m'=a'1+10a'2+...+10a'fc,即m'=a'k...a'2a't。

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

>第二章不定方程

一、重要内容

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

递降法、费尔马大定理C

二、基本要求

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

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

4内+a2x2+…〃二c有解的条件，在有解的条件下的解法。

2、掌握不定方程x2+y2=z?在一定条件下的通解公式，并利用这个通解公式作简单的应用。

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

措施。

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

三、难点和重点

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

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

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

四、自学指引

不定方程重要讲解如下几个问题

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

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

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

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

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

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

到之处。尤其要指出用最大公因数的措施。它的依照是求(a,b)时所得的成果。因为注意

通解公式x=xo-bit,y=yo+a"中ai,bi的意义和位置。以免犯错。

多元一次不定方程。内+的/+…《/〃=c也有类似的成果，但在求解的过程中将它转化

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

的措施一般选择最大公因数的措施。因为n元一次不定方程可转化为个二元一次不定方

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

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

这些限制并不影响其一般性。在条件x>0,y>0,z>0,(x,y)=l,2Ix的条件能够给出x2+y2=z2

的通解公式,x=2ab>y=a2-b2»z2=a2+b2,a>b>0,(a,b)=1,a,b一奇一偶。若将2Ix限为2

Iy,则也有对应的一个通解公式。在证明这个通解公式的过程中，用到了引理u=w?,u>0,

v>0,(u,v)=1,则v=b2,w=ab。a>0,b>0,(a,b)=1。利用这个结论能够求解某

些不定方程。尤其当w=l或素数po则由uv=l或uv=P可将原不定方程转化为不定方程组。

从而取得某些不定方程的解。上述解不定方程的措施叫佣子分福耳希望读者能掌握这种措

施。

为了处理知名的费尔马大定理：xn+yn=zn,n23无正整数解时，当n=4时能够用较初

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

日一组解出发通过结构得出另一组解，使得两组解之间有某种特定的关系，并旦这种结构能

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

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

明不定方程无解要轻易些。证明不定方程无解的证明措施常采取如下形式：(反证法)

若A有解=Ai有解=>&有解n...=>人有解，而4自身无解，这么来结构矛盾。从而

阍明原不定方程无解。

对于证明不定方程的无解性一般在几个措施，一般是总的儿个措施交替使用。尤其要求

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

五、例子选讲

例1：利用整数分离系数法求得不定方程151+10>4-6z=61o

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

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

66

令h=-(-3x+2t/+i)ez,BP-3x+2y-6/i+l=0

6

此0寸y系数最4、，:.y=i(3x++6%_I)=x+-1)

令『2=；(x-1)ez,即x=+1,反推依次可解得

y=x+3/i+/2=2/2+1+3ZI+/2=1+3八+3/2

Z=-2E-2)叶10+ri=6-5/i+1(力

x=1+2t2

・,•原不定方程解为<y=l+3%+3t2tit2£z.

z=6-5t(-l()t2

例2:证明后是无理数

证：假设上是有理数，则存在自数数〃力使得满足­=2»2即/=2〃，轻易懂得。是偶数，

设a=2m,代入得b'=2a；,又得到〃为偶数，a.<b<a,设匕=2%,则a；=2b；,这里与<勾

这么能够深入求得。2,历…且有a>b>a\>h\>a2>b2>...

不过自然数无穷递降是不也许的，于是产生了矛盾，，拒为无理数。

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

证：设N=3〃z±l(m为整数)/.N2=9m2±6/M+1=3(3/w2±2/n)+1

即一个整数若不是3的倍数，则其平方为3A+1,或者说3K2不也许是平方数，设x,.y为勾

股整数，且都不是3的倍数，则都是3A+L但z2=f+)2=3&+2形，这是不也许，

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

例4：求『+)2=328的正整数解

解：:328为偶数，奇偶性相同，即x土)，为偶数，设x+)=2〃,x-y=2v,代入原方程即

为

〃2+,=]64,同埋令W+V=2MI,M-V=2VI有

+12：=82,U|+vx=2%,%-%=2V2

/+达=41,02H2为一偶一奇,且0<U2<6

W2=l,2,3,4,5代方程，有解(4,5)(5,4)

.1•原方程解X-18,y=2,或x=2,y=18。

例5：求X24-XJ,-6=0的正整数解。

解：原方程等价于Q+y)=23故有

...卜=2,卜=3,俨=1,俨=6,,...即有尸2尸1；日,产5.

x+y=3,[x+y=2,[x+y=6,[x+y=\.

例6：证明不定方程f-2冲2+5Z+3=0无整数解。

解：若不定方程有解，则X=U2±&』-5Z_3

但三0,1(mod5),对y,z,)#-5z-3三2,3(mod5)

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

・・・)，4・5z・3不也许为完全平方，即6-5z-3不是整数,因此原不定方程无解。

例7：证明：F+),2+z2=8a+7无整数解

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

注意到对于模8,有

02三0,广三1,22三4,32三1,42三0,52三I,62三4,7：三1,

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

无论1,),2/2怎样变化，只能有人2十),2十z2三0,123,4,5,6(111X18)

而8〃+7三7(mod8),故8a+7不一样余于/+)，+z?有关模8,因此假设错误，即

8a+7w/+y2+z2,从而证明了原方程无解。

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

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

解：由题意立式得：10(h+d-23=100x2d+2c

即98c-19SH=23.

令〃=。-2d得98u-3d=23,

令D=33u-d得前-tz=23

因此〃=23(9为任意整数)，代入得：

d=33〃-12=98D—33x23,(1)

c=u+2d=199V-67x23,

其中U是任意整数。又依照题意要求：d>O,O<c<l(X).

依照⑴,仅当“8时满足此要求，从而d=25,c=5l.

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

>第三章同余

一、重要内容

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

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

二、基本要求

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

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

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

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

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

三、难点和重点

(1)同余的概念及基本性质

(2)完全剩余系和简化剩余系的结构、判别

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

(4)循环小数与分数的互化

(5)特殊数的整除规律。

四、自学指引

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

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

想本质上是将整数按模m分类，然后讨论每一个类中整数所具备的共性及不一样灵乏丽

陋。第一章中用带余除法定理将整数分类处理某些问题的措施只不过是同余理论中的一个

特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故|同余尚有二个等价的定义:

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

相对概念。即它是相对于模m来讲，二个整数a和b有关一个整数模m同余。则对于另一

人整数模n>,a和b未必会同余。

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

述上，还是处理问题的措施上都有了明显的变化，同时也带来了某些新的知识和措施。在引

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

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

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

(i)模不变化的除法，若ak三bk(modm),(k,m)=l7则amb(modm)

(ii)模变化的除法，若ak三bk(modm)(k,m)=d,则a三b[mod?

这一点读者要尤其注意。

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

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

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

在每个剩余类各取一个数组成的m个不一样数的集合，故一组完全剩余系包括m个整数，因

为二个不一样的剩余类中的数有关m两两不一样余，故可得判别一组数是否为模加的一个完

合剩余系的条件有二条为

（1）个数二m

（2）有关m两两不一样余

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

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

当初（见，吗）=1,能由犯的完全剩余系和叫的完全剩余系，结构如/完全剩余系。

为讨论简化剩余系，需要引进欧拉函数。（/〃），欧应函数。（而定义为不超出m且与m互

素的正整数的个数，记为0（加，要掌握。（血的计算公式，了解它的性质。这些性质最重要

的是当（a,b）=1时，二。（6）,和）=p（"—]

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

m的一个简化剩余系。另首先，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系,

一组完全剩余系中与m互索的的数组成的。（/〃）个不一样数的集合称为m简化剩余系。同样

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

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

（2）个数=0（加）

（3）有关m两两不一样余

（3）每个数与m互素

有关ni的简化剩余系也能用己知完全剩余系结构新的简化剩余系。

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

当初（叫，加2）=1，能由町的简化剩余系和叫的简化剩余系,结构〃2M2简化剩余系。

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

理的条件和结论。

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

三IQnodni）

费尔马小定理：若P是素数，则看

ap=Q（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、设4=41000”+611000"7+—即，则7或7或13整除a的充要条件是7或11

或13整除(。0+。2+…)-(。1+。3+…)

五、例子选讲

例1：求3406的末二位数。

解：•・・(3,100)=1,・・・3折三1(mod100)

(100)=0(22•52)=40,,・・3”三l(mol100)

.・.3406^340)10.36=(32)2.32=_19x9=_171=29([nocl100)

・,・末二位数为29。

例2：证明(a+b)，=H+Z/〈modp)

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

由同余性质知有：三a+b5)

又由费尔马小定理有(。+〃)P^a+b(p)

(〃+b)〃三H-f-b'(p)

例3：设素数或2,则2,-1的质因数一定是2P代1形。

证：设。是22-1的质因数，因为2。-1为奇数，・・・q#2.

:.(2q)=1,由条件q|2"T,即2P三1(modq),又丁((7,2)=1,2P=1(modq)

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

若则有力夕则与夕为素数矛盾

/.i=p,/.p[q-l

又二01为偶数,2|^-1,

:.2p\q-\,q-\=2pk,即q=2pk+1

例4：证明13|42田+3”+2

证：V42rt+,+3/,+2=4・16”+9・3”

三3〃(4+9)三13X3〃•三0(13)

/.13|42/,+I+3W+2

例5：证明5产3二/无解

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

有5六3三产(mod5)

即3=^(mod5)

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

・・・3/0,1,4(mod5)

即得矛盾,即5y+3=f无解

例6：求11......1被7除的余数。

50

解：・门11111被7整除，An---…V-…-1-=11(mod7)=4(mod7),即余数为4。

例7：把().04263化为分数。

解：设/尸0.04263,从而1000b=42.63,

100000b=4263.63,9900344263-42

b==里二*

9900011000

当然也可用直化分数的措施做。

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

解：因为9|62XY427

因此916+2+X+Y+4+2+7,即9121+X+Y

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

即111(X-Y+13)

因为OWX,Y<9,因此有2”21+X+Y<39.

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,

222

4=095=1,6三4,72三1,

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

不能不,>2a2怎样变化,只能有能+y2+z2三OJ23,4,5,6(mod8)

而8a+7三7mod8),故8〃+7不一样余于/+)/+z?有关模8

8a+7。+)岸+z?,从而证明了结论。

>第四章同余式

一、重要内容

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

次同余方程组，|孙子定理|高次同余方程|素数模的同余确,|威尔逊定理.

二、基本要求

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

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

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

三、重点和难点

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

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

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

四、自学指引

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

样求解,一般地说，对于一般的同余方程，因为仅有有限个解，只要把模m的一个完全剩

余系一一代入验算总解组则所需的成果。因此上述三个问题已基本处理，只不过详细到某一

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

的解数能够不小于其次O读者能够举出反例来证明这一事实。

要学好同余方程这一章。必须首先搞清同余方程的概念，尤其是同余方程解的概念，相

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

算是老式的，同余方程两边也能够加上模的若干倍。相称于同余方程两边加“零工无论是

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

国

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

的。总结一次同余方程与二元一次不定方程有相称的联系，一次同余方程的求解能够由二元

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

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

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

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

x=bi(modm)

x=b2(modm2)

……(1)

x三bn(modmn)

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

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

同余方程组(1)有解的条件。(叫，m)|b「bj,iWi,

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

求解一次同余方程组(1)有两种措施：|待定系数法|和同子定理|。二种措施各有特长。

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

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

(孙子定理)k>2,叫，叫,.…,mk两两互素，m==1,2,...Z:则一次同余式

x三仇(mod叫\x=b2(modm2),..x="(modmk)的解为

x=+M2M2b2+.,.MkM也(modm\

其中MjM；=l(modmi),i=1,2,…左.

看待定系数法和孙子定理要有深刻的了解。体会其实质，这么无须死记硬背。

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

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

程的解。

求高次同余方程解的基本措施有两条，I一是小模，二是降次。

设m=P\'Pk;则要求f(x)三O(modm)的解只要求f(x)三O(modp。)(2)

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

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

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

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

将x=Xi+pti代入f(x)三O(modp2)有

f(xi+pti)三O(modp?)nf(x】)+ptif‘(x)=0(modp2)

小)

n八"(Y)=0(modp)=t尸+pt2

P

2

代入X=X1+pti=Xi+p(t/+t2p)=x2+p2t2

则x三X2(modp2)即为f(x)三O(modp?)的解。然后重复上述过程，即可由x2得f(x)三

O(modp。)的解x3o最后求出f(x)=0(modp。)的解4

从上所述，核心是求素数模的同余方程f(x)三(Xmodp)的解。

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

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

条件必不可少。

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

素数p的条件也必不可少

本节的辅产品是知名।的wilsom定理。

P为素数，则有(p-1)!三-l(modp),

实际上wiIsom定理的逆定理也成立。故wilsom定理能够作为素数成立重要条件。

五、例子选讲

补充知识

定义1：当(a,m)=1时，若abml(mod〃z),贝！J记b三L(mod〃?)，称为形式分数。

依照定义和记号，则£表示c,关于榜明则有下列性质

cc+mt.L/」、，

1、—三----------(modG乙

aa+

Q

2、若(d,m)=1,且。=必4=阳,则£—(modtri).

a4

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

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

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

同余方程解为

三冬竺三工

17-824-1

x=-2(mod12)

例2：解同余方程组r三6(modl0)

A=1(modi5)

解：•.*(12,10)|6+2,(12,15)|-2-l,(10,15)|6-1

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

x=-2(mod4)

x三-2(mod3)

x=-2(niod4)

x=6(mod2)

<=><x三l(mod3)此时变成模两两互素

x=6(mod5)

x三l(mod5)

x=l(mod3)

x=(mod5)

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

例3：解一次同余式组

5lx三57(mod75)

3x=l(mod4)

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

Jx=7,32,57(mod75)

[x=3(mod4)

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

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

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

证：设〃=2p+l,由假设〃为素数，于是由威尔逊定理有(〃-1)!三TGnod力

因为(止1)!+1三(/7-1)(/7-2)…(加2)(加1)〃(/?-1)…3•2•1+1

=1•(/7-1)•2(/?-2)•2(/?-3)••••(/7-1)[/?-(p-l)]•p•(〃-0)+1

=p\(/7-1)(zr2)(/?-/;)+1=(p!)2(-l);，+l(modri)

(/;/)2(-l)//+1=0(med/i)

:.(pl)2+(-1y=0(mod2/zH)

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

解：・・•(28,35)=7|21,

・•・原同余方程有解，且有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)三O(modp)的解是

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

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

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

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

余只要在模P的一个简化剩余系中及丽丽E模m的全体平方剩余和全体平方非剩余

组成了模P的一个简化剩余系因为平方剩余和平方非剩余各占二分之一，且平方剩余与下

列数列设22,……(-j同余。这为我们提供了计算模P的平方剩余的措施，另一个为欧

拉判别定理a-三l(modp),这个定理的证明依赖于高次同余方程的素数模p,次数等于

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

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

'二或⑶=1的p及仁1卜1,M=-l的p的值需要记忆,

IP)\P)\P)\P)

即有

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

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

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

p平方剩余平方非剩余

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

其他性质要了解，尤其是二次互反律的条件为p,g为二个不一样的奇素数。勒让德符

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

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

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

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

本章重要处理如下三个问题

1、已知素数p判别同余方程/三a（modp）是否有解。

即计算（4卜1或-1。

yP）

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

3、在（三）口的条件卜，怎样求出六三a（modp）的解。若小为一个解，则另一个解为-x1。

上述已论述了问题（1）、（2）,目前只剩余解（3）解的措施。除了书上简介的公措施，我

们再补充另一个措施即高斯逐渐裁减法。

五、例子选讲

补充知识

2

高斯逐渐裁减法：首先，不妨设(Ka〈p是(KX<5,故X2<£,

因解同余方程,三a(modp)(用相称于不定方程x2=a+py,故<—<^

|〃〃4

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

4

其次，任取素数q#p,求出q的平方非剩余为由，为……8并以打，打,……S表示同余方程

a+py三a1(modq),a+p3^=a2(modq),.......

a+py=as(modq)的解，因为平方数一定为任何模的平方剩余，故若取y三Vi(modq),