初等数论练习题答案

初等数论练习题答案WrittenbyPeterat2021inJanuary初 等 数 论 练 习 题 一一、填空题1、d(2420)=12; (2420)=_880_2、设a,n是大于1的整数，若an-1是质数，则a=_2.3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1,0,1,2,3,4}.4、同余方程9x+12≡0(mod37)的解是x≡11(mod37)。518x-23y=100x=900+23t，y=700+18ttZ。.6、分母是正整数m的既约真分数的个数为_(m)_。7、18100被172除的余数是_256。8、65

=-1。 1039、若p是素数，则同余方程xp11(modp)的解数为p-1 。二、计算题1、解同余方程：3x211x200(mod105)。解：因105=357，同余方程3x211x200(mod3)x1(mod3)，同余方程3x211x380(mod5)x0，3(mod5)，同余方程3x211x200(mod7)x2，6(mod7)，故原同余方程有4解。作同余方程组：xb1(mod3)，xb2(mod5)，xb3(mod7)，其中b1=1，b2=0，3，b3=2，6，由孙子定理得原同余方程的解为x13，55，58，100(mod105)。2、判断同余方程x2≡42(mod107)是否有解？故同余方程x2≡42(mod107)有解。3、求（127156+34）28除以111的最小非负余数。解：易知1271≡50（mod111）。由502≡58（mod111）,503≡58×50≡14（mod111），509≡143≡80（mod111）知5028≡（509）3×50≡803×50≡803×50≡68×50≡70（mod111）从而5056≡16（mod111）。故（127156+34）28≡（16+34）28≡5028≡70（mod111）三、证明题1、已知p是质数，（a,p）=1，证明：a为奇数时，ap-1+(p-1)a≡0(modp)；a为偶数时，ap-1-(p-1)a≡0(modp)。证明：由欧拉定理知ap-1≡1(modp)及(p-1)a≡-1(modp)立得（1）和（2）成立。2、设a为正奇数，n为正整数，试证a证明a=2m1，当n1时，有

n2≡1(mod2n+2)。 （1）2=(2m1)2=1)11(mod23)，即原式成立。设原式对于n=k成立，则有

