《初等数论》第三版习题解答

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐《初等数论》第三版习题解答第一章整数的可除性

§1整除的概念·带余除法1．证实定理3

定理3若12naaa，，，都是m得倍数，12nqqq，，，是随意n个整数，则

1122nnqaqaqa++

+是m得倍数．

证实：

12

,,naaa都是m的倍数。

∴存在n个整数12,,

nppp使1122,,

,nnapmapmapm===

又12,,

,nqqq是随意n个整数

1122nn

qaqaqa∴++

+

1122nnqpmqpmqpm=+++

1122()nnpqqpqpm=++

+

即1122nnqaqaqa++

+是m的整数

2．证实3|(1)(21)nnn++证实

(1)(21)(1)(21)nnnnnnn++=+++-

(1)(2)(1)(1)nnnnnn=+++-+又

(1)(2)nnn++，(1)(2)nnn-+是延续的三个整数

故3|(1)(2),3|(1)(1)nnnnnn++-+

3|(1)(2)(1)(1)nnnnnn∴+++-+

从而可知

3|(1)(21)nnn++

3．若00axby+是形如axby+（x，y是随意整数，a，b是两不全为零的整数）的数中最小整数，则00()|()axbyaxby++．

证：

,ab不全为0

∴在整数集合{}|,SaxbyxyZ=+∈中存在正整数，因而有形如axby+的最小整数

00axby+

,xyZ?∈，由带余除法有0000(),0axbyaxbyqrraxby+=++≤则令,22

qq

stabsab=

=-=-，则有02222

bqqq

absta

babbt≤-==-=-则令11

,22

qqstabsab++=

=-=-，则有

若0b而111,22

bb

ttttttb≤

≤∴-≤+≤冲突故11,sstt==当b为偶数时，,st不唯一，举例如下：此时

2

b

为整数11312(),,22222bbbbbbbtt?

=?+=?+-=≤

§2最大公因数与辗转相除法1．证实推论4.1

推论4.1a，b的公因数与（a，b）的因数相同．证：设d'是a，b的任一公因数，∴d'|a，d'|b由带余除法

111222

11

1111,,,,,

0nnnnnnnnnnabqrbrqrrrqrrrqrrrrb

++-=+=+=+==≤，(,)1ab∴=2．证实定理3定理3[][]1212,,||,||,||nnaaaaaa=

证：设121[,,

,]naaam=，则1|(1,2,,)iamin=

∴1|||(1,2,,)iamin=又设122[||,||,

,||]naaam=

则21|mm。反之若2|||iam，则2|iam，12|mm∴从而12mm=，即12[,,,]naaa=122[||,||,,||]naaa

3．设1110nnnnaxaxaxa--++

++（1）

是一个整数系数多项式且0a，na都不是零，则（1）的根只能是以0a的因数作分子以na为

不是有理数．

证：设（1）的任一有理根为

p

q

，(,)1,1pqq=>。则

111

0()()0nnnnpp

p

aaaaqqq

--++++=111100nnnnnnapapqapqaq++

++=（2）

由11110(2)nnnnnnapapqapqaq=+

++，

所以q整除上式的右端，所以|nnqap，又(,)1,1pqq=>，所以(,)1,|nnqpqa=∴；又由（2）有11110nnnnnnapapqapqaq++

+=-

由于p整除上式的右端，所以0|nPaq，(,)1,1pqq=>，所以(,)1,|nnqppa=∴故（1）的有理根为

p

q

，且0|,|npaqa。

220xx=∴-=，次方程为整系数方程，则由上述结论，可知其有有理根只能是

1,2±±为无理数。

=

,p

q

(,)1,1pqq=>，则2

222222222,2,(,)(2,)1pqppqqpqq

=∴=∴==>

但由(,)1,1pqq=>知22(,)1pq=不是有理数。§4质数·算术基本定理1．试造不超过100的质数表解：用Eratosthenes筛选法

（110=a

（2）10内的质数为：2，3，5，7

（3）划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数罗列如下：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

2．求82798848及81057226635000的标准式．

解：由于8|848，所以38|,827988488103498562AAB==?=?，又8|856，所以8|B，3812937322BC=?=?，又4|32，所以4|C，243234332CD=?=?

又9|（3+2+3+4+3+3），所以9|D，29359373DE=?=?，又9|（3+5+9+3+7），所以9|E，93993E=?又3399331331311=?=?所以8532311A=；

同理有3343281057226635000235711172337=???????。3．证实推论3.3并推广到n个正整数的情形．推论3.3设a，b是随意两个正整数，且

1212n

napppααα=??

?，0iα≥，1,2,

,ik=，12

12n

nbpppβββ=???，0iβ≥，1,2,

,ik=，

则1212(,)kkabpppγγγ=???，12

