初等数论练习题答案

初等数论练习题

一、填空题

1、d(2420)=12;(2420)=880

2、设a,n是大于1的整数，若an-1是质数，则a--2.

3、模9的绝对最小完全剩余系是{-4,3-2,-1,0,123.4}.

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

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

6分母是正整数m的既约真分数的个数为(二。

8、—=-lo

1OR

7、18】。。被172除的余数是为。

9、若p是素数，则同余方程XPIl(modp)的解数为pzl

二、计算题

1、解同余方程：3x211x200(mod105)。

解：因105=357,

同余方程3x2llx200(mod3)的解为x1(mod3),

同余方程3x11x380(mod5)的解为x0,3(mod5),

同余方程3x2llx200(mod7)的解为x2,6(mod7),

故原同余方程有4解。

作同余方程组：xbi(mod3)fxb(mod5),xba(mod7),

其中bi=1,b2=0,3,b3=2,6,

由孙子定理得原同余方程的解为x13,55,58,100(mod105)。

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

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

3、求(127156+34)28除以ni的最小非负余数。

解:易知1271三50(mod111)0

由502三58(mod111),503三58X50三14(mod111),5(P三143三80(mod111)知

33

5028=(5Q9)3X50三80X50三80X50三68X50三70(mod111)

从而5056三16(mod111)。

故(127H6+34)28三Q6+34)28三5028三70(mod111)

三、证明题

1、已知p是质数,(a,p)=1,证明:

(1)当a为奇数时，ap-i+(p-l)a=o(modp);

2n

2、设a为正奇数，n为正整数，试证三l(mod2皿)。(1)

成立。

(2)当a为偶数时,aP-i-(p-l)a=0(modp)o

证明：由欧拉定理知aZ=1(modp)及(p-1)a=-1(modp)立得⑴和(2)

证明设a=2ml,当n=l时，有

设原式对于n二k成立，则有③2kigod2k+今：-q2

a=(2m1)=4m(m1)11(mod2),即原式成立。

*1

2k*22kJk*3

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

其中qZ,所以a=(1q2)=1q21(mod2),

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

k

3、设p是一个素数，且Kk<p-lo证明：Cpi(-1)(modp)o

证明：设A二Cp】(P%分斜分得：Pk!

k!•A=(p-1)(p-2)...(p-k)=(-1)(-2)•••(-k)(modp)

又(k!,p)=1,故A=Cpi(-1)k(modp)

4、设p是不等于3和7的奇质数,证明：p6=l(mod84)。

说明：因为84=4X3X7,所以，只需证明：

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

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

(P,4)=1,(p,3)=1,(p,7)=10

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

于是x应为其中使5x1(mod12)成立的最小数，经计算知：x=6。

三、证明题

1、试证13|(54m+46n+2000)(提示:可取模13进行计算性证明)

2m2n2m

证明：54m+46n+200025+64+2000(-1)+(-1)2n+200020020(mod13)o

2、证明Wilson定理的逆定理：若n>1,井且(n1)!1(modn),则n是素数。

证明：假设n是合数，即n=nm2,1<m<n,由题设易知(n1)!1(modn",得

01(modn",矛盾。故n是素数。

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

10s1(10a)b110a1

ps111——-一-———M,其中M>1是正整数。

,Q9Q

证明：假设s是合数，即s=ab,l<a,b<se贝U

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

4、证明：若2Pl是奇素数，则(p!)2⑴P0(mod2pl)o

证明：由威尔逊定理知1(2p)!=p!(p1)(2p)(1)P(p!)2(mod2p1),由此得(p!)2Q)P0(mod2p

Do

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

证明:因为240=23x3X5,所以只需证：p4=l(mod8),p4=l(mod3),p4=l(mod5：即可。事

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

初等数论练习题三

一、单项选择题

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

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

2、设n是正整数，以下各组a,b使b为既约分数的一组数是(D)o

a

A.a=n+l,b=2n-1B.a=2n-l,b=5n+2C.a=n+l,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)

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

(4)划去a的十进位表示中所有的数字9,所得的新数被9整除以上各条件中，成为9|a的充要条件

的共有(C)。

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

二、填空题

2、数C2。。的标准分解式中,质因数7的指数是_3。

3、每个数都有一个最小质因数,所有不大于10000的合数的最小质因数中,最大者是97

4、同余方程24x=6(mod34)的解是X]H13(mod34)X2^30(mod34)_o

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

&31。3被11除所得余数是_5_o

7、60=-1o

97——

三、计算题

1、判定(i)2X?X?3x10(mod5)是否有二个解；

(ii)x62x54x230(mod5)是否有六个解？

g?:(i)2x3x23x10(mod5)等价于x33x24x30(mod5),5.x5x=(x33x24x3)(x23x5)+

(6x212x15),其中r(x)=6x212x15的系数不都是5的倍数,故原方程没有三个解。

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

2、设n是正整数，求C；n,C;n,Cn】的最大公约数。

解：设2打2跖,Cfnl)d油C;nC3nC;:122nl知，

设2k|n且2k+”n，即2k+i||n,

则由2k+i||C；n及2klic2n罕C2J1,i=3,5,,2n1得d=2卜+

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

解：因为(18,77)=1，所以有欧拉定理知18®三l(mod77)e

又由于(77)=60,所以x|60,而60的所有正因数为123,4,5,6,10,12,15,20,30,60于是x应为其

中使18x1(mod77)成立的最小数，经计算知：x=3Co

四、证明题

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

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

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

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

1、c(2010)=4896.(2010)=528。

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

2、设p、q是两个大于3的质数,证明：p2=q2(mod24)。

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

p2=q2(mod3)p2=q2(mod8)同时成立。

事实上,由于(p,3)=1,(q,3)=1,所以p2=l(mod3),q2=l(mod3),于是p2=q2(mod3),

22

由于p,q都是奇数,所以p2三l(mod8),q2三l；mod8),于是p=q(mod8)t故

p2=q2(mod24)。

3、若x,y€R,

(1)证明：[xy]>[x][y];

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

注:我们知道，[xy]>[x]+[y],{x+y}<{x}+{y}。此题把加法换成乘法又如何呢？证明：(1)设x=[x]+a,0

<a<1,y=[y]+B,0<B<l0于是

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

所以[xy]=[x][y]+[B[x]+a[y]+aB]>[x][y]o

(2){xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。

11

当x=y=-时,{xy}={x}{y}=—;

24

3131

当x=3,y;■时,{xy}=-，仅}{y}:一，此时{xy}>{:《}{y};

2244

1111

当x=--,y=--时,{xy}=-，仅}{y}二一，此时{xy}v{x}{y}o

