初等数论练习题答案

初等数论练习题一

一、填空题

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

2、设a,n是大于1的整数，若an-l是质数，则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、分母是正整数m的既约真分数的个数为一包。

7、18-被*2除的余数是256。

9、若p是素数，则同余方程x-l(modo)的解数为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的最小非负余数。

解：易知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是质数，(a,p)=l,证明：

(1)当a为奇数时，ap-1+(p-l)a=0(modp)；

(2)当a为偶数时，a「T-(p-l)a三0(modp)。

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

n+2

2、设a为正奇数，n为正整数，试证a2"=i(m0d2)0.........(1)

证明设a=2m1,当〃二1B寸，有

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

2k

设原式对于〃=A成立，则有a1(mod2*i)/*=i或…，

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

其中q是某个整数。这说明式⑴当〃=41也成立。

由归纳法知原式对所有正整数〃成立。

3、设p是一个素数，且lWkWp-1。证明：C；,_,(-1)k(modp).

证明：设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、设p是不等于3和7的奇质数，证明：p6=l(mod84)o

说明：因为84=4义3义7,所以，只需证明：

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

证明：因为84=4X3X7及p是不等于3和7的奇质数，所以

(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)。

注：设p是不等于3和7的奇质数，证明：p6^l(mod168)o(见赵继源p86)

初等数论练习题二

一、填空题

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

2、2010!的标准分解式中，质数11的次数是199..

3、费尔马(Fermat)数是指Fn=22"+1,这种数中最小的合数Fn中的n=5o

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

5、分母不大于m的既约真分数的个数为(2)+(3)+...+(力)。

6、设7](80勺),则最小的正整数n=逸一

7、使41x+15y=C无非负整数解的最大正整数C=559.

9、若夕是质数，np1,则同余方程x"1(modp)的解数为此

二、计算题

1、试求200220032004被19除所得的余数。

解：由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)成立的最小自然数x。

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

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

于是x应为其中使5*1(mod12)成立的最小数，经计算知：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),则〃是素数。

证明：假设〃是合数，即〃=nm，1<6<n,由题设易知(A1)!1(modm)，得

01(mod“)，矛盾。故〃是素数。

3、证明：设外表示全部由1组成的s位十进制数，若总是素数，则s也是一个素数。

证明：假设S是合数，即5=2卜ka,b<s0则

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

亿=111=—--=---=—---M,具।HM>1是正整数。

由夕">1也是正整数知外是合数，这与题设矛盾。故s也是一个素数。

4、证明：若2P1是奇素数，贝U3)2⑴"0(mod2pl)o

证明:由威尔逊定理知1(2p)!=p!(p1)(2。)⑴〃(p!)2(mod2P1),

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

5、设p是大于5的质数，证明：p4=l(mod240)o(提示：可由欧拉定理证明)

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

可。事实上，由(8)=4,(3)=2,(5)=4以及欧拉定理立得结论。

初等数论练习题三

一、单项选择题

1、若n>l,(〃)=AT是n为质数的(C)条件。

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

2、设n是正整数，以下各组a,b使匕为既约分数的一组数是(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无非负整数解的最大整数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、设a是整数，(l)a=0(mod9)(2)a三2010(mod9)

(3)a的十进位表示的各位数字之和可被9整除

(4)划去a的十进位表示中所有的数字9,所得的新数被9整除

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

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

二、填空题

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

2、数C需的标准分解式中，质因数7的指数是上。

3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是£2。

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

5、整数n>l,且(n-l)!+l三0(modn),则n为素数。

6,38被11除所得余数是工。

入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的系数

不都是5的倍数，故原方程没有三个解。

(ii)因为这是对模5的同余方程，故原方程不可能有六个解。

2、设〃是正整数，求C晓,C黑，…,的最大公约数。

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

设2*)且2”,即,

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

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

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

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

于是x应为其中使18*1(mod77)成立的最小数，经计算知：x=30o

四、证明题

1、若质数p25,且2p+l是质数，证明：4p+l必是合数。

证明：因为质数p25,所以(3,p)=1,可设p=3k+l或p=3k+2。

当p=3k+l时，2p+l=6k+3是合数，与题设矛盾，从而p=3k+2,

此时2p+l是形如6k+5的质数，而4p+l=12k+9=3(4k+3)是合数。

注：也可设p=6k+r,r=0,1,2,3,4,5。再分类讨论。

2、设p、q是两个大于3的质数，证明：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都是奇数，所以p?三l(mod8),q2=l(mod8),

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

3、若x,ySR,,

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

(2)试讨论{xy}与{x}{y}的大小关系。

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

证明：(1)设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}之间等于、大于、小于三种关系都有可能出现。

当x=y=，时，{xy}={x}{y}=7;

24

当x=m，y=L时，{xy}=g,{x}{y}=L,此时{xy}>{x}{y}；

2244

当x=-《，y=-(时，{xy}=5，{x}{y}=^，此时{xy}V{x}{y}。

2363

4,证明：存在一个有理数二，其中d<100,能使伙£卜法卫]

ddL100

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

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

73d-100c=l

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

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

100d

设则以<n+l=2以d,于是

故伙射n平色

初等数论练习题四

一、单项选择题

1、若F0=22"+l是合数，则最小的门是(D)。

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

2、记号b'”la表示b.Ia,但b“"/a.以下各式中错误的一个是(B)。

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

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

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

4、设a是整数，下面同余式有可能成立的是(C)0

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

5、如果a三b(modm),c是任意整数，则下列错误的是(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、对于任意一个自然数n,为使自N起的n个相继自然数都是合数，可取N=(n+1)!

3、为使3n-l与5n+7的最大公因数达到最大可能值，整数n应满足条件n=26k+9,k£Z。

4、在5的倍数中，选择尽可能小的正整数来构成模12的一个简化系，则这组数是

{5,25,35,55}

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

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

三、计算题

1、设〃的十进制表示是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他的末二位数。

解：(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)

二末二位数为29。

3、求(2149犯+40户被73除所得余数。

解：(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、设a”a2,,a*,是模勿的完全剩余系，证明：

(1)当m为奇数时，S|+a2++am=0(modm)；

(2)当m为偶数时，a,+a++a„,=—(modm)

22o

证明：因为｛1,2,,血与｛4,,为｝都是模勿的完全剩余系，所以

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

(modni)。

/=!/=12

(1)当m为奇数时，由竺士leZ即得：,nm(m+D,故:三0(mod向。

222

(2)当m为偶数时，由(m,m+1)=1即得：Va.="?("+D=—(mod加)。

占22

(p(/?1)

2、证明：若m>2,a„a2,,是模力的任一简化剩余系，则ga产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,(力)是偶数。故：^<2,.=/??—....s0(modm).

i=i2

3、设/>0是偶数，｛4,,蜃｝与｛4，b,,,口都是模勿的完全剩余系，证明：｛&bx,

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

证明：因为｛1,2,,就与｛团，a一&,｝都是模加的完全剩余系，所以

££,=幽里2三？丽川曲。(1)

金占22

同理产%(mod加)。(2)

i=l2

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

mm..、

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

/=i2

联合上式与式⑴和式(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)设质数p>3,证明：6pIx-xo

证明：(1)因为2730=2X3X5X7X13,2,3,5,7,13两两互质，所以：

由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

初等数论练习题五

一、单项选择题

1、设x、y分别通过模m、n的完全剩余系，若(C)通过模mn的完全剩余系。

A.m、n都是质数，贝UmynxB.mrn,则mynx

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

2、1X3X5X…X2003X2005X2007X2009X2011标准分解式中11的基指数是（A）。

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

3、n为正整数，若2"T为质数，则n是（A）。

A.质数B.合数C.3D.2k（k为正整数）

4、从100到500的自然数中，能被11整除的数的个数是（B）o

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

5、模100的最小非负简化剩余系中元素的个数是（C）。

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

二、填空题

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

2、高斯称反转定律是数论的酵母，反转定律是指设夕与q是不相同的两个奇质数,

p-1q-\

（9=（-i尸d）

p（i

3、2012刈2被3除所得的余数为」

4、设n是大于2的整数，则（-1）。®=1。

5、单位圆上的有理点的坐标是（士一^,±04）或（±R,±—）,其中a与」是不全为

a2+b2a2+b2a2+b2a2+b2

零的整数。

6、若3258Xa恰好是一个正整数的平方，则a的最小值为避。

7、已知2011是一素数，则。

UOllJ----

三、计算题

1、求32.><72W9X13刈。的个位数字。

解：32008X72009X132010=__22008+2009+2010

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

2、求满足（mn）=5）+（〃）的互质的正整数m和n的值。

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

设(加)=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元，现在用100元买这三样东西共100

斤，问各买几斤

解：设买甲物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,所以OVt3o

即亡可以取值t}=1,t2=2,t3=3。相应的x,y,z的值是

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

四、证明题

1、已知2011是质数，则有2011|里二2。

2010个

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

2010个

2、设p是4n+l型的质数，证明若a是p的平方剩余，则p-a也是p的平方剩余。

证明：因为质数p=4n+l,a是p的平方剩余，所以

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

3、已知p,q是两个不同的质数，且a'"'三1(modq),aql=l(modp),

证明:aw=a(modpq)。

证明：由p,q是两个不同的质数知(p,q)=lo于是由Fermat定理a"=a(modp),

qp

又由题设ag三1(modp)得到:a'三(a尸三6皿尸三ama(modp)0

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

4、证明：若m,n都是正整数，则(mn)=(m,n)([加，五I)。

证明：易知mn与[加，加有完全相同的质因数，设它们为口(IWiWQ,则

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

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

PiPiPk

类似的题：设皿初侬,nu与m由相同的质因数,证明：(m)=nh(加。

初等数论练习题六

一、填空题

1、为了验明2011是质数，只需逐个验算质数2,3,5,…p都不能整除2011,此时，质

数p至少是3—。

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

3、设3"|40!,而3ar40!,即3"II40!,则a=18。

4、形如3n+l的自然数中，构成模8的一个完全系的最小那些数是｛1,4,7,10,13,16,19,

22｝。

5、不定方程(+/=2；2除，(x,y)=l,x,y,z>0的整数解是且仅是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、将意写成三个既约分数之和，它们的分母分别是3,5和7。

解:设监=>]+"，即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是质数0的平方剩余，问0是什么形式的质数?

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产17是否有解？

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

17三1(mod4)

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

三、论证题

1、试证对任何实数x,恒有(x)+(x+L)=(2x)

2

证明：设x=[x]+0W

①当时，[x+l]=[xL[2x]=2[x]...等式成立

22

②当J_Wa<1时,[x+-]=[x]+l,[2x]=2[x]+l.,.等式成立

22

故对任何实数X,恒有[x]+[x+L]=[2x]o

2

2、证明：(1)当n为奇数时，3|(2.+1)；

n

(2)当n为偶数时，3f(2+l)o

证明：由2“1三(-1)n+l(mod3)立得结论。

3、证明：(1)当31n(n为正整数)时，7|(2=1)；

(2)无论n为任何正整数，7\(2n+l)o

证明：(1)设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为任何正整数，7f(2+l)o

4、设m>0,n>0,且m为奇数，证明：2，1)=1。

证明一：由m为奇数可知：2n+lI2mn+l,又有2T|2*1,

mnmn

于是存在整数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均为奇数可知：2"+1)=10

证明二:设(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为奇数，所以d=l。

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

注：我们已证过：记",=2"1,对于正整数a,b,有(必，成)=%,@。

显然当a#b,a,b为质数时，(〃，必)=1。

初等数论练习题七

一、单项选择题

1、设a和b是正整数，则(回2,回2)=(A)

ab

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

2、176至545的正整数中，13的倍数的个数是(B)

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

3,200!中末尾相继的0的个数是(A)

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

4、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是(B)

A.2的倍数B.3的倍数C.4的倍数D.5的倍数

5、设n是正整数，下列选项为既约分数的是(A)

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

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

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

二、填空题

1、314侬被163除的余数是」_。(欧拉定理)

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

3、(需工

4、[-n]=-4o

5、为使nT与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+l,k@Z。

6、如果一个正整数具有21个正因数，问这个正整数最小是2"X3-'=576。

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

-、IA-Ar-OT-

二'计舁题

1、求不定方程X2y3z=41的所有正整数解。

解：分别解x2y=t

t3z-41

得x-t2u

y-uuL,

t=413”

z=vVL,

消去t得x=413v2u

y-u

z-vu,vLa

由此得原方程的全部正整数解为

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

2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3

人。已知这队士兵不超过170人，问这队士兵有几人？

解：设士兵有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),

因此所求的整数矛=52+1651,/Zo

由于这队士兵不超过170人，所以这队士兵有58人。

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

解：286=2X143,433是质数，(143,443)=1

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

...原方程有解。

四、证明题

1、设(a,加)=1,4是使a"1(mod勿)成立的最小正整数，则

(i)加(血；

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

证明：(i)由Euler定理，4(加，因此，由带余数除法，有

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

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

1/(⑼=/%+「三优(mod面,

即整数r满足a'1(mod/ii),0r<40

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

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

不妨设i>Jo因为(a,m)=1,所以a'j0(modin),Q<ij<4°

这与4的定义矛盾，所以式(1)必成立。

2、证明：设a,b,c,勿是正整数，m>1,(b,ni)=1,并且

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

记d=(a,c),则If1(modni)o

证明：由裴蜀恒等式知，存在整数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、设o是素数，pb"1,曲，则下面的两个结论中至少有一个成立：

(i)pb'1对于〃的某个因数d〈〃成立；

(ii)p1(modz?)o

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

证明：记d=5,p1),由夕1,bp11(modp),及第2题有

bd1(modp)o

若d<〃，则结论(i)得证。

若d=〃，则和1,即01(modn),这就是结论(ii)。

若2f〃，0>2,则01(mod2)。由此及结论(ii),并利用同余的基本性质,

得到p1(mod2/7)o

初等数论练习题八

一、单项选择题

1、设〃>1,则〃为素数是(〃1)!1向0(1〃)的((：)。

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

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

2、小于545的正整数中，15的倍数的个数是(C)

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

3、500!的标准分解式中7的毒指数是(D)

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

4、以下各组数中，成为模10的简化剩余系的是(D)

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

5、设n是正整数，下列选项为既约分数的是(A)

Ac2n—1cn+1

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

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

二、填空题

1、。(120)=360。

2、7355的个位数字是3。

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

5^E-V2]=-2o

6、如果一个正整数具有6个正因数，问这个正整数最小是四

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

三、计算题

1、已知563是素数，判定方程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、试求出所有正整数〃，使得1"+2"+3"+4"能被5整除。

解：若n为奇数，则l〃+2〃+3"+4T+2"+(-2)"+(-1)"0(mod5)；

若n=2m,mez,则1"+2"+3"+4"产+2”+(-2)?"+(-1)为

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

当m为奇数时,r+2"+3〃+4"0(mod5)；

当m为偶数时，1"+2"+3"+4"4(mod5)。

故当4Jn时,5|l"+2n+3n+4no

四、证明题

1、证明：若质数p>2,则2忆1的质因数一定是2pk+l形。

证明：设g是2。-1的质因数，由于2丁1为奇数，q丰2,(2,g)=1。

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

r

设h是使得2=l(modq)成立最小正整数，若K/i<p,则有h\po这与p

为质数矛盾。从而h=p,于是又/I为偶数，2|91,

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

n)

2、设(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,所以〃产力7=1(modmn)Q

注：此题也可这样表述：若两个正整数a,b互质，则存在正整数m,n,使得

,n

a+b"=1(modab)o

p

npih

3、设(a,b)=1,a+bWO,p为一个奇质数，证明：(Q+Z?,-------)=1或〃。

a+b

说明：事实上，设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"-'+产+•••+b'"'=pb'-'(moda+b)。

a+b

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

a+b

(否则设(d,b)>1,立即得到I|a和d'|b,这与(a,b)=1矛盾。)

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

初等数论练习题九

一、单项选择题

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

4

A.B.D.

2、100至500的正整数中，能被17整除的个数是（B)

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

3、设3al500!,但3a+」500!,则a=(C)

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

4、以下数组中，成为模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、设〃是正整数，则以下各式中一定成立的是(B)

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

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