初等數(shù)論練習(xí)題答案

初等數(shù)論練習(xí)題一

一、填空題

1、d(2420)=J2;夕(2420)=880

2、設(shè)a,n是大于1的整數(shù)，若an-l是質(zhì)數(shù)，則a=^.

3、模9的絕對最小完全剩余系是"4,-3,-2,-10123,4}.

4、同余方程9x+12三0(mod37)的解是x三ll(mod37)。

5、不定方程18x-23y=100的通解是x=900+23t,y=700+18tfZ。.

6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個數(shù)為一包。

7、18-被*2除的余數(shù)是256。

9、若p是素數(shù)，則同余方程x-l(modo)的解數(shù)為pT。

二、計算題

1、解同余方程:3x11x200(mod105)0

解：因105=357,

同余方程3x21x200(mod3)的解為x1(mod3),

同余方程3x，lx380(mod5)的解為x0,3(mod5),

同余方程3x211x200(mod7)的解為x2,6(mod7),

故原同余方程有4解。

作同余方程組：xb\(mod3),xZ>2(mod5),xbA(mod7),

其中b\=1,A=0,3,&=2,6,

由孫子定理得原同余方程的解為x13,55,58,100(mod105)0

2、判斷同余方程x2三42(modl07)是否有解？

故同余方程X?三42(mod107)有解。

3、求(127甲+34)28除以in的最小非負(fù)余數(shù)。

解：易知1271三50(mod111)。

由502三58(mod111),503=58X50=14(mod111),5。9三14?三80(mod111)

知5028三(5()9)3x50三803X50三803X50三68X50三70(mod111)

從而5()56三16(modm)o

故(127戶6+34)28三(16+34)28=5028=70(mod111)

三、證明題

1、已知p是質(zhì)數(shù)，(a,p)=l,證明：

(1)當(dāng)a為奇數(shù)時，ap-1+(p-l)a=0(modp)；

(2)當(dāng)a為偶數(shù)時，a「T-(p-l)a三0(modp)。

證明：由歐拉定理知址-三1(modp)及(p-l)a三-1(modp)立得(1)和(2)成立。

n+2

2、設(shè)a為正奇數(shù)，n為正整數(shù)，試證a2"=i(m0d2)0.........(1)

證明設(shè)a=2m1,當(dāng)〃二1B寸，有

a=(2/771)2=4/77(/771)11(mod23),即原式成立。

2k