2363

4、证明：存在一个有理数一，其中d<100,能使[k£]=[k空]

dd1100j

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

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

73d-100c=l

从而空k-勺®-逆0=J__，由k<100可知：

100d100d100d

0v空k-kCv_L

设[k:]=n,贝U也vl7md，于是

4dd

73|kc1"n1.

kv<d=n+l,

100dd

［瞪］二』

初等数论练习题四

、单项选择题

1、若FFF-1是合数，则最小的n是(D)。

42B.3c.4D.5

2、记号baIIa表示ba|a,但b-ila.以下各式中错误的一个是(B)。

4218120!B.10456||50)C.1191100!D.13161200!

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

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

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

2222

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

5、如果a=b(modm),c是任意整数，则下列错误的是(A)

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

二、填空题

1、d(10010)=32(10010)=2880。

2、对于任意一个自然数n,为使自N起的n个相继自然数都是合数,可取N=(n+1)!

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

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

三、计算题

1、设n的十进制表示是13xy45z,若792n,求x,y,zo解:因为792=8911,故792n8n,9n及lln。

7、54=-1。

RQ

我们有8n845zz=6,以及

{5,25,35,55}

5同余方程26x+l=33(mod74)的解是X)三24(mod74)x青61(mod74).

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

9n913xy45z=19xy9xy1,Q)

lln11z54yx31=3yxll3yxe(2)

xy1=9或1

3yx二或1

A-i

xy1a

这样得到四个方程组：3yxb

由于0x,y9,所以由式⑴与式⑵分别得出

其中a取值9或18,b取值0或11。在0x,y9的条件下解这四个方程组，

得至P：x=8,y=0,z=6O

2、求34。6的末二位数。

解：—(3,100)=1,二3。°°)三1(mod100),而©(100)=©(22•52)=40,