1

2[,]k

kabpppδδδ=???，

其中min(,)iiiγαβ=，min(,)iiiδαβ=，1,2,,ik=

证：

min(,)iiiγαβ=，∴0,0iiiiγαγβ≤≤≤≤

∴|,|iiiiiiiippppγαγβ(1,2)ik=

∴

1

1

i

i

k

k

i

iiippγα==∏∏，1

1

i

ik

k

i

iiippγβ==∏∏.∴12

12|(,)kkpppabγγγ，又明显12

12(,)|k

kabpppγγγ

∴121

2(,)kkpppabγγγ=，同理可得1212

[,]k

kpppabδδδ=，max{,}iiiδαβ=

推广

设11112

112

kkapppβββ=,22122

212kkapppβββ=,12

12,nnnknkapppβββ=

(其中jp为质数1,2,

,,ijka=为随意n个正整数1,2,,,0ijinβ=≥)，则

12

12

121(,,

,),min{},

1,2,,iiik

knijijin

pppaaajkγγγγβ≤≤===

12

12121[,,,],max{},1,2,

,iiik

knijijin

pppaaajkδδδδβ1），则n是2的方幂．证：（反证法）设2(knll=为奇数），则2222

(1)

2(2)2121(2)1(21)[221]k

k

k

k

k

nllll??-?-+=+=+=+-+

+

∵22121(2)121kk

ln+

≥≥+=+;111

00

11

[][][]

1[][][]()[]([]1)[]nnkniiinknnn

ii

nnnnkknkααααααααα=-=--∴+++++=+=+++=-++=+∑∑∑

1

[][]nii

nnαα-=∴+=∑

[证法二]令1

()[][]niifnnααα-==

+-∑,10

11()[][1]()niifnfnnαααα-=++=+-+≡∑

10

11()[][1]()niifnfnnαααα-=++=+-+≡∑

()fα∴是以

1

n

为周期的函数。

又当[0,1),()000,,()0fRfαααα∈=-=∴∈≡时，

即

1

1

[][]ninnαα-=+=∑。

[评注]：[证一]充分体现了常规办法的特点，而[证二]则表现了较高的技巧。3．设α，β是随意二实数，证实：(i)[][][]αβαβ-=-或[]1αβ-+(ii)[2][2][][][]αβααββ+≥+++证实：（i）由高斯函数[x]的定义有

[],[],01;01rsrsααββ=+=+≤>=的非负整数解为Nab??????或1Nab??

+????

证实：当0N>，故00,xy中一正一负，可设0,0xy>≤

原方程的普通解是：()000,1,

xxbt

tyyat=-?=±?

=+?

要求00000,0xy

xbtyattba

-≥+≥?

≥≥-，仅当0ya-

是整数时，才干取0yta??=-????，否则0yta??

>-????

故这个不等式的整数解个数T是：

当是整数时000011xyxyTbaba????????

=--+=++????????????????

因而001xyNNTabbaab????????

=+?=+????????????????

当

0ya不是整数时00001xyxyTbaba????????=--=++????????????????

因而00001xybaNabxyba?????

+?????

???????=?????????

?++?????????

?所以()m?

证实2：二元一次不定方程ax+by=N的一切整数解为00xxbt

yyat=-??=+?

，t∈Z，于

是由x≥0，y≥0得00yxtab-≤≤，但区间00,[]yxab-的长度是

N

ab

，故此区间内的整数个数为

[][]NNab

ab

或+1。

：

4、证实：二元一次不定方程,(,)1,1,1axbyNabab+==>>，当Nabab>--时有非负整数解，Nabab===则不然。

证实：先证后一点，当Nabab=--时，原方程有非负整数解()00,xy则12(,).dmm=

00001,11,1,1,1bxayxbkyahkh?++?+=+=≥≥

(),2abkhabkh?+=+≥，这是不行能的。

次证，当N>ab-a-b时，因(a，b)=1，故原方程有整数解（x0，y0），普通解是{

00(0,1,)

xxbt

yyat

t=-=-=±要求x0-bt≥0，y00at-≥00yx

tab

?-

≤≤会证实存在满足这个不等式的整数0tt=可取使00(0)xbtrrb=+≤+=-∴+≥?≥-这就证实了当Nabab>--时，原方程有非负整数解．1．证实定理2推论。

推论单位圆周上座标都是有理数的点（称为有理点），可以写成

2222

2222222222,,()()abababababababab

--±±±±++++或的形式，其中a与b是不全为零的整数。

证实：设有理数ln

xymm

=

=，（m≠0）满足方程x2+y2=1，即l2+n2=m2，于是得l=±2abd，n=±(a2-b2)d，m=±(a2+b2)d或l=±(a2-b2)d，m=±2abd，

m=±(a2+b2)d，由此得(x,y)=2222

2

2222222

22,,()()abababab

abababab

--±±±±++++或。反之，代入方程x2+y2=1即知这样的点在单位圆周上。

2．求出不定方程2223,(,)1,0,0,0xyzxyxyz+==>>>的一切正整数解的公式。解：设不定方程2223xyz+=,(,)1xy=有解则(1)3/z-x或3/z+x由于2223()()yzxzxzx=-=-+

?3/()()3/zxzxzx-+?-或3/z+x

()()2

2

22

2

3333/3/zxzx

zxzxzxzx

yy

yx

z+-+=?

=?-=+?

+-或者得或

以下不妨设3/zx+

②(),1xz=，设2

2

2

(x,z)d,d/x,d/zd/3

,yxz=?=-则

2

2

2

,3/,9/,9/9/33/dyyxz???若()3/,xy?与(),1xy=冲突!

这样()(

)

2

2

2

3,1/

//3dddy

y

yd

=??而()//,1dxdxyd??=

③(),12zxzx+-=或，(),/()()2tzxzxtzxzxx=+-?+--=设，

()/()()2/2.22tzxzxztxz++-=?=即12tt==或

④若

(),1,,1,3zxzxzxzx+??

+-=-=

???

则()()()2

2

33

zx

zxzxzxyy

+=+-?

=

?-从而由引理可设

2,3

zxa+=2

,zxyabb-==从而≡，为证得,xz为整数，(),1,xz=必需有a，b均为奇数，且2

2

3a

b>

⑤若(),2,1,12262zxzxzxzxzxzx+-+-????

+-=?=?=

??????

()()2

2

3262yzxzxzxzxy

+-??

=+-?=?

???

从而设

222222

,,,3,2,3622

zxzxyabxyabzababab+-====-==+即，其中,ab为一奇一偶，且有(),1

ab=

4．解不定方程：x2+3y2=z2，x>0，y>0，z>0，(x,y)=1。

解：设(z-x,z+x)=d，易知d=1或2。由(z-x)(z+x)=3y2得z-x=3da2，z+x=db2，y=dab或z-x=db2，z+x=3da2，y=dab，a>0，b>0，(a,b)

=1。(ⅰ)当d=1：2222

|3|322

babaxyabz-+===，，，a>0，b>0，(a,b)=1，3|/b，a,b同为奇数；(ⅱ)当d=2：x=|b2-3a2|，y=2ab，z=b2+3a2，a>0，b>0，(a,b)=1，3|/

b，a,b一奇一偶。反之，易验证(ⅰ)或(ⅱ)是原

不定方程的解，且x>0，y>0，z>0，(x,y)=1。3．证实不等式方程

()2

2

4

,,1,0,0,/xyxyzxyxz+

==>>的一切正整数解．

可以写成公式:2

24(

),xaba

b=-y=∣442

2

6aba

b

+-∣，2

2

za

b=

+

其中()0,0,,1,,ababab>>=一单一双证实:由定理1知道原方程的解是2

222

2,,,xcdyzc

dcd==

-=+

()0,,1cdcd>>=，且c，d为一奇一偶，

其中，()2

2

2,,0,,1cabdababa

b==->>=，且a，b为一奇一偶．

所以2

2

4(

),xaba

b=-y=∣4

4

2

2

6aba

b

+-∣，2

2

za

b=

+是原方程的正整数解

()2

2

(0,0,0,,1,2/,xyzxyxab>>>=+且是奇数，

原方程正整数的解有:

()000,，

，()2

0,aa±±，

，()2

,0,aa±±()2

2

4

4

2

2

2

2

4(),(6),()ababababab±-±+-±+，()4

4

2

2

2

2

2

2

(6),4(),(),ababababab±+-±-±+

6．求方程x2+y2=z4的满足(x,y)=1，2∣x的正整数解。

解：设x，y，z是x2+y2=z4的满足(x,y)=1，2∣x的正整数解，则x=2ab，y=a2-b2，z2=a2+b2，a>b>0，(a,b)=1，a,b一奇一偶，再由z2=a2+b2得a=2uv，b=u2-v2，z=u2+v2或a=u2-v2，b=2uv，z=u2+v2，u>v>0，(u,v)=1，u,v一奇一偶，于是得x=4uv(u2-v2)，y=|u4+v4-6u2v2|，z=u2+v2，u>v>0，(u,v)=1，u,v一奇一偶。反之，易验证它是原不定方程的整数解，且x>0，y>0，z>0，(x,y)=1，2∣x。

其中正负号可随意选取．第三章同余

ξ1同余的概念及其基本性质

1、证实（i）若1

k

ααA≡1k

α

αB(modm)

xi≡yi(modm)、i=1，2，、、、，k则

1

1

1

11,,1

1,,1,,

kkkk

k

k

kx

xyyααααααααααα

α

A≡

B∑∑(modm)

特殊地，若iiab≡（modm），i=0，1，

,n则

111010nnnnnnnnaxaxabxbxb++≡++

+（modm）

(ii)若a≡b(modm)，k0,(mod),akbkmk>≡

（iii）若a≡b(modm)，d是a，b及m的任一正公因数，则(mod),abm

bdd

≡(iv)若a≡b(modm)，,0.dmd>则a≡b(modd)．证实：（i）据性质戊，由(mod),1,2,,.iixymik≡=

得(mod),1,2,,,iiiixymikαα≡=

进一步，则

1

1

1

1

11

(mod)k

k

kkkkxxByymα

ααααααααA≡

最后据性质丁，可得：

1

1

1

11,,1

1,,1,,

kkkk

k

k

kx

xyyααααααααααα

α

A≡

B∑∑（modm）

(ii)据定理1，a≡b(modm),mab?-

0,()kmkkabkakb>∴-=-

又据定理1，即得(mod).kakbmk≡

（iii）据定理1，a≡b(modm),mab?-即a-b=ms(s∈z)

,,,0,abmdabmdsdd->∴

=，即,abm

sddd-=?仍据定理1，立得(mod),abm

bdd≡

(iv)据定理1，a≡b(modm),(),aamssz?-=∈

又

,,,dmmdttz∴=∈

故(),,abmsdststz-==∈

(mod).abd∴≡

2、设正整数1101010,010nnnniaaaaa--=++

≤>>

故有限步后，必有(mod)naxym≡其中0,,nm

xyττ

≤≤≤

即结论成立。

2.ξ孙子定理

试解下列各题：

（i）十一数余三，七二数余二，十三数余一，问本数。（ii）二数余一，五数余二，七数余三，九数余四，问本数。（杨辉：续古摘奇算法（1275））。

解：（i）依题意得3(mod11)

2(mod72)1(mod13)xxx≡??

≡??≡?

则据孙子定理，上述方程组有唯一解(mod117213)??

由112

23

372731(mod11)1;11131(mod72)1;11721(mod13)1;MMMMMM''?≡=''?≡=-''?≡=-得得得故原方程组的解是39362(1)1431(1)7921730(mod10296).x≡?+?-?+?-?≡

(ii)依题意得1(mod2)2(mod5)3(mod7)4(mod9)

xxxx≡??≡?

?≡??≡?

13152126369044703307157(mod630).x?≡?+?+??+??≡≡

2、（i）设123,,mmm是三个正整数，证实：

([])(1323123

(,),(,),,mmmmmmm=????．

（ii）设12(,).dmm=证实：同余式组1122(mod),(mod)xbmxbm≡≡（1）有解的充分与须要条件是12.db-

在有解的状况下，适合（1）的一切整数可由下式求出：

[]()1,212mod,xxmm≡

其中1,2x是适合()1的一个整数。

()iii应用()(),iii证实同余式组()mod,1,2,

,iixbmik≡=()2

有解的充分与须要条件是(,)|(,),,1,2,,ijijmmbbijk=，并且有解的状况下，适合(2)的一切

整数可由下式求出：

[]1,2,

,12(mod,,)k

kxxmmm=

其中1,2,

,k

x是适合(2)的一个整数。

证实：()i[]1323132313231323123(,)(,)(,)(,)

(,),(,)((,),(,))(,,)

mmmmmmmmmmmmmmmmmmm=

=

[]1212312132312

1233121212(,(,))(,,)(,,)(

,)(,)(,)(,)

mmmmmmmmmmmmmmmmmmmmmmm===

123121323123121231312323222222

12121313232312312132321131223232222212122323131(,,)(,,)

((,,),(,,),(,,))

(,,,,,,)(,)()()(,,,)(,)

(,,,,,mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm====23123,)

mmm

∴123121323121323(,,)(,,)(,)(,)(,)mmmmmmmmmmmmmmm=即

132312132312312(,)(,)(,,)

(,,)(,)

mmmmmmmmmmmmmmm=

∴[][]1323123(,),(,)(,,).mmmmmmm=

()ii设(1)有解c，即1122(mod),(mod)cbmcbm≡≡

故此得1212(mod(,))bbmm≡，须要性成立；反之，设12|dbb-即12(mod)bbd≡

则由§1定理，知方程1212(mod)mybbm≡-必有解，设其解为02(mod)yym≡，即10212(mod)mybbm≡-令1,2110xbmy=+则易见：

1,211(mod)xbm≡且1,222(mod)xbm≡

即(1)有解1,2x，充分性得证。进一步，若(1)有解,xy，则

12(mod),(mod)xymxym≡≡

即xy-是12,mm的公倍数，固然也是[]12,mm的倍数，

∴[]12(mod,)xymm≡

故若1,2x是(1)的一个解，则(1)的任一解x必满足

[]1,212(mod,)xxmm≡。

()iii若同余式组(mod),1,2,

,iixbmik≡=有解，

则(mod)(mod)iijjxbmxbm≡???≡??也有解。从而由()ii知必有

(,)|(,),1,2,

,ijijmmbbik=，须要性成立。

下证充分性。首先，推()i，用归纳法易证：

[][]121121(,),(,),,(,)(,,,,)kkkkkkmmmmmmmmmm--=

又由()ii知2k=时，充分性也成立；

现设同余式组1111(mod)(mod)

kkxbmxbm--≡??

??≡?

有解[]11(mod,

,)kxbmm-≡，

即(mod),11iibbmik≡≤≤-。

设,11iiibblmik=+≤≤-；又由条件知(,)|()ikikmmbb-，

而()ikkiibbbblm-=-+，从而(,)|,11ikikmmbbik-≤≤-，所以241(mod16)x≡，即[]121(,,

,,)kkkmmmmbb-=-，

又由()ii，则同余式组[]11(mod,,)(mod)

kkkxbmmxbm-?≡?

?≡??，

必有解[]11(mod,

,,)kkxcmmm-≡（※）

明显(mod),1iicbmik≡≤≤，即（※）就是同余式组(2)的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。

§3高次同余式的解数及解法

1、解同余式3262717200(mod30)xxx+++≡。

解：原同余式等价于2320(mod2)(1)

220(mod3)(2)220(mod5)(3)xxxxxx?+≡?

+≡??++≡?

(1)0,1(mod2)x≡有解(2)2(mod3)x≡有解(3)0,1,2(mod5)x≡有解

11223(mod2)0,1(mod3)

23(mod5)0,1,2

xbbxbbxbb≡=??

≡=??≡=?

联立

据孙子定理，可得12315106(mod30)xbbb≡++

故原同余式共有6个解是：

12345620,5,26,11,2,17,(mod30)xxxxxx≡≡≡≡≡≡

2、解同余式433157961910(mod225)xxx+++≡

解：

2222535=?

故原同余式等价于432432

43620(3)67490(mod5)

xxxmodxxx?+++≡?

?+--≡??1）先解4343620(mod3)xxx+++≡

即410(mod3)x-≡得1(mod3)x≡±

32()1696(1)31,331

(1)1,3(1)

fxxxff''=++?=I'-=-I-

1121122222212(1)

(1)5(mod3)1(mod3).3

134(mod3);(1)5(mod3)2(mod3)135(mod3);4,5

(mod3).ffttxtfttxtxx'≡-

=-?≡∴≡+≡'-≡-?≡∴≡-+≡≡≡由又由即第一式有两个解

②再解43()67490

(mod5)gxxxx≡+--≡

即43210(mod5)xxx+++≡

设1,

2(mod5).x≡

32()24214.

(1)41.

(2)272,gxxxgg'''=+-==

而541

5272II

1122410(mod5)0(mod5)

27227(mod5)4

(mod5)

tttt≡?≡≡-?≡由

231

12

21,3

(mod5).

(mod9)4,5(mod25)

1,3

xxbbxbb∴≡-≡=??

≡=-?其次式有两个解联立

由孙子定理设12100126(mod225)xbb≡+

即原四条式有4个解是76,22,176,122(mod225).x≡

§4．质数模的同余式

补充例子：1．解同余方程：

(ⅰ)3x11+2x8+5x4-1≡0(mod7)；(ⅱ)4x20+3x12+2x7+3x-2≡0(mod5)。

解：(ⅰ)原同余方程等价于3x5+5x4+2x2-1≡0(mod7)，用x=0，±1，±2，±3代入知后者无解；(ⅱ)原同余方程等价于2x4+2x3+3x-2≡0(mod5)，将x=0，±1，±2代入，知后者有解x≡±1(mod5)。2．判定

(ⅰ)2x3-x2+3x-1≡0(mod5)是否有三个解；(ⅱ)x6+2x5-4x2+3≡0(mod5)是否有六个解？

解：(ⅰ)2x3-x2+3x-1≡0(mod5)等价于x3-3x2+4x-3≡0(mod5)，又x5-x=(x3-3x2+4x-3)(x2+3x+5)+(6x2-12x+15)，其中r(x)=6x2-12x+15的系数不都是5的倍数，故原方程没有三个解；(ⅱ)由于这是对模5的同余方程，故原方程不行能有六个解。

定理5若p是素数，n∣p-1，p|/a则

xn≡a(modp)(14)

有解的充要条件是

1

pn

a

-≡1(modp)。(15)

若有解，则解数为n。

证实须要性若方程(14)有解x0，则p|/x0，由Fermat定理，得到

110

()

ppnn

n

a

x--≡=x0p-1≡1(modp)。

充分性若式(15)成立，则

1111

1(()

1)

()()(1)ppppn

n

n

n

pnn

x

xxxaaxaPxxa

=-+-=-+-，

其中P(x)是关于x的整系数多项式。由定理4可知同余方程(14)有n个解。证毕。

1、设n︱1p-，1n>，(,)1ap=．证实同余式(mod)nxap≡

有解的充分须要条件是11(mod)pn

a

p-≡，并且在有解的状况下就有n个解。

证实：0)(mod),xxp?≡若同余式有解，令其解为设01.(,)1,(,)1pknapxp-==∴=则1001(mod)pknxxp-=≡

但10(mod)pxa

p-≡

1101

(mod);ppn

a

xp--∴≡≡

1)1(mod)pn

a

p-?≡则由(mod)n

xa

p≡可得11

1(mod)ppn

x

a

p--≡≡。

它有1p-个解。

n又︱1p-

令11

21(1)(1)2()pppnpnnnn

gxxaxaxa??=+++????

则1()()0

(mod)pnxxagxp-=-≡

()0(mod)gxp≡

无多于(1)pn--个解，而110

(mod)pxp--≡恰有1p-个解，

10(mod)pxap--≡必有n个解。

2．设n是整数，（a，m）=1，且已知同余式(mod)nxam≡

有一解0(mod)xxm≡，证实这个同余式的一切解可以表成0(mod)xyxm≡

其中y是同余式1(mod)nym≡的解。

证实：设01,(mod)xxxxm≡≡均是(mod)nxam≡的解，则10(mod)nnxxam≡≡，

（a，m）=1，∴（0x，m）=(1x，m)=1

则由第三章定理3．3知，必存在y，使01(mod)yxxm≡，

∴010(mod)nnnnyxxxm≡≡．

故原同余式的任一解可表示为0(mod)xyxm≡而y满足1(mod)nym≡

3．设(a,m)=1，k与m是正整数，又设x0k≡a(modm)，证实同余方程

xk≡a(modm)

的一切解x都可以表示成x≡yx0(modm)，其中y满足同余方程yk≡1(modm)。解：设x1是xk≡a(modm)的随意一个解，则一次同余方程yx0≡x1(modm)有解y，再由yka≡ykx0k≡(yx0)k≡x1k≡a(modm)得yk≡1(modm)，即x1可以表示成x≡yx0(modm)，其中y满足同余方程yk≡1(modm)；反之，易知如此形式的x是xk≡a(modm)的解。

第五章二次同余式与平方剩余§1普通二次同余式

1、在同余式20(mod)yApα-≡中，若|pAα，试求出它的一切解来。解：若|pAα，则0(mod)Apα≡，上同余式即为

20(mod)ypα≡

从而2|pyα，即有2|p

yα??

????

。

易见，当2αβ=为偶数时，2αβ??

=????

，则2ppαβ??

????=，上同余式有解：

0,,2,,(1)(mod)xpppppββββα≡-，共有21nmp=+的解为111,12,1,12(mod2)xααα--≡+21(mod)10(mod)iiiixpxpαα≡?+≡或10(mod)iixpα-≡

二者不能同时成立，否则2p=冲突

故它有两个1(mod),1,2,

,iixpikα

≡±=

解，联立方程组即可求出一切解。

第六章原根与指标

1.设p是单质数，a是大于1的整数，证实:

(i)pa1-的奇质数q是a-1的因数或是形如2px+1的整数，其中x是整数(ii)pa1+的单质因数是a+1的因数或是形如2px+1的整数，其中x是整数证实(i)设qpa1-则pa1(mod)q≡设a对模q的质数是δ

P是质数从而1δ=或p

若1δ=，则pa1(mod)q≡，故qpa1-;若pδ=，而δ()qq1φ=-，q-1为偶数，

记q-1=2x，则p2x，又假设px故q=2px+1得证。

(ii)设q为1pa+的奇质因数，则1(mod)paq≡-

从而21(mod)paq≡，从而a对模q的指数2pδ．故1δ=，2，p，2p之一若1δ=，则1(mod)aq≡，从而1(mod)paq≡即有11(mod)q≡-，不行能，故1δ≠

若2δ=，则21(mod)aq≡，而2a≡1(mod)q(否则1δ=)故1(mod)aq≡-?1qa+

若pδ=，则1(mod)paq≡，而有11(mod)q≡-，不行能若2pδ=，则由()1qqδ?=-，q－1＝2m?pm记m＝px，则q＝2px+1，得证

2.设a对模m的指数是δ，试证aλ对模m的指数是(,)

δ

λδ证实：设aλ对模m的指数为γ，则()1(mod)aamλγλγ=≡

?δλγ?kλγδ=?

(,)(,)

δλ

γλδλδ

而,1(,)(,)δλλδλδ??=?

??

，股(,)δ

γλδ反之()

()

()

()

()

(),,,1modaa

a

mλδλδλδλδ

λδλδ==≡

故(),δ

γλδ，从而γ=()

,δλδ得证

例1求1，2，3，4，5，6对模7的指数。按照定义1直接计算，得到

δ7(1)=1，δ7(2)=3，δ7(3)=6，

δ7(4)=3，δ7(5)=6，δ7(6)=2。

例1中的结果可列表如下：

这样的表称为指数表。这个表就是模7的指数表。

下面是模10的指数表：

1．写出模11的指数表。

解：经计算得δ11(1)=1，δ11(2)=10，δ11(3)=5，δ11(4)=5，δ11(5)=5，δ11(6)=10，δ11(7)=10，δ11(8)=10，δ11(9)=5，δ11(10)=2，列表得

2．求模14的所有原根。

解：x≡3，5(mod14)是模14的所有原根。

1．求模29的最小正原根。解：因?(29)=28=22?7，由

(29)

(29)

14

47

2

2

21(mod29)2

21(mod29)φφ=≡=≡//，

知2是模29的最小正原根。

2．分离求模293和模2?293的原根。

解：由2是模29的原根及229-1=228=228≡

/1(mod292)知2是模293的原根；

由2是模293的原根及2是偶数知2+293是模2?293的原根。3．解同余方程：x12≡16(mod17)。

解：易得3是模17的原根，3i（i=0,1,2,,15）构成模17的简化剩余系，列表为

由上表知38≡16(mod17)，设x≡5y(mod17)，则12y≡8(mod16)，由此解得y1≡2，y2≡6，y3≡10，y4≡14(mod16)，查上表得x1≡9，x2≡15，x3≡8，x4≡2(mod17)。

ξ3指标及n次剩余

1．设12,,,nqqq???是()m?的一切不同的质因数，证实g是模m的一个原根的充要条件是g对模m的(1,2,,)iqin=???次非剩余。证实：须要性，设g为模m的一个原根由ξ2Th5知()1(mod),1,2,,mgmim?≡=???

若g为模m的iq次剩余，则存在0x，使得

00(mod),(,)1iq

xgmxm≡=

又由欧拉定理()01(mod)mxm?≡

故()

()

()00()

1(mod)qi

i

immqqmg

xxm???≡=≡，冲突！

充分性，若g不为模m的一个原根，由ξ2Th5知

存在tq，使得：()

1(mod)t

mqg

m?≡

设'g为模m的一个原根，则对上式两边关于'g取指标：

'()

0(mod())gt

mIndgmq??≡

'0(mod)tgIndgq?≡

记'tgIndgqγ=，则由指标的定义即有：

'()(mod)tq

ggmγ≡

故'()(mod)xgmγ≡即为同余式(mod)tq

xgm≡的解

从而g为tq次剩余，冲突。

2．证实10是模17及模257（质数）的原根，并由此证实把11

,

17257

化成循环小数时，循环节的长度分离是16及256．

证实：(17)16?=，它的有且惟独质因子2，而()3610251721117171755??????????

==-==-

????????????????

从而10不是模17的平方剩余，由上题知10是模17的原根。

8(257)2562?==，由且仅有质因子2，而

10252572125725725755??????????====-????????????????

故同上理10也是模257的原根。由ch3§42.3Th的证实可知，

117，1

257

的循环节的长度，t，这是10关于模17，模257的指数，从而

t=16，256证毕3．试利用指标表解同余式

1514(mod41)x≡

解：同余式1514(mod41)x≡等价于：

15Ind14(mod41)xInd≡

查表知1425Ind=，故：

15Ind25(mod40)x≡

因为()15,405|25=，故上式由5个解，解之得：Ind7,15,23,31,39(mod40)x≡查表知：原同余式的5个解为：29,3,30,31,7(mod41)x≡

4．设模m（m．>2）的原根是存在的，试证对模m的任一原根来说，1-的指标总是1()2

m?．证实：模m的原根存在，故m=4，pα或2pα设g为模m的一个原根，则()1(mod)mgm?≡从而1

1

()()2

2

(1)(1)0(mod)mmg

g

m??-+≡()*

()i若m=4，()42?=，则模m有且惟独一个原根3，

131(mod)m≡-，故1-的指标为()

12

m?=

()11μ=若mpα=，p为奇质数，则由()*知()90μ=或1

()2

|1mpg

?+

但二者不能同时成立，否则1

1

()()2

2

|(1)(1)2mmpgg

??+-=，冲突!

若1

()2

|1,|mpg

p?-1

()2

1,mg

?+又由（*）知

1

()2

|mpg

?α

1

()2

1mg

??≡（modm），与g的指数为()m?冲突。

从而|p1

()2

1,mg?-1

()2

|1mpg

?+，从而1

()2

|1mpg

?α

+

1

()2

1mg

??≡-（modm）

故-1的指标为1()2

m?。

()iii若2mpα=，g为2pα的原根，则g为奇数

类似于()ii的研究，我们有

|pα

1

()2

1mg

?-，1

()2

|1mpg

?α

+

从而1

()2

2|1mpg?α

+

从而1

()2

1mg

?≡-（modm）故-1的指标为1()2

m?。

5、设g，1g是模m的两个原根，试证：()i111ggindgindg?≡（mod()m?）；()ii11gggindaindginda≡?（mod()m?）。证实：()i由指标的定义知：

1

1gindgg

g≡（modm）

两边对原根1g取指标：

1

111gindgggindg

indg≡（mod()m?）

故111ggindgindg?≡（mod()m?）

()ii由指标的定义知：

11

ginda

ga≡（modm）

两边对原根g取指标：1ginda

ggindg

inda≡（mod()m?）

故11gggindaindginda≡?（mod()m?）。（证毕）

第九章数论函数§1．可乘函数

1．设()fx是一个可乘函数，证实()()dx

Fxfd=∑也是一个可乘函数．由此说明(),

()saaτ是

可乘函数．

证实：首先我们证实：设12(,)1xx=，若1d跑过1x的所有因子，2d跑过2x的所有因子，则12

ddd=跑过mn的所有因子，事实上，由于1122,dxdx，故1212ddxx，且当''1122,dxdx，

{}{}''

1212,

,dddd≠时，因为12(,)1xx=，得''1212dddd≠，反之任给12dxx，因为12(,)1xx=，

设

11

(,)dxd=，

22

(,)dxd=，明显

121122

,,ddddxdx=．因此

12

1122

1212(,)()()dxxdxdxFxxfdfdd=

=∑∑∑

1122

1

2

()()dxdxfdfd=∑∑

11

22

1

2

1

2

()()()()dxdxfdfdFxFx=

=∑∑

故()Fx为一个可乘函数．(此为65页)

若()fxx=，它为可乘函数．，且()()()da

FafaSa==∑．

若()1fx=，它为可乘函数，且()()()da

Fafdaτ==∑．

故(),()Saaτ为可乘函数．

2．设()fx是一个定义在一切正态数的函数，并且()()dx

Fxfd=

∑是一个可乘函数，证实

()fx是可乘函数．

证实：反证，假设()fx不是可乘函数，则存在一对正态数,,(,)1mnmn=，使得

()()()fmnfmfn≠，于是我们可以挑选这样一对,mn，使得mn最小．若1mn=，则

(1)(1)(1)fff≠，

即(1)1f≠，又1

(1)()(1)dFfaf==∑，()Fx为可乘函数，故有(1(1)1fF==冲突！

若mn>1，则对全部正态数对a,b,(a,b)=1,ab一定为的一个解B．()()

0mod,1,()0modpfxpχχ??≡?>≡一定为的一个解

C．()()

()00(),()0modmod,modpfxfxpxxpxxpααα≡≡≡当不整除时一定有解其中D．()()

()00mod()0mod,modxxpfxpxxpααα≡≡≡若为的一个解则有10．()10(),,0mod,,nninfxaxaxaaapnp=+

++≡>/设其中为奇数则同余式

()()0modfxp≡的解数：

（）A．有时大于p但不大于n;B．可超过p

C．等于p

D．等于n

11．若2为模p的平方剩余，则p只能为下列质数中的:()

A．3

B．11

C．13

D．2312．若雅可比符号1am??

=

???

，则()A．()2mod,xam≡同余式一定有解

B．()()2,1,modamxap=≡当初同余式有解;

C．()2(,modmpxap=≡当奇数)时同余式有解;

D．()2(),modapxap=≡当奇数时同余式有解．

13．()

()2mod2,3,2,1,xaaαα≡≥=若同余式有解则解数等于()

A．4

B．3

C．2

D．114．模12的全部可能的指数为;()

A．1，2，4

B．1，2，4，6，12

C．1，2，3，4，6，12

D．无法确定15．若模m的单根存在，下列数中，m可能等于:()A．2B．3C．4D．1216．对于模5，下列式子成立的是:()

A．322ind=

B．323ind=

C．350ind=

D．3331025indindind=+17．下列函数中不是可乘函数的是:()A．茂陛鸟斯(mobius)函数w(a);B．欧拉函数()aφ；

C．不超过x的质数的