2k1(mod2k+

a2k=1q2k+2，其中qZ，所以 a1=(1+2)2=1q2k+31(mod2k+3)，q是某个整数。这说明式(1)当n=k1n成立。3、设p是一个素数，且1≤k≤p-1。证明：Ckp1

（-1）k(modp)。证明：设A=Ckp1

（p(p2) (pk)得：k!k!·A=（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(modp)又（k!，p）=1，故A=Ckp1

（-1）k(modp)4、设p是不等于3和7的奇质数，证明：p6≡1(mod84)。说明：因为84=4×3×7，所以，只需证明：p6≡1(mod4) p6≡1(mod3) p6≡1(mod7)84=4×3×7p37的奇质数，所以（p，4）=1，（p，3）=1，（p，7）=1。由欧拉定理知：p(4)≡p2≡1(mod4)，从而p6≡1(mod4)。同理可证：p6≡1(mod3) p6≡1(mod7)。 故有p6≡1(mod84)。注：设p是不等于3和7的奇质数，证明：p6≡1(mod168)。（见赵继源p86）初等数论练习题二一、填空题1、d(1000)=_16_；σ(1000)=_2340_.2、2010!的标准分解式中，质数11的次数是199 .3、费尔马(Fermat)数是指Fn=22n+1,这种数中最小的合数Fn中的n=5。4、同余方程13x≡5(mod31)的解是x≡29(mod31)5、分母不大于m的既约真分数的个数为(2)+(3)+…+(m)。6、设7∣(80n-1),则最小的正整数n=_6 .7、使41x+15y=C无非负整数解的最大正整数C= 559 .8、46=_1 .1019p是质数，np1，则同余方程xn1(modn.二、计算题1、试求200220032004被19除所得的余数。解：由2002≡7(mod19) 20022≡11(mod19) 20023≡1(mod19)又由≡22004≡（22）1002≡1(mod3)可得：200220032004≡20023n+1≡(20023)n×2002≡7(mod19)24x106x180(mod5)。Fermatx(mod5)，因此，原同余方程等价于x30(mod5)x0，1，2(mod5)分别代入上式进行验证，可知这个同余方程解是x1(mod5)。3a=5，m=21,ax1(modm)x。解：因为（5,21）=1，所以有欧拉定理知5(21)≡1(mod21)又由于(21)=12，所以x|12，而12的所有正因数为1,2,3,4,6,12。于是x应为其中使5x1(mod12)成立的最小数，经计算知：x=6。三、证明题1、试证13|(54m+46n+2000)。(提示：可取模13进行计算性证明)证明：54m+46n+2000252m+642n+2000（-1）2m+（-1）2n+200020020(mod13)。2Wilson定理的逆定理：若n>1，并且(n1)!1(modn是素数。n是合数，即n=nn，1<n<n1)!1(modn)，得12 1 101(modn)，矛盾。故n是素数。s1ss3、证明：设数。s

p表示全部由1组成的s位十进制数，若

是素数，则s也是一个素证明：假设s是合数，即s=ab，1<a，b<s。则p110s110a)b110a1M，其中M＞1是正整数。s 9 9 9s由p＞1也是正整数知

是合数，这与题设矛盾。故s也是一个素数。a s42p1(1)p0(mod2p1)。1(2p1)(2p)(1)p(p!)2(mod2p(1)p0(mod2p1)。5、设p是大于5的质数，证明：p4≡1(mod240)。（提示：可由欧拉定理证明）证明：因为240=23×3×5，所以只需证：p4≡1(mod8)，p4≡1(mod3)，p4≡1(mod5)即可。事实上，由(8)=4，(3)=2，(5)=4以及欧拉定理立得结论。初等数论练习题三一、单项选择题1、若n＞1，(n)=n-1是n为质数的（C ）条件。A.必要但非充分条件B.充分但非必要条件C.充要条件D.既非充分又非必要条件2、设n是正整数，以下各组a，b使b为既约分数的一组数是（ D ）。a=n+1,b=2n-1 =2n-1,b=5n+2 =n+1,b=3n+1 =3n+1,b=5n+23、使方程6x+5y=C无非负整数解的最大整数C是（ A ）。4、不是同余方程28x≡21(mod35)的解为（ D ）。≡2(mod35) B.x≡7(mod35) C.x≡17(mod35)5、设a是整数，(1)a≡0(mod9) (3)a的十进位表示的各位数字之和可被9整除

D.x≡29(mod35)(4)划去a的十进位表示中所有的数字9，所得的新数被9整以上各条件中，成为9|a的充要条件的共有（C ）。个二、填空题

个个 个1、σ(2010)=_4896 ；(2010)=528。2、数C20100

的标准分解式中，质因数7的指数是_3。3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中，最大者是97。4、同余方程24x≡6(mod34)的解是x1≡13(mod34)x2≡30(mod34)_。5、整数n>1，且(n-1)!+1≡0(modn),则n为素数。6、3103被11除所得余数是_5_。7、60=_-1_。 97三、计算题13x10(mod5)是否有三个解；(ⅱ)x62x54x230(mod5)是否有六个解？解：(ⅰ)2x33x10(mod5)3x24x30(mod5)x=(x33x24x3x5)+(6x212x15)，其中6x212x15的系数不都是5的倍数，故原方程没有三个解。(ⅱ)因为这是对模5的同余方程，故原方程不可能有六个解。2、设n是正整数，求C12n

,C32n

,,C2n2n

的最大公约数。解：设(C1

,

,C2n1d，由

C2n1

22n1d22n1，2n 2n 2n 2n 2n 2n设2k|n且2k+1|n，即2k+1||n，2n2n2k+1||C2n

及2k1|Ci 2n

Ci1i 2n

，i=3,5,,2n1得d=2k+1。3、已知a=18,m=77,求使ax1(modm)成立的最小自然数x。解：因为（18,77）=1，所以有欧拉定理知18(77)≡1(mod77)。又由于(77)=60，所以x|60，而60的所有正因数为1,2,3,4,5,6,10,12,15,20,30,60。于是x应为其中使18x1(mod77)成立的最小数，经计算知：x=30。四、证明题1、若质数p≥5,且2p+1是质数，证明：4p+1必是合数。证明：因为质数p≥5,所以（3，p）=1，可设p=3k+1或p=3k+2。当p=3k+1时，2p+1=6k+3是合数，与题设矛盾，从而p=3k+2，2p+16k+54p+1=12k+9=3(4k+3)是合数。注p=6k+r，r=0,1,2,3,4,5。再分类讨论。2、设p、q是两个大于3的质数，证明：p2≡q2(mod24)。证明：因为24=3×8，（3,8）=1，所以只需证明：p2≡q2(mod3) p2≡q2(mod同时成立事实上，由于（p，3）=1，（q，3）=1，所以p2≡1(mod3)，q2≡1(mod3)，p2≡q2(mod3)p，qp2≡1(mod8)q2≡1(modp2≡q2(mod8)。故p2≡q2(mod24)。3、若x,y∈R+，（1）证明：[xy]≥[x][y]；（2）试讨论{xy}与{x}{y}的大小关系。注：我们知道，[xxxy=[x][y]+β[x]+α[y]+αβ所以[xy]=[x][y]+[β[x]+α[y]+αβ]≥[x][y]。（2）{xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。1 1当x=y=2时，{xy}={x}{y}=4；当x=3，y=1时，{xy}=3，{x}{y}=1，此时{xy}＞{x}{y}；2 2 4 4当x=-1，y=-1时，{xy}=1，{x}{y}=1，此时{xy}＜{x}{y}。2 3 6 3c4、证明：存在一个有理数

，其中d<100,能使[k

c]=[k73]d d 100对于k=1，2，….，99均成立。证明：由（73，100）=1c，d73d-100c=173从而100

kck-d

=k(73d100c)100d

k=100d

，由k<100可知：0＜73100

kc 1k-d＜d[k c[k 设d ，则d

＜n+1=

n1d,于是d73k＜kc1≤n1d=n+1，]c100 d d]cd故[k73]=n=[k 。d100初等数论练习题四一、单项选择题1、若是合数，则最小的n是(D )A.2 B.3 C.4 D.52、记号baa表示ba｜a但ba+1|a.以下各式中错误的一个是(B A.1820! B.1550! C.119100! D.116200!3、对于任意整数n，最大公因数(2n+1，6n-1)的所有可能值是( A )A.1 B.4 C.1或2 D.1，2或44、设a是整数，下面同余式有可能成立的是(C )。A.a2≡2(mod4) B.a2≡5(mod7) C.a2≡5(mod11) D.a2≡6(mod5、如果a≡b(modm)，c是任意整数，则下列错误的是（A ）A．ac≡bc(modmc) B．m|a-b C．(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-1与5n+7的最大公因数达到最大可能值，整数n应满足条件n=26k+9，k∈Z。4、在5的倍数中，选择尽可能小的正整数来构成模12的一个简化系，则这组数是{5,25,35,55}5、同余方程26x+1≡33(mod74)的解是x1≡24(mod74)x2≡61(mod74)_。6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10,y=4。7、54=_-1_。 89三、计算题1、设n的十进制表示是13xy45z，若792n，求x，y，z。792=8911792n8n，9n及。我们有8n845z z=6，以及9n913xy45z=19xy9xy1，(1)11n11z54yx31=3yx113y。(2)0y9，(1)与式(2)分别得出xy1=9或3yx=011xy1ayxba918，b0110xy9的条件下解这四个方程组，得到：x=8，y=0，z=6。2、求3406的末二位数。（3，100）=1，∴3φ(100)≡1（mod100），φ(100)=φ(22·52)=40,∴340≡1(mod100)∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod100)∴末二位数为29。3、求(214928+40)35被73除所得余数。解：(214928+40)35≡(3228+40)35≡[(32×32)14+40]35≡(102414+40)35≡(214+40)35≡(210×24+40)35≡(25+40)35≡7235≡-1≡72(mod73)四、证明题1、设a,a,,a

是模m的完全剩余系，证明：1 2 m（1）当m为奇数时，a+a++a≡0（modm）；1 2 m（2）当m为偶数时，a+a++a≡m（modm）。1 2 m 2证明：因为{1,2,,a,a,,a}都是模m的完全剩余系，所以1 2 mmai

im(m(mod2i1 im(m2当m由m1m(m22m)。

maii1

m(m1)2

0(mod当m（m,m+1）=1m

m(m

m(modm)。ii1

2 2（m）2m＞2，a1a2a(m)m的任一简化剩余系，则

aii1

0(modm).a1,a2,,a(m)mm-a1,m-a2m-a(m)m的一个简化剩余系，于是：

（m）

(m)

ma)(modm).从而：

（m）

m(m)(modm).a(2ai i ia(2ai1 i1 i1m＞2，(m)

（m）ai

m（m）0(modm).2i13、设m>0是偶数，{a1,a2,,am}与{b1,b2,,bm}都是模m的完全剩余系，证明：{a1b1,a2b2,,ambm}m的完全剩余系。证明：因为{1,2,,a,a,,a}都是模m的完全剩余系，所以1 2 mmai

im(m2 2

(mod。 (1)同理 mbii1

i1 i1m(mod。 (2)2如果{a

b,

b,,

b}是模m的完全剩余系，那么也有1 1 2

2 m(aii1

mb)i

m(modm)。2联合上式与式(1)和式(2)，得到 0mm

m(modm)，2 2 2这是不可能的，所以{a1b1,a2b2,,ambm}m的完全剩余系。4、证明：1）2730∣x13-； （2）24x(x+2)(25x-1；（3）504∣x9-3； 4）p＞3，证明：6p∣xp-x。证明：（1）因为2730=2×3×5×7×13，2,3,5，7,13两两互质，所以：由x13-x=x(x12-1)≡0(mod2)知：2∣x13-x；13∣x13-x；x13-x=x(12-1)x(2-1(x2+1)(8+4+1≡0(mod3知：3∣x13-；x13-x=x(12-1)x(4-1(x8+4+1≡0(mod55∣x13-；x13-x=x(12-1)x(6-1(x6+1≡0(mod7知：7∣x13-。2730∣x13-。同理可证（2）、（3）、（4）。初等数论练习题五一、单项选择题1x、ym、n的完全剩余系，若（C）mn的完全剩余系。m、n都是质数，则mynx B.m≠n，则mynxC.（m，n）=1，则mynx D.（m，n）=1，则mxny2、1×3×5×…×2003×2005×2007×2009×2011标准分解式中11的幂指数是(A)。3、n为正整数，若2n-1为质数，则n是(A)A.质数 B.合数 (k为正整数)4、从100到500的自然数中，能被11整除的数的个数是(B)。5、模100的最小非负简化剩余系中元素的个数是(C)。二、填空题1a+≡0(mod有解的充分必要条件是(a,)∣b。2、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数，(q)p

p1q1 2011(1)22 2011q3、被3除所得的余数为_1 。4、设n是大于2的整数，则(-1)(n)= 1 。5、单位圆上的有理点的坐标是(

2ab

,a2b2)或(a2b2, 2ab

)，其中a与b是不全为零的整数。

a2b2

a2b2

a2b2

a2b26、若3258×a恰好是一个正整数的平方，则a的最小值为362。7、已知2011是一素数，则 72 =_-1_。 三、计算题1、求32008×72009×132010的个位数字。解：32008×72009×132010≡32008×（-3）2009×32010≡-32008+2009+2010≡-36027≡-3×（32）3013≡3(mod10)。2、求满足(mn)=(m)+(n)的互质的正整数m和n的值。解：由（m，n）=1知，(mn)=(m)(n)。于是有：(m)+(n)=(m)(n))=n)=b，即有：a+b=aa∣bb∣aa=b。2a=a2a=2，即(mn)=2m=3,n=4m=4,n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100斤，问各买几斤?解：设买甲物x斤，乙物y斤，丙物z斤，则5x3y

1z=100，3xyz=100。消去得到 7x4y=100。 (1)显然x=0，y=25是方程(1)的解，因此，方程(1)的一般解是x4t ，y257t因为x＞0，y＞0，所以 0＜t3。即t可以取值t1

=1，t2

=2，t3

=3。相应的x，y，z的值是(x,y,z)=(4,18,78)，(8,11,81)，(12,4,84)。四、证明题120112011|9。2010个9=12011-≡0(mod2011。2010个2p4n+1app-app=4n+1，ap的平方剩余，所以= =pa a 1= = p p pp

p2

a=1p=1

即：p-a也是p的平方剩余。3、已知p,q是两个不同的质数，且ap-1≡1(modq),aq-1≡1(modp),证明：apq≡a(modpq)。证明：由p,q是两个不同的质数知（p，q）=1。于是由Fermat定理ap≡a(modp),又由题设aq-1≡1(modp)得到：apq≡(aq)p≡ap(aq-1)p≡ap≡a(modp)。同理可证：apq≡a(modq)。故：apq≡a(modpq)。4、证明：若m,n都是正整数，则(mn)=（m,n）([m,n])。证明：易知mn与[m,n]有完全相同的质因数，设它们为pi(1≤i≤k)，则又mn=（m,n）[m,n]故n)[m

1p1

1) p2

1)(m,n)([m,n])。pkm=m1m2，m1与m由相同的质因数，证明：(m)=m2(m1)。初等数论练习题六一、填空题1、为了验明2011是质数，只需逐个验算质数2，3，5，…p都不能整除2011，此时质数p至少是_43 。2、最大公因数(4n+3,5n+2)的可能值是_1,7 。33∣40!3α+|40340，则α=_18_。43n+18的一个完全系的最小那些数是{1,4,7,10,13,16,19，22}。5、不定方程x2+y2=z2,2|x,(x,y)=1,x,y,z>0的整数解是且仅是x2==ab0，(a1，a与b有不同的奇偶性。6、21x≡9(mod43)的解是x≡25(mod43)。 7、73=-1 199二、计算题1173，57。105解：设17

xyz

，即35x21y15z=17，因(35,21)=7，(7,15)=1，117，故有解。

105 3 5 7分别解5x3y=t 7t15z=17得 x=t=2tt=1115v，z=4消去t得 x=1115vy=2230vz4。u=0，v=-1x=4，y=-8，z=3。即：

4

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

p1

p， (1) p p

3p

p4)p>3，pp

1(mod3)且 3

p4)∴3p

pp1只能下列情况p4) p1 ∴pp12。3、判断不定方程x2+23y=17是否有解？解：只要判断x2≡17(mod23)是否有解即可。∵17≡1(mod4)

172362331721 23 17 17 1717 17 3 3∴x2≡17(mod23)无解，即原方程无解。三、论证题1、试证对任何实数x,恒有〔x〕+〔x+1〕=〔2x〕2证明：设x=[x]+α,0≤α<1

1时,[x+1]=[x],[2x]=2[x] ∴等式成立2 2②当11时,[x+1]=[x]+1,[2x]=2[x]+1 ∴等式成立2 2故对任何实数x,恒有[x]+[x+1]=[2x]。22、证明：（1）当n为奇数时，3∣（2n+1）；（2）当n为偶数时，3|（2n+1）。证明：由2n+1≡（-1）n+1（mod3）立得结论。3、证明：1）3∣n（n为正整数）时，7∣（2n-1）；（2）无论n为任何正整数，7|（2n+1）。证明：1）n=3m，2n-1=m-1≡0mod7），即：7∣（2-1）；（2）23m≡1（mod7）得23m

+1≡2（mod7），23m+1

+1≡3（mod7），23m+2+1≡5（mod7）。n为任何正整数，7（2n+1）。4、设m＞0，n＞0，且m为奇数，证明：（2m-1，2n+1）=1。证明一：由m为奇数可知：2n+1︱2mn+1，又有2m-1︱2mn-1，x,y使得：（2n+1）x=2mn+1,(2m-1)y=2mn-1。从而（2n+1）x-(2m-1)y=2。这表明：（2m-1，2n+1）︱2由于2n+1，2m-1均为奇数可知：（2m-1，2n+1）=1。证明二：设（2m-1，2n+1）=d，则存在s,t∈Z,使得2m=sd+1,2n=td-1。由此得到：2mn=(sd+1)

n,

=(td-1)m于是2mn=pd+1=qd–。所以：（q=2。从而d=12md=1即（2m-1，2n+1）=1。n a b (a,注：我们已证过：记M=2n1，对于正整数a，b，有(M,Mn a b (a,b显然当a≠b，a,b为质数时，(Ma,M)=1。b初等数论练习题七一、单项选择题1、设a和b是正整数，则([a,b],[a,b])=（ A ）a bB．a C．b D．(a,b)2、176至545的正整数中，13的倍数的个数是（B ）A．27 B．28 C．29 D．303、200!中末尾相继的0的个数是（ A ）A．49 B．50 C．51 D．524、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（B ）的倍数 B．3的倍数C．4的倍数 D．5的倍5、设n是正整数，下列选项为既约分数的是（A ）A．4

B．n1 C．2n

D．n114n3二、填空题

2n1 5n2

11、314162被163除的余数_1 。（欧拉定理）2、同余方程3x≡5(mod13)的解是x≡5(mod13)。3、(365)=1。18474、［-π］＝-4。5、为使n-1与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+1,k∈Z。6、如果一个正整数具有21个正因数，问这个正整数最小是26×32=576。7、同余方程x3+x2-x-1≡0(mod3)的解是x≡1,2(mod3)。三、计算题1x2y3z=41的所有正整数解。x2y=tt3z=41得 x=t2uy=uuZ，t=413vz=vvZ，消去t得x=413v2uy=uz=v 。(x,y,z)=(413v2u,u,v)，u>0，v>0，413v2u>0。2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？解：设士兵有x人，由题意得x1(mod3)，x2(mod5)，x3(mod11)。在孙子定理中，取m1

=3，m2

=5，m3

=11，m=3511=165，M=55，M1 2

=33，M3

=15，M=1，M1 2

=2，M3

=3，则 x1551（-2）332315358(mod165)，因此所求的整数x=52+165t，tZ。由于这队士兵不超过170人，所以这队士兵有58人。3、判断同余方程x

?解：286=2×143，433是质数，(143，443)=1奇数143不是质数，但可用判定雅可比符号计算的勒让德符号1431 7114311433

11

8 2

7 3

∴原方程有解。四、证明题

7

1、设(a,m)=1，d0

是使ad1(mod(ⅰ)d(m)；0i，j，0jd0

1，i，有aiaj(mod（1）证明：(ⅰ)由Euler定理，d0

，因此，由带余数除法，有(m)=qd0

r，qZ，q>0，0r<d。0因此，由上式及d0

的定义，利用欧拉定理得到1a(m)aqd0

ar(modm)，即整数r满足ar1(modr<d。0d的定义可知必是r=0，即d0 0(ⅱ)若式(1)不成立，则存在i，j，0jd0

1，iaiaj(mod不妨设i>1，所以j0(mod<ij<d。0这与d0

的定义矛盾，所以式(1)必成立。2、证明：设a，b，c，m是正整数，m>1，(b,m)=1，并且ba1(modm)，bc1(modd1(modaxcy=，显然xy<0。若x>0，y<0，由式(1)知：1bax=bdbcy=bd(bcybd(mod若x<0，y>0，由式(1)知：1bcy=bdbax=bd(ba)xbd(modm)。3、设p是素数，pbn1，nN，则下面的两个结论中至少有一个成立：(ⅰ)pbd1对于n的某个因数d<n成立；(ⅱ)p1(modn)。若2>2，则(ⅱ)中的modn可以改为mod。证明：dp1)，由bn1，bp11(modp)，及第2bd1(modd<d=np1，即p1(mod若2|n，p>2，则p1(mod2)。由此及结论(ⅱ)，并利用同余的基本性质，p1(mod2n)。初等数论练习题八一、单项选择题1n>1，则n为素数是(n1)!1(mod（C）。A.必要但非充分条件 B.充分但非必要条C.充要条件 D.既非充分又非必要条2、小于545的正整数中，15的倍数的个数是（C）3、500!的标准分解式中7的幂指数是（D ）410的简化剩余系的是（D）,9,－3,－1 ,－1,7,9 ,7,11,13 D.－1,1,－3,35n是正整数，下列选项为既约分数的是（A）1

n1

2n1

n15n2 2n1 5n2 1二、填空题1、σ（120）=360。2、7355的个位数字是3。3、同余方程3x≡5(mod14)的解是x≡11(mod14)。4、（17）=1。2325、［- ］＝-2。26、如果一个正整数具有6个正因数，问这个正整数最小是12。7、同余方程x3+x2-x-1≡0(mod5)的解是x≡±1(mod5)。三、计算题1、已知563是素数，判定方程x2429(mod563)是否有解。563解：把429Jacobi符号563 429563563134 2 6767-）. .563

2 2 429

429

429

429429

8 429

67(1)671429429276767..429

2.2

67

67

67

2 227

27

13(1)2711312711，..27 2 2 13 13 故方程x2429(mod563)有解。2、求出模23的所有的二次剩余和二次非剩余。解：模23的所有的二次剩余为x1,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、试求出所有正整数n，使得1n＋2n＋3n＋4n能被5整除。解：若n为奇数，则1n＋2n＋3n＋4n1n＋2n＋（-2）n＋（-1）n0(mod5)；若n=2m，m∈Z，则1n＋2n＋3n＋4n12m＋22m＋（-2）2m＋（-1）2m2+2×22m=2+2×4m=2+2×(-1)m(mod5)；当m为奇数时，1n＋2n＋3n＋4n0(mod5)；当m为偶数时，1n＋2n＋3n＋4n4(mod5)。4|n时，5∣1＋2n＋3n＋n。四、证明题1、p>2，则的质因数一定是2pk+1形。q2p-12p-1q≠2，（2，q）=12p≡1（mod。h2x≡1（mod这与ph=p,p|q-1q-1为偶数，2|q-1，2p|q-1，q-1=2pk, q=2pk+1。2、设（m,n）=1,证明：m(n)+n(m)≡1(modmn)。证明：因为（m,n）=1，所以由欧拉定理知：n(m)≡1(modm)，m(n)≡1(modn)于是m(n)+n(m)≡1(modm)m(n)+n(m)≡1(modn)。又因为（m,n）=1，所以m(n)+n(m)≡1(modmn)。注：此题也可这样表述：若两个正整数a,b互质，则存在正整数m,n，使得am+bn≡1(mod)3、设（a,b）=1,a+b≠0,p(abapbp)或p。ab说明：事实上，设(ab,apbp)d，只需证明：d|p即可。aba+b≡0(moda+b)，即a≡-b(moda+b)，知ak≡(-b)k(moda+b)。其 中 0 ≤ k ≤ 。 又apbpap1ap2babp2bp1bp1bp1bp1pbp1(modab)。ab令(ab,apbp)d，则d|pbp-1。又（a,b）=1，d|（a+b）知（d,b）=1。ab（否则设（d,b）=d′＞1d′︱a和d′︱b，这与（a,b）=1矛盾。）于是（d。故d|即 d=1或。初等数论练习题九一、单项选择题1、以下Legendre符号等于-1的30被-1是(D )A.3

B.4

C.5

D.611

11

11

11 2、100至500的正整数中，能被17整除的个数是(B )A.23 B.24 C.25 D.263、设3|500!，但31500！，则α=( C )A.245 D.2484、以下数组中，成为模7的完全剩余系的是(C )A.－14，－4，0，5，15，18，19C.－4，－2，8，13，32，35，135

B.7，10，14，19，25，32，40D.－3，3，－4，4，－5，5，05、设n是正整数，则以下各式中一定成立的是(B )A.(n+1，3n＋1)=1C.（2n，n＋1）=1二、填空题1、25736被50除的余数是1。

B.（2n－1，2n＋1）=1D.（2n＋1，n－1）=12、同余方程3x≡5(mod16)的解是x≡7(mod16)。3、不定方程9x－12y=15的通解是x=-1+4t，y=-2+3t，tZ。4、323

=1。 415、实数的小数部分记为{x}，则{－5}＝。46、为使3n与4n＋1的最大公因数达到最大可能值，整数n应满足条件n=3k+2，k∈Z。7、如果一个正整数具有35个正因数，问这个正整数最小是26×34=5184。三、计算题1、解不定方程9x＋24y－5z=1000。解：解因（9，24）=3，（3，-5）=1知原方程有解。原方程化为9x24y=3t， 即 3x8y=(1)3t-5z=1000 3t-5z=1000， (2)解(2

t5uz200

，uZ，再解3x8y=5u

xu8v，u，vZ。yuxu8v故 yu，。z2002A={x,x,,x}是模mx,)=1，求

1 2 m{}axb{}i 。mi1解：当x通过模m的完全剩余系时，ax b也通过模m的完全剩余系，因此对于任意的i（1 i i

b一定与且只与某个整数j（1 j 同余，即存在整数k，使得axi

b=kmj。从而：3n2，

i。即在数列1,2,,n中，与n互素的整数之和。1in(i,n)1解：设在1,2,,n中与n互素的(n)个数是a,a,,a，(a,n)=1，1a

n1，1i1 2 (n) i i则 (na,=1，1nan1，1ii i因此，集合{a,a,,anana,,na

}是相同的，于是1 2 (n) 1 2 a a a =(na)(na) (na)，1 2 (n) 1 2 (n)2(a a1 2

a

)=因此：a a1 2

a(n)

=1n(n)。24m1，(a1，xxx

是模m(m{ax}。1 2

imi1其中{x}表示x的小数部分。解：设ax=mq r，0 r<由x通过模m的简化剩余系知：ax也通过模m的简化i i i i i i剩余系，从而r通过模m的最小非负简化剩余系，于是：i(m{ax}(mqr}(m)r

1(m)r

1m(m)1(m)。i im i

im m

2m 2i1 i1 i1四、证明题

i11、a是有理数，bbaccab∣c。(提示：利用带余数除法解决。)证明：设c=bq+r，0≤r＜b，q∈Z，则ca=(ba)q+ra。ca，ba∈Z，ra∈Z，ra=0a≠0r=0b∣c。2、设p是素数，证明：(ⅰ)对于一切整数11(x1)(x2)(xp1)(mod(ⅱ)(p1)! 1(modp)。证明：(ⅰ)110(modx1，2，，p1(mod11(x1)(x2)(xp1)(mod(ⅱ)在(ⅰ)中令x=。n a32n，p

-1,则 1。p pp∣an-1an1(modp)。又（p，a）=1an+1a(modp)。n1

2 a2n，所以(a

)2a(modp

a(modp)

1。p4p=4m+1（1。pmm(1ppp

)

p12 1)2m1。p15、设p是奇质数，p1(mod4(p1)!)22

1(modp)解由Wilson定理有：注：（1）设 p 为质数且 p＝，则同余方程x2p)的解是x12 (2m)(modp。pp＝4m+1aa2≡1(modp)。初等数论练习题十一、单项选择题p1、设p是大于1的整数，如果所有不大于 的质数都不能整除p，则p一定是p（A）。A.素数 B.合数 C.奇数 D.偶数2、两个质数p，q，满足p+q=99，则pq的值是（B ）B.9413

q pC.9413

D.9413194 99 1113、2010！的标准分解式中，7的最高幂