設(shè)原式對于〃=A成立，則有a1(mod2*i)/*=i或…，

其中qZ,所以a2k+'=(1或…T=1q2…1(mod2…)，

其中q是某個整數(shù)。這說明式⑴當(dāng)〃=41也成立。

由歸納法知原式對所有正整數(shù)〃成立。

3、設(shè)p是一個素數(shù)，且lWkWp-1。證明：C；,_,(-1)k(modp).

證明：設(shè)A=C3=(〃IX〃2)-一(/D得：

k\

k!?A=(p-l)(p-2)(p-k)=(-1)(-2)???(一k)(modp)

又(k!,p)=1,故人=C；_1(~1)k(modp)

4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6=l(mod84)o

說明：因為84=4義3義7,所以，只需證明：

p6=l(mod4)p6=l(mod3)p6=l(mod7)同時成立即可。

證明：因為84=4X3X7及p是不等于3和7的奇質(zhì)數(shù)，所以

(p,4)=1,(p,3)=1,(p,7)=1o

126

由歐拉定理知：p=p=l(mod4),從而p=l(mod4)o

同理可證：p6=l(mod3)p6=l(mod7)o故有三l(mod84)。

注：設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6^l(mod168)o(見趙繼源p86)

初等數(shù)論練習(xí)題二

一、填空題

1、d(1000)=16：0(1000)=2340.

2、2010!的標(biāo)準(zhǔn)分解式中，質(zhì)數(shù)11的次數(shù)是199..

3、費爾馬(Fermat)數(shù)是指Fn=22"+1,這種數(shù)中最小的合數(shù)Fn中的n=5o

4、同余方程13x三5(mod31)的解是x三29(mod31)

5、分母不大于m的既約真分?jǐn)?shù)的個數(shù)為(2)+(3)+...+(力)。

6、設(shè)7](80勺),則最小的正整數(shù)n=逸一

7、使41x+15y=C無非負(fù)整數(shù)解的最大正整數(shù)C=559.

9、若夕是質(zhì)數(shù)，np1,則同余方程x"1(modp)的解數(shù)為此

二、計算題

1、試求200220032004被19除所得的余數(shù)。

解：由2002三7(mod19)20022=ll(mod19)20023=1(mod19)

又由20032。04三2曲4三(22)1002=1(mod3)可得：

3n+13n

200220032aM=2002=(2002)X2002=7(mod19)

2、解同余方程3/4/6x180(mod5)。

解：由Fermat定理，z5x(mod5),因此，原同余方程等價于2Vx30(mod5)

將x0,1,2(mod5)分別代入上式進行驗證，可知這個同余方程解是x1(mod5)?

3、已知a=5,m=21,求使a*1(modm)成立的最小自然數(shù)x。

解:因為(5,21)=1,所以有歐拉定理知5⑵』l(mod21)。

又由于(21)=12,所以x|12,而12的所有正因數(shù)為1,2,3,4,6,12。

于是x應(yīng)為其中使5*1(mod12)成立的最小數(shù)，經(jīng)計算知：x=60

三、證明題

1、試證13|(54m+46n+2000).(提示：可取模13進行計算性證明)

證明：54m+46n+2000252m+642n+2000(-1)2m+(-1)2n+200020020(mod13)。

2>證明Wilson定理的逆定理：若〃〉1,并且(A1)!1(modn),則〃是素數(shù)。

證明：假設(shè)〃是合數(shù)，即〃=nm，1<6<n,由題設(shè)易知(A1)!1(modm)，得

01(mod“)，矛盾。故〃是素數(shù)。

3、證明：設(shè)外表示全部由1組成的s位十進制數(shù)，若總是素數(shù)，則s也是一個素數(shù)。

證明：假設(shè)S是合數(shù)，即5=2卜ka,b<s0則

...105-1(10")6-110"-1..甘曰T敝物

億=111=—--=---=—---M,具?HM>1是正整數(shù)。

由夕">1也是正整數(shù)知外是合數(shù)，這與題設(shè)矛盾。故s也是一個素數(shù)。

4、證明：若2P1是奇素數(shù)，貝U3)2⑴"0(mod2pl)o

證明:由威爾遜定理知1(2p)!=p!(p1)(2。)⑴〃(p!)2(mod2P1),

由此得(0!)"⑴"0(mod2P1)o

5、設(shè)p是大于5的質(zhì)數(shù)，證明：p4=l(mod240)o(提示：可由歐拉定理證明)

證明：因為240=23X3X5,所以只需證：p4=l(mod8),p4=l(mod3),p4=l(mod5)BP

可。事實上，由(8)=4,(3)=2,(5)=4以及歐拉定理立得結(jié)論。

初等數(shù)論練習(xí)題三

一、單項選擇題

1、若n>l,(〃)=AT是n為質(zhì)數(shù)的(C)條件。

A.必要但非充分條件B.充分但非必要條件C.充要條件D.既非充分又非必要條件

2、設(shè)n是正整數(shù)，以下各組a,b使匕為既約分?jǐn)?shù)的一組數(shù)是(D)。

a

A.a=n+l,b=2n-lB.a=2n-l,b=5n+2C.a=n+1,b=3n+1D.a=3n+l,b=5n+2

3、使方程6x+5y=C無非負(fù)整數(shù)解的最大整數(shù)C是(A)。

A.19B.24C.25D.30

4、不是同余方程28x三21(mod35)的解為(D)。

A.x=2(mod35)B.x=7(mod35)C.x=17(mod35)D.x=29(mod35)

5、設(shè)a是整數(shù)，(l)a=0(mod9)(2)a三2010(mod9)

(3)a的十進位表示的各位數(shù)字之和可被9整除

(4)劃去a的十進位表示中所有的數(shù)字9,所得的新數(shù)被9整除

以上各條件中，成為91a的充要條件的共有(C)o

A.1個B.2個C.3個D.4個

二、填空題

1,。(2010)=4896:<p(2010)=528o

2、數(shù)C需的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)7的指數(shù)是上。

3、每個數(shù)都有一個最小質(zhì)因數(shù)。所有不大于10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是￡2。

4、同余方程24x三6(mod34)的解是xi三13(mod34)X2三30(mod34)。

5、整數(shù)n>l,且(n-l)!+l三0(modn),則n為素數(shù)。

6,38被11除所得余數(shù)是工。

入Q。

三、計算題

1、判定(i)2義/3*10(mod5)是否有三個解；

(ii)/2x4/30(mod5)是否有六個解？

解：(i)2/*3x10(mod5)等價于f3/4x30(mod5),又fx=

{x3x24x3)(x3x5)+(6/12x15),其中r(x)=I2x15的系數(shù)

不都是5的倍數(shù)，故原方程沒有三個解。

(ii)因為這是對模5的同余方程，故原方程不可能有六個解。

2、設(shè)〃是正整數(shù)，求C曉,C黑，…,的最大公約數(shù)。

解：設(shè)…，噫T)=d,由C/+G.+…+C黑=22M知婷，

設(shè)2*)且2”,即,

則由2*T|U“及2皿|<3鼠=乎03一，2=3,5,,2〃1得d=2…。

3、已知a=18,m=77,求使a*1(modm)成立的最小自然數(shù)x。

解:因為(18,77)=1,所以有歐拉定理知18(⑺三l(mod77)。

又由于(77)=60,所以x|60,而60的所有正因數(shù)為1,2,3,4,5,6,10,12,15,20,30,60。

于是x應(yīng)為其中使18*1(mod77)成立的最小數(shù)，經(jīng)計算知：x=30o

四、證明題

1、若質(zhì)數(shù)p25,且2p+l是質(zhì)數(shù)，證明：4p+l必是合數(shù)。

證明：因為質(zhì)數(shù)p25,所以(3,p)=1,可設(shè)p=3k+l或p=3k+2。

當(dāng)p=3k+l時，2p+l=6k+3是合數(shù)，與題設(shè)矛盾，從而p=3k+2,

此時2p+l是形如6k+5的質(zhì)數(shù)，而4p+l=12k+9=3(4k+3)是合數(shù)。

注：也可設(shè)p=6k+r,r=0,1,2,3,4,5。再分類討論。

2、設(shè)p、q是兩個大于3的質(zhì)數(shù)，證明：p2=q2(mod24)(.

證明：因為24=3X8,(3,8)=1,所以只需證明：

p2=q2(mod3)p?三q2(mod8)同時成立。

事實上，由于(p,3)=1,(q,3)=1,所以p2三：l(mod3),q2=l(mod3),

于是p』q'mod3),由于p,q都是奇數(shù)，所以p?三l(mod8),q2=l(mod8),

于是p2三q'mod8)。故p2三q2(mod24)。

3、若x,ySR,,

(1)證明：[xy]2[x][y]；

(2)試討論{xy}與{x}{y}的大小關(guān)系。

注：我們知道，[xy]2[x]+[h，{x"}W{x}+{y}。此題把加法換成乘法又如何呢？

證明：(1)設(shè)x=[x]+。，0Wy=[y]+￡,0W￡<1。于是

xy=[x][y]+￡[x]+a[y]+aB

所以[xy]=[x][y]+[￡[x]+a[y]+a￡]2[x][y]。

(2){xy}與{x}{y}之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。

當(dāng)x=y=，時，{xy}={x}{y}=7;

24

當(dāng)x=m，y=L時，{xy}=g,{x}{y}=L,此時{xy}>{x}{y}；

2244

當(dāng)x=-《，y=-(時，{xy}=5，{x}{y}=^，此時{xy}V{x}{y}。

2363

4,證明：存在一個有理數(shù)二，其中d<100,能使伙￡卜法衛(wèi)]

ddL100

對于k=l,2,….，99均成立。

證明：由(73,100)=1以及裴蜀恒等式可知：存在整數(shù)c,d,使得

73d-100c=l

”k73,kc%(73d-100c)k,,.,-

從而——k~—=----------=----,由k<10An0可知:

100d

設(shè)則以<n+l=2以d,于是

故伙射n平色

初等數(shù)論練習(xí)題四

一、單項選擇題

1、若F0=22"+l是合數(shù)，則最小的門是(D)。

A.2B.3C.4D.5

2、記號b'”la表示b.Ia,但b“"/a.以下各式中錯誤的一個是(B)。

A.218II20!B.105II50!C.Il9II100!D.13161|200!

3、對于任意整數(shù)n,最大公因數(shù)(2n+l,6nT)的所有可能值是(A)。

A.1B.4C.1或2D.1,2或4

4、設(shè)a是整數(shù)，下面同余式有可能成立的是(C)0

A.a'=2(mod4)B.a'=5(mod7)C.a-=5(mod11)D.a2=6(mod13)

5、如果a三b(modm),c是任意整數(shù)，則下列錯誤的是(A)

A.ac=bc(modme)B.m|a-bC.(a,m)=(b,m)D.a=b+mt,tGZ

二、填空題

1,d(10010)=32,6(10010)=28800

2、對于任意一個自然數(shù)n,為使自N起的n個相繼自然數(shù)都是合數(shù)，可取N=(n+1)!

3、為使3n-l與5n+7的最大公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=26k+9,k￡Z。

4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來構(gòu)成模12的一個簡化系，則這組數(shù)是

{5,25,35,55}

5、同余方程26x+l三33(mod74)的解是Xi三24(mod74)x2三61(mod74)。

6、不定方程5x+9y=86的正整數(shù)解是x=l,y=9或x=10,y=4。

三、計算題

1、設(shè)〃的十進制表示是13xy45z,若792〃，求x,y,z。

解：因為792=8911,故792〃8A,9〃及

我們有8〃8蒞z=6,以及

9〃913xy45z=19xy9xy1,(1)

11/7llz54yx31=3yx113yxo(2)

由于0x,y9,所以由式(1)與式(2)分別得出

xy1=9或18,

3yx=0或11。

x+y+1=a

這樣得到四個方程組：二,

3-y+x-b

其中a取值9或18,6取值0或11。在0x,y9的條件下解這四個方程組，

得至!J：x=8,y=0,z=6o

2、求3他的末二位數(shù)。

解：(3,100)=1,：.3^lW=l(mod100),而4)(100)=<1)(22?52)=40,

/.3皿三l(mod100)/.3406=(340)10?36^(32)2?32=-19X9=-171=29(mod100)

二末二位數(shù)為29。

3、求(2149犯+40戶被73除所得余數(shù)。

解：(214928+40)非三(32“+40)35三［(32*32)”+40『5=(1024w+40)35=(211+40)35三⑵。

X24+40)35三(2%40)35=7235三T三72(mod73)

四、證明題

1、設(shè)a”a2,,a*,是模勿的完全剩余系，證明：

(1)當(dāng)m為奇數(shù)時，S|+a2++am=0(modm)；

(2)當(dāng)m為偶數(shù)時，a,+a++a?,=—(modm)

22o

證明：因為｛1,2,,血與｛4,,為｝都是模勿的完全剩余系，所以

"I三立"1=m(m+1)

(modni)。

/=!/=12

(1)當(dāng)m為奇數(shù)時，由竺士leZ即得：,nm(m+D,故:三0(mod向。

222

(2)當(dāng)m為偶數(shù)時，由(m,m+1)=1即得：Va.="?("+D=—(mod加)。

占22

(p(/?1)

2、證明：若m>2,a?a2,,是模力的任一簡化剩余系，則ga產(chǎn)0(mod/n).

/=1

證明：若a,a2,,a?是模力的一個簡化剩余系，則/-a,m-a2,,/-a?也是模力的

(p(m)(p(ni)(p(tn')

一個簡化剩余系，于是：.三Z(加一4)(m°d機).從而：2⑼.又

i=li=ii=l

由于m>2,(力)是偶數(shù)。故：^<2,.=/??—....s0(modm).

i=i2

3、設(shè)/>0是偶數(shù)，｛4,,蜃｝與｛4，b,,,口都是模勿的完全剩余系，證明：｛&bx,

a2bi,,a?ZU不是模力的完全剩余系。

證明：因為｛1,2,,就與｛團，a一&,｝都是模加的完全剩余系，所以

￡￡,=幽里2三？麗川曲。(1)

金占22

同理產(chǎn)%(mod加)。(2)

i=l2

如果｛&b\,a2b,,,a,。,｝是模勿的完全剩余系，那么也有

mm..、

￡(修+2)三一(modZZ7)o

/=i2

聯(lián)合上式與式⑴和式(2),得到0m2+2m2(mod而，

222

這是不可能的，所以1匕,a2th,,am6J不能是模勿的完全剩余系。

4、證明：(1)2730|xI3-x；(2)24|x(x+2)(25x-l)；

93p

(3)504|x-x；(4)設(shè)質(zhì)數(shù)p>3,證明：6pIx-xo

證明：(1)因為2730=2X3X5X7X13,2,3,5,7,13兩兩互質(zhì)，所以：

由xI3-x=x(x12-l)=0(mod2)知:2|x1:-x；13|x13-x；

由xI3-x=x(x12-l)=x(x2-l)(x2+l)(x8+x4+l)=0(mod3)知:3Ix13-x；

由x"-x=x(x12-l)=x(x4-l)(x8+x4+l)=0(mod5)知：5|xl3-x；

I3l26613

由x~x=x(x-l)=x(x-l)(x+l)=0(mod7)知：7|x-xo

故有2730|x13-xo

同理可證(2)、(3)、(4)o

初等數(shù)論練習(xí)題五

一、單項選擇題

1、設(shè)x、y分別通過模m、n的完全剩余系，若(C)通過模mn的完全剩余系。

A.m、n都是質(zhì)數(shù)，貝UmynxB.mrn,則mynx

C.(m,n)=1,貝!JmynxD.(m,n)=1,貝!Jmxny

2、1X3X5X…X2003X2005X2007X2009X2011標(biāo)準(zhǔn)分解式中11的基指數(shù)是（A）。

A.100B.101C.99D.102

3、n為正整數(shù)，若2"T為質(zhì)數(shù)，則n是（A）。

A.質(zhì)數(shù)B.合數(shù)C.3D.2k（k為正整數(shù)）

4、從100到500的自然數(shù)中，能被11整除的數(shù)的個數(shù)是（B）o

A.33B.34C.35D.36

5、模100的最小非負(fù)簡化剩余系中元素的個數(shù)是（C）。

A.100B.10C.40D.4

二、填空題

1、同余方程a/b三0（modzz?）有解的充分必要條件是（a,m）Ib。

2、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)夕與q是不相同的兩個奇質(zhì)數(shù),

p-1q-\

（9=（-i尸d）

p（i

3、2012刈2被3除所得的余數(shù)為」

4、設(shè)n是大于2的整數(shù)，則（-1）。?=1。

5、單位圓上的有理點的坐標(biāo)是（士一^,±04）或（±R,±—）,其中a與」是不全為

a2+b2a2+b2a2+b2a2+b2

零的整數(shù)。

6、若3258Xa恰好是一個正整數(shù)的平方，則a的最小值為避。

7、已知2011是一素數(shù)，則。

UOllJ----

三、計算題

1、求32.><72W9X13刈。的個位數(shù)字。

解：32008X72009X132010=__22008+2009+2010

三一3融7三-3X（32）30,3=3（mod10）0

2、求滿足（mn）=5）+（〃）的互質(zhì)的正整數(shù)m和n的值。

解：由（m,n）=1知，（mn）=（加）（〃）。于是有：（加）+（〃）=（加）（〃）

設(shè)(加)=a,(〃)=b,即有：a+b=ab0顯然a|b,且b|a,因此a=b。

于是由2a=a?得a=2,即(9)=(A)=2。故m=3,n=4或m=4,n=3。

3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100

斤，問各買幾斤

解：設(shè)買甲物X斤，乙物y斤，丙物Z斤，則

5x3y-z=100,

3

xyz-100o

消去z,得到7x4y=100o⑴

顯然x=0,y=25是方程(1)的解，因此，方程(1)的一般解是

x=4t

fZ

。=25-7f'

因為x>0,y>0,所以O(shè)Vt3o

即亡可以取值t}=1,t2=2,t3=3。相應(yīng)的x,y,z的值是

(x,y,z)=(4,18,78),(8,11,81),(12,4,84)o

四、證明題

1、已知2011是質(zhì)數(shù)，則有2011|里二2。

2010個

證明：99-9=1020H-l=0(mod2011)。

2010個

2、設(shè)p是4n+l型的質(zhì)數(shù)，證明若a是p的平方剩余，則p-a也是p的平方剩余。

證明：因為質(zhì)數(shù)p=4n+l,a是p的平方剩余，所以

即：p-a也是p的平方剩余。

3、已知p,q是兩個不同的質(zhì)數(shù)，且a'"'三1(modq),aql=l(modp),

證明:aw=a(modpq)。

證明：由p,q是兩個不同的質(zhì)數(shù)知(p,q)=lo于是由Fermat定理a"=a(modp),

qp

又由題設(shè)ag三1(modp)得到:a'三(a尸三6皿尸三ama(modp)0

同理可證:apq=a(modq)。故：apq=a(modpq)。

4、證明：若m,n都是正整數(shù)，則(mn)=(m,n)([加，五I)。

證明：易知mn與[加，加有完全相同的質(zhì)因數(shù)，設(shè)它們?yōu)榭?IWiWQ,則

又mn=(m,n)[m,n\

故。(mn)={m,n)[m,n\(\--)(1———)■??(1———)=(m,n)(p([m,n\)。

PiPiPk

類似的題：設(shè)皿初儂,nu與m由相同的質(zhì)因數(shù),證明：(m)=nh(加。

初等數(shù)論練習(xí)題六

一、填空題

1、為了驗明2011是質(zhì)數(shù)，只需逐個驗算質(zhì)數(shù)2,3,5,…p都不能整除2011,此時，質(zhì)

數(shù)p至少是3—。

2、最大公因數(shù)(4n+3,5n+2)的可能值是」

3、設(shè)3"|40!,而3ar40!,即3"II40!,則a=18。

4、形如3n+l的自然數(shù)中，構(gòu)成模8的一個完全系的最小那些數(shù)是｛1,4,7,10,13,16,19,

22｝。

5、不定方程(+/=2；2除，(x,y)=l,x,y,z>0的整數(shù)解是且僅是x=2ab,y=

a，占,z=a，k其中十>>>0,(a,8)=1,a與6有不同的奇偶性。

6、21x=9(mod43)的解是x三25(mod43是

7、73=-lo

V199；

二'計算題

1、將意寫成三個既約分?jǐn)?shù)之和，它們的分母分別是3,5和7。

解:設(shè)監(jiān)=>]+"，即35x21y15z=17,因(35,21)=7,(7,15)=1,117,

故有解。

分別解5x3y=tIt15z=17

得x=t3u,y-2t5u,〃Z,

t=1115r,z=47r,rZ,

消去t得x=1115P3u,

y=2230K5〃，

z=47r,u,vZo

174-83

令u=0,p=T得到：x=4,y=-8,z=3o即:--=—I----1—

105357

2、若3是質(zhì)數(shù)0的平方剩余，問0是什么形式的質(zhì)數(shù)?

P-1

解：；由二次互反律(-1)2國

p=l(mod4)

注意到夕>3,,只能為4三±1(mod3)且P_

p=-l(mod4)

p=l(mod3)p=-l(mod3)

】只能下列情況■

p=l(mod4)p=-l(mod4)

...p=l(mod12)或p三-l(mod12)o

3、判斷不定方程x423產(chǎn)17是否有解？

解：只要判斷f三17(mod23)是否有解即可。

17三1(mod4)

，f三17(mod23)無解，即原方程無解。

三、論證題

1、試證對任何實數(shù)x,恒有(x)+(x+L)=(2x)

2

證明：設(shè)x=[x]+0W

①當(dāng)時，[x+l]=[xL[2x]=2[x]...等式成立

22

②當(dāng)J_Wa<1時,[x+-]=[x]+l,[2x]=2[x]+l.,.等式成立

22

故對任何實數(shù)X,恒有[x]+[x+L]=[2x]o

2

2、證明：(1)當(dāng)n為奇數(shù)時，3|(2.+1)；

n

(2)當(dāng)n為偶數(shù)時，3f(2+l)o

證明：由2“1三(-1)n+l(mod3)立得結(jié)論。

3、證明：(1)當(dāng)31n(n為正整數(shù))時，7|(2=1)；

(2)無論n為任何正整數(shù)，7\(2n+l)o

證明：(1)設(shè)n=3m,則2n-l=8m-l三0(mod7),即：7|(2匚1)；

(2)由于2舐=1(mod7)得

Z.+l三2(mod7),23m+1+1=3(mod7),23m+2+1=5(mod7)。

n

故無論n為任何正整數(shù)，7f(2+l)o

4、設(shè)m>0,n>0,且m為奇數(shù)，證明：2，1)=1。

證明一：由m為奇數(shù)可知：2n+lI2mn+l,又有2T|2*1,

mnmn

于是存在整數(shù)x,y使得：(2"+1)x=2+l((2?-l)y=2-lo

從而(2n+l)x-(2-l)y=2o這表明：

(2-1,2"+1)|2

由于2-+1,2憶1均為奇數(shù)可知：2"+1)=10

證明二:設(shè)(2<1,2n+l)=d,則存在s,t￡Z,使得2m=sd+l,2n=td-lo由此得到:

2mn=(sd+l)\2ran=(td-l)m

于是2,?1=pd+\=qd-l,p,qWZ。所以：(<?-p)d=2。

從而2,就有d=l或2。由因為m為奇數(shù)，所以d=l。

即(2m-l,2n+l)=lo

注：我們已證過：記",=2"1,對于正整數(shù)a,b,有(必，成)=%,@。

顯然當(dāng)a#b,a,b為質(zhì)數(shù)時，(〃，必)=1。

初等數(shù)論練習(xí)題七

一、單項選擇題

1、設(shè)a和b是正整數(shù)，則(回2,回2)=(A)

ab

A.1B.aC.bD.(a,b)

2、176至545的正整數(shù)中，13的倍數(shù)的個數(shù)是(B)

A.27B.28C.29D.30

3,200!中末尾相繼的0的個數(shù)是(A)

A.49B.50C.51D.52

4、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡化剩余系的是(B)

A.2的倍數(shù)B.3的倍數(shù)C.4的倍數(shù)D.5的倍數(shù)

5、設(shè)n是正整數(shù)，下列選項為既約分?jǐn)?shù)的是(A)

.21〃+4卜n+1_2/1-16〃+1

A.------B.----C.-----D.----

14〃+32/7-15/1+23〃+1

二、填空題

1、314儂被163除的余數(shù)是」_。(歐拉定理)

2、同余方程3x三5(modl3)的解是x三5(modl3)。

3、(需工

4、[-n]=-4o

5、為使nT與3n的最大公因數(shù)達(dá)到最大的可能值，則整數(shù)n應(yīng)滿足條件n=3k+l,k@Z。

6、如果一個正整數(shù)具有21個正因數(shù)，問這個正整數(shù)最小是2"X3-'=576。

7、同余方程x3+x2-x-l=O(mod3)的解是x三1,2(mod3)。

-、IA-Ar-OT-

二'計舁題

1、求不定方程X2y3z=41的所有正整數(shù)解。

解：分別解x2y=t

t3z-41

得x-t2u

y-uuL,

t=413”

z=vVL,

消去t得x=413v2u

y-u

z-vu,vLa

由此得原方程的全部正整數(shù)解為

(x,y,z)=(413v2u,u,。，u>0,v>0,413v2u>0o

2、有一隊士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3

人。已知這隊士兵不超過170人，問這隊士兵有幾人？

解：設(shè)士兵有x人,由題意得*1(mod3),x2(mod5),x3(mod11)。

在孫子定理中，取0=3,例=5,mi=11,m=3511=165,

M=55,M,=33,M=15,

4=1,鹿=2,M=3,

則x1551(-2)332315358(mod165),

因此所求的整數(shù)矛=52+1651,/Zo

由于這隊士兵不超過170人，所以這隊士兵有58人。

3、判斷同余方程一三286(mod443)是否有解

解：286=2X143,433是質(zhì)數(shù)，(143,443)=1

奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號計算的勒讓德符號

...原方程有解。

四、證明題

1、設(shè)(a,加)=1,4是使a"1(mod勿)成立的最小正整數(shù)，則

(i)加(血；

(ii)對于任意的i,j,0i,Jda1,ij,有a'ta'(mod勿)。(1)

證明：(i)由Euler定理，4(加，因此，由帶余數(shù)除法，有

(加)=qd0r,ql,<7>0,0r<4。

因此，由上式及4的定義，利用歐拉定理得到

1/(⑼=/%+「三優(yōu)(mod面,

即整數(shù)r滿足a'1(mod/ii),0r<40

由4的定義可知必是r=0,即4(血。

(ii)若式(1)不成立，則存在了,j,0i,jdn1,ij,使a，a'(modni)o

不妨設(shè)i>Jo因為(a,m)=1,所以a'j0(modin),Q<ij<4°

這與4的定義矛盾，所以式(1)必成立。

2、證明：設(shè)a,b,c,勿是正整數(shù)，m>1,(b,ni)=1,并且

b"1(modni),bc1(modni)(1)

記d=(a,c),則If1(modni)o

證明：由裴蜀恒等式知，存在整數(shù)x,外使得axcy=d,顯然孫<0o

axdcreyd

若x>0,y<0,由式(1)知：1b=bb=b\b}b(modni)0

若x<0,y>0,由式(1)知：1bcy=bdbax=Z/(")'bd(mod血。

3、設(shè)o是素數(shù)，pb"1,曲，則下面的兩個結(jié)論中至少有一個成立：

(i)pb'1對于〃的某個因數(shù)d〈〃成立；

(ii)p1(modz?)o

若2/〃，p>2,則(ii)中的mod〃可以改為mod2n。

證明：記d=5,p1),由夕1,bp11(modp),及第2題有

bd1(modp)o

若d<〃，則結(jié)論(i)得證。

若d=〃，則和1,即01(modn),這就是結(jié)論(ii)。

若2f〃，0>2,則01(mod2)。由此及結(jié)論(ii),并利用同余的基本性質(zhì),

得到p1(mod2/7)o

初等數(shù)論練習(xí)題八

一、單項選擇題

1、設(shè)〃>1,則〃為素數(shù)是(〃1)!1向0(1〃)的((：)。

A.必要但非充分條件B.充分但非必要條件

C.充要條件D.既非充分又非必要條件

2、小于545的正整數(shù)中，15的倍數(shù)的個數(shù)是(C)

A.34B.35C.36D.37

3、500!的標(biāo)準(zhǔn)分解式中7的毒指數(shù)是(D)

A.79B.80C.81D.82

4、以下各組數(shù)中，成為模10的簡化剩余系的是(D)

3,—1B.1,-1,7,9C.5,7,11,13D.-1,1,-3,3

5、設(shè)n是正整數(shù)，下列選項為既約分?jǐn)?shù)的是(A)

Ac2n—1cn+1

A.-3-n-+--1cB.-n--+-1C.-----D.----

5n+22n-l5n+23n+l

二、填空題

1、。(120)=360。

2、7355的個位數(shù)字是3。

3、同余方程3x三5(modl4)的解是x三1l(modl4)。

5^E-V2]=-2o

6、如果一個正整數(shù)具有6個正因數(shù)，問這個正整數(shù)最小是四

7、同余方程x3+x2-x-l=0(mod5)的解是x三土l(mod5)。

三、計算題

1、已知563是素數(shù)，判定方程x2429(mod563)是否有解。

解：把黑看成"bi符號，我們有

)

故方程x2429(mod563)有解。

2、求出模23的所有的二次剩余和二次非剩余。

解：模23的所有的二次剩余為

xl,2,3,4,6,8,9,12,13,16,18(mod23)；

模23的所有的二次非剩余為

x5,7,10,11,14,15,17,19,20,21,22(mod23)。

3、試求出所有正整數(shù)〃，使得1"+2"+3"+4"能被5整除。

解：若n為奇數(shù)，則l〃+2〃+3"+4T+2"+(-2)"+(-1)"0(mod5)；

若n=2m,mez,則1"+2"+3"+4"產(chǎn)+2”+(-2)?"+(-1)為

2+2X2加=2+2X40=2+2X(-1)"(mod5)；

當(dāng)m為奇數(shù)時,r+2"+3〃+4"0(mod5)；

當(dāng)m為偶數(shù)時，1"+2"+3"+4"4(mod5)。

故當(dāng)4Jn時,5|l"+2n+3n+4no

四、證明題

1、證明：若質(zhì)數(shù)p>2,則2憶1的質(zhì)因數(shù)一定是2pk+l形。

證明：設(shè)g是2。-1的質(zhì)因數(shù)，由于2丁1為奇數(shù)，q豐2,(2,g)=1。

由條件即2。三1(modq)。

r

設(shè)h是使得2=l(modq)成立最小正整數(shù)，若K/i<p,則有h\po這與p

為質(zhì)數(shù)矛盾。從而h=p,于是又/I為偶數(shù)，2|91,

2p\q-l,q-l=2pk,即于2%+1AWZ。

n)

2、設(shè)(m,n)=1,證明：ni+n=1(modmn)o

證明：因為(m,n)=1,所以由歐拉定理知：n(m>=\(modm),m<n)=1(modn)

(，1)(m)

于是ni+n=1(modm),W+n=1(modn)o

(，!1)

又因為(m,n)=1,所以〃產(chǎn)力7=1(modmn)Q

注：此題也可這樣表述：若兩個正整數(shù)a,b互質(zhì)，則存在正整數(shù)m,n,使得

,n

a+b"=1(modab)o

p

npih

3、設(shè)(a,b)=1,a+bWO,p為一個奇質(zhì)數(shù)，證明：(Q+Z?,-------)=1或〃。

a+b

說明：事實上，設(shè)m+o,且土且)=[,只需證明：d|P即可。

a+b

證明：由a+b三0(moda+b),即a三-b(moda+b),知a八三(-b)"(moda+b)o

其中0WAW/7-1。又=ap-'-a"-2b+ab1-2+b1"'=b"-'+產(chǎn)+???+b'"'=pb'-'(moda+b)。

a+b

令(a+8")=d,則dIpt!"1o又(a,b)=1,d\(a+b)知(d,b)=lo

a+b

(否則設(shè)(d,b)>1,立即得到I|a和d'|b,這與(a,b)=1矛盾。)

于是Qd,ZT‘)=lo故"Ip,即d=1或p。

初等數(shù)論練習(xí)題九

一、單項選擇題

1、以下Legendre符號等于T的30被T是（D）

4

A.B.D.

2、100至500的正整數(shù)中，能被17整除的個數(shù)是（B)

A.23B.24C.25D.26

3、設(shè)3al500!,但3a+」500!,則a=(C)

A.245B.246C.247D.248

4、以下數(shù)組中，成為模7的完全剩余系的是（C)

A.-14,-4,0,5,15,18,19B.7,10,14,19,25,32,40

C.-4,-2,8,13,32,35,135D.—3,3,~4,4,—5,5,0

5、設(shè)〃是正整數(shù)，則以下各式中一定成立的是(B)

A.(z?+l,3〃+1)=1B.(2/7-1,2〃+1)=1

C.(2/7,zz+l)=1