・・・340三i(mod100)二3406=04。)10.36三02)2•32三-19x9三-171三29(mod100)•••

末二位数为29。

3、求(214928+40)35被73除所得余数。

解*214928+40)35三(3228+40)35三［(32X32)"。甲H(102414+40)35H(214+40)35三(2X24+40)35

三(25+40产三7235三-1三72(mod73)

四、证明题

1、设ai,a2,,am是模m的完全剩余系,证明：

(1)当m为奇数时，ai+a2++am=0(modm;

⑵当m为偶数时,ai+a2++am=—(modm。

2

a.(mod—

i1r

m

m(m

⑴当m为奇数时，Z即得：1),故ai

证明：因为｛12,m与｛ai,a-am｝都是模m的完全剩余系，所以

⑵当m为偶数时，由(m,m+l=1即得：a,m(mod—

ii22

(m)

2、证明：若m>2,ai,a2,,a(m)是模m的任一简化剩余系，则O(modm).

il

证明：若a1,a2,,am是模m的一个简化剩余系，则m-a*m-a>,,m-a:m也是模m的

(ra)(m)(m)

一个简化剩余系，于是：a(ma.)(modm)从而：2a.m(m)(modm).

由于m>2,(n)是偶数。故：3⑺)O(modm).

m------

itifil

3、设m>0是偶数，｛a1,a2,,a/与｛b,b,,bm｝都是模m的完全剩余系，证明：gbi,

a2b2,,ambn｝不是模m的完全剩余系。

证明：因为｛12,n｝与｛五a-ad都是模m的完全剩余系,所以

mmm(m1)m,0)

aii(modm。

同理：22

bi

iib?,,ambn)是模m的完全剩余系，那么也有

•hnF=Rr-L.

m

(a.bi)(modm0

联合上式与式⑴和式⑵，得到0'

77｛Sm,

这是不可能的，所以｛aibl,azb2〃――廿人工”人,

2

4、证明:⑴2730Ix】3-x;「、、.

.......93⑷设质数P>3,证明:6pI「、，

证明：⑴因为2730=2X3x5X7X13,2,3,5,7,13两两互质，所以:由x^.x=x(x0I)=0(mod

2)知：2Ix13-x;13Ix13-x;

由x13-x=x(x12-1)=x(x2-l)(x2+l)(x8+x4+l)=0(mod3)知：3Ix13-x;

由x13-x=x(x12-1)=x(x4-l)(x8+x4+l)=0(mod5)知：5Ix13-x;

13126613

由x-x=x(x-1)=x(x-l)(x+l)=0(mod7)知:7Ix-xc

故有2730Ixi3-x。

同理可证(2)、(3)、(4)

初等数论练习题五

、单项选择题

L设x、y分别通过模mn的完全剩余系,若(C)通过模mn的完全剩余系

A.m、n都是质数，贝UmynxB.m工n,贝Umynx

C.(mn)=1,贝UmynxD.(m,n)=1,贝Umxny2、1X3X5X-X2003X2005X

2007X2009X2011标准分解式中11的幕指数是(A)

A.100B.1O1C.99D.102

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

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

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

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

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

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

二、填空题

1、同余方程ax+b=0（moch）有解的充分必要条件是（a,m）lb。

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

plql

①（1心

pq

3、2012282被3除所得的余数为_1_。

4、设n是大于2的整数，则（-1）⑺=_1一

2222

5、单位圆上的有理点的坐标是（一?或（手2,.?ab.）,其中奉与b是不全为

ab'ab,abab

零的整数。

&若3258xa恰好是一个正整数的平方，则a的最小值为362o

72

7、已知2011是一素数，则——=-1o

2011

三、计算题

解：32。。8X72009X13201。三32008必-3）由X3201。=_3

1、求32008x72009X13201。的个位数字。

60272、3013

=-3=-3x(3)=3(mod10)

2、求满足(mn)=(m)+(n)的互质的正整数m和n的值

解：由(知，(于是有：(

mn)=1mn)=(m(n)om+(n)=(m(n)

设(即有：显然且因此

n)=a,(n)=b,a+b=abbaIb,bIa,a=bo

于是由2得，即(故或

2a=aa=2m)=(n)=2Om=3,n=4m=4,n=3o

3、甲物每斤5元，乙物每斤3元,丙物每三斤1元，现在用100元买这三样东西共100斤,问各买几

斤

解：设买甲物X斤，乙物y斤，丙物z斤，则

1

5X3y=100,

3

xyz=100。

消去乙彳导至I」7x4y=100oii)

显然x=0,y=25是方程⑴的解，因此，方程⑴的一般解是

x4t

因为x>0,y>0,所以0vt3。

即t可以取值七=1,t2=2,+口一..任曰

t3=3。相应的x,y,z的值是

(x,y,z)=(4,18,78)

,■,***、・,**

y257t

四、证明题

1、已知2011是质数，则有2011|999。

2010个

证明：999=102011-1=0(mod2011)。

2010个

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

a是p的平方剩余，所以

pi

2a

=1P

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

3、已知p,q是两个不同的质数，且aP-i=1(modq),a2=1(modp),

证明：apq=a(modpq)。

证明：由p,q是两个不同的质数知(p,q)=1.于是由Fermat定理aP=a(modp),又由题设a^-1=1

(modp)得至U:aPA=(aQ)p=aP(aq-1)p=aP=a(modp)。

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

4、证明：若m,n都是正整数，则(mn)=(m,n)([m,n])o

证明：易知mn与[m,n]有完全相同的质因数,设它们为p[l<i<k),则

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

11

(m,n)([m,n])o

(mn)(m,n)[m,n](l)(1)(1Pk

PlP2

类似的题：设m二nm,m与m由相同的质因数，证明：(m)=m(m)

初等数论练习题六

、填空题

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

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

3、设3。I40!,而3-1140!,即40!,贝lja=_18_c

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

22｝。

5、不定方程x2+y2=z2,2|x,(x,y)=l,x,y,z>0的整数解是且仅是x二2ab,y二

a2b2,z二a2b2,其中a>b>0,(a,b)二1,a与b有不同的奇偶性。

&21x=9(mod43)的解是x三25(mod43)。

7、空=-l

二、计算题5益写成三个既约分数之和，它们的分母分别是3,5和7

17xyz

解：设,即35x21yl5z=17,因(35,21)=7,(7,15)=1,117,

分别解5x3y=t7tl5

得3u,y=2t5u,

t=115v,z=47v,vZ,

消去t得x=115v3u,

y2230v5u,v

u,vZo

令u=0,v=-1得到：x=4,y=-8,z=3即：—

in1

2、若3是质数p的平方剩余，问p是什么形式的质数？

故有解。

解：・••由二次互反律3

z=47v,

1pl(mod4)

注意到p>3p只能为pl(mod3)且

z1pl(mod4)

pl(mod3)

31只能下列情况p1舄4;

n1fmcrM)

pl(mod12)或pl(mod12)。

3、判断不定方程X+23y=17是否有解?

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

317

■/17=l(mod4)17空_6/

m1-71-7171717?

X2=17(mod23)无解，即原方程无解。

三、论证题

1、试证对任何实数x,恒有〔X〕+(x+±；=(2x)

证明：设X二冈+a,O<a<l

①当OWa<_L时，[x+1]=冈，[2x]=2冈…等式成立

r2

②当：…时，[x+!]=[x]+U2x]=2[x]+1…等式成立

故对任何实数—恒有冈+[x+JL]=[2x]。

2、证明：⑴当n为奇数时，31(2»1);

⑵当n为偶数时，引(2口1)。

证明：由2+1=(-1)Ml(mod3)立得结论。

3,证明：(1)当31nm为正整数)时,71(2"-1);

无论n为任何正整数(221)。

证明：(1)设n=3m贝U2-仁8"-1=0(mod7),BP：

由于2=1(mod7)得

3m3m*l3m+2

+1=2(mod7),2+1=3(mod7),n

故无论n为任何正整数，7|(2"1)。

4、设m>0,n>0,且m为奇数,证明：（2八1,2n+l）=1。

证明一：由m为奇数可知：2x1|2mn+i,又有2?1|2^-1,

于是存在整数X,y使得：（2n+l）X=2mn+1,（2t）y=2m】1

从而（2n+l）x-（2m-l）y=2。这表明：

（2川2+1）|2

由于2n+L2m.i均为奇数可知：（2匚2+1）=10

证明二：设（2?1,2n+l）=d则存在s,t€乙使得2]sd+1,2n=td-l0由此得到:

mnnmnm

2=（sd+1）,2=（td-1）

mn

于是2=pd+仁qd-1,p,q€乙所以：（q-p）d=2O

从而dl2,就有d=l或2。由因为m为奇数，所以d=L

即（2m-l,2n+l）=le

注：我们已证过：记M二小1,对于正整数a,b,有（M,M）=M3）。

显然当aMb,a,b为质数时，（M,M）=le

初等数论练习题七

、单项选择题

L设a和bMIE整数，则(啦ta，bl)=(A)ab

C.b

A.1D.(a,b)

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

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

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

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

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

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

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

13n1

A.B,C.D.

14n32n15n2

、填空题

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

3、

4、［-n］二-4。

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

6如果一个正整数具有21个正因数，问这个正整数最小是26X32=576。

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

三、计算题

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

解：分别解x2y=t

t3z=41

得x=t2u

y=uuZ,

t=413v

z=vvZ,

消去t得x=413v2u

y=u

z=vu,vZo

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

(x,y,z)=(413v2u,u,v),u>0,v>0,413v2u>0e

2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若人一人一组，则余3人。已知这

队士兵不超过170人,问这队士兵有几人？

解：设士兵有x人，由题意得x1(mod3),x2(mod5),x3(mod11).

在孙子定理中，取m=3,m=5,m=11,m=3511=165,

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

M=1,M=2,M=3,

贝Uxl551(-2)332315358(mod165),

因此所求的整数x=52+165t,tZo

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

3、判断同余方程x286(mod443)是否有解

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

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

空L21412M331

(I)8(/2143.31二原方程有解。

四、证明题

1、设(a,m)=1,do是使ad1(modn)成立的最小正整数，则

(i)d0(m;

(ii)对于任意的i,j,0i,jd°l,ij,有aiai(modn)。(1)

证明：(i)由Euler定理,d0(n),因此,由带余数除法，有

(n)=qdor,qZ,q>0z0r<d。。

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

(m)qgrr..

1□a。。a(modn),

r

即整数r满足a1(modn),or<doe

由d。的定义可知必是r=o,即do(n)o

(i)若式⑴不成立，则存在i,j,。i,jd°l,ij,使aai(modn).

不妨设i>jo因为(a,n)=1,所以auo(modn),o<ij<doo这与d。的定义矛盾，所以

式⑴必成立。

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

b玄1(modm,b01(modn)(1)

记d=(a,c),贝！1bd1(modm)。

证明：由裴蜀恒等式知，存在整数x,y,使得axcy二d,显然xy<0。

dcdcd

若x>0,y<0,由式(1)知：1bax二bby=b(b)yb(modn)o

若xv0,y>0,由式Q)知：1b，y=b叱ax=bd(ba)xbd(modm)。

3、设p是素数，pbn1,nN,则下面的两个结论中至少有一个成立：

(i)pbd1对于n的某个因数dvn成立；

(ii)p1(modn)。

若21n,p>2,则(ii)中的modn可以改为mod2no

证明：记d=(n,p1),由b111,bp11(modp),及第2题有

bd1(modp)。

若d<n厕结论(i)得证。

若d=n则np1,即p1(modn),这就是结论(ii)

并利用同余的基本性质,

若2|n,p>2,贝！1p1(mod2)。由此及结论(ii),得至I」p1

(mod2n)。

初等数论练习题八

一、单项选择题

1、设n>1,则n为素数是(n1)11(modn)的(C)。

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

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

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

A.34B.35C.36

D.82

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

A.79B.80C.81

D.-1,1—3,3

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

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

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

A.心B.UC.2

5n22n15n2

二、填空题

1、c(120)=360。

2、7355的个位数字是又_

3、同余方程3x二5(modl4)的解是人气ll(modL4)。

4、(D)=L

23—

5、[-2]=-2。

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

563

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

三、计算题

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

解：把429看成Jacobi符号我们有

563

42915631429^1

42913467

2—,563563~8~

429429429429

6714291(1产271671

27

67429429--6767

67(1)

429"67"677777

271131

—1)22271

2714

故方程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