初等数论试卷

本文格式为Word版，下载可任意编辑——初等数论试卷

一．填空题：

1、(?1859,1573)=1432、对于任意的正整数a,b，有[a,b]?ab.(a,b)3、x?[x]?{x}.4、22345680的标准分解式是

22345680?24?3?5?7?47?283.

5、整数集合A中含有m个整数，且A中任意两个整数对于m是不同余的，则整数集合A是模m的完全剩余系.

6、设a、b是任意两个正整数，则不大于a而为b的倍数的正整数个数为??.

b7、素数写成两个平方数和的方法是唯一的.8、不同剩余类中的任何两个不同整数对模m是不同余的.

9、n元一次不定方程a1x1?a2x2?……?anxn?c.有解的充分必要条件是

?a???(a1?a2……an)c.10、初等数论按研究方法分为：初等数论、解析数论、代数数论、几何数论.

11、数集合A是模m的简化剩余系的充要条件（1）A中含有f(m)个整数；（2）任意两个整数对模m不同余；

（3）A中每个整数都与m互素；

212、设n是正整数c2n1,c2n3,c2n2n?1的最大公约数为,k?113、若(a,b)?1，则

(a,bc)?(a,c).

14、81234被13除的余数是12.15、模7的最小非负完全剩余系是0、1、2、3、4、5、6.

二、判断题：

1、若n为奇数，则8|n?1。（√）2、设n、k是正整数n与nkk?42的个位数字不一定一致。（×）

3、任何大于1的整数a都至少有一个素因数.（√）4、任何一个大于1的合数与a，必然有一个不超过a的素因数.（√）5、任意给出的五个整数中必有三个数之和能被整数3整除.（√）6、最大公约数等于1是两两互素的必要而不充分条件.（√）7、设p是素数，a是整数，则pa或(p,a)?1.（√）8、假使a1,a2……an是互素的，则a1,a2……an一定两两互素（×）

9、设p是素数，若pab，则pa且pb.（×）10、（刘维尔定理）设p是素数，则(p?1)！??1(modp)（√）11、m是正整数(a,m)?1，则a?(m)?1(modm).（√）

12、由于每个非零整数的约数个数是有限的，所以最大的公约数存在，且正整数。（√）13、设d是a1,a2……ak的一个约数，则da1,a2……ak（√）14、1978103?19783不能被10整除。（×）15、1?311??(n?2)是整数（×）2nn16、n为正整数，若2?1为素数，则n不一定是素数（×）17、若n?1并且(n?1)!?(modn),则n不是素数（×）

18、设f(x)是整系数多项式，并且f(1),f(2),……f(m)都不能被m整除，则f(m)?0有整数解（×）

19、若(m1,m2)?1（m1,m2是任意两个互质的正整数），是则?(m1m2)??(m1)??(m1)（×）

20、假使两个整数相互整除，则这两个数仅相差一个符号（×）三、计算题：

221、设a、b是整数且9a?ab?b，则3(a,b).

22222解：由9a?ab?b?3(a?b)?3ab?3(a?b)?3a?b?9(a?b).22再由9a?ab?b得93ab?3ab.

由定理4的推论1（设p是素数，若pab，则pa或pb.）得3a或3b.2、求(12345,678).

（12345,339）?（12023,339）?（6003,339）?（5664,339）解：(12345,678).=

=（177,339）=（177,162）=（177,81）=（96,81）=（3,81）=3.

3、求(25733?46)26被50除的余数.解：根据定理4，有(257?46)3326?(733?4)26?[(7?72)16?4]26?[7?(?1)16?4]26

265?（7?4）?326?3（?35）??21?29（mod50)即所

求的余数是29.

19写成三个既约分数之和，它们的分母分别是2，3和5.3019xyz???即15x?10y?6z?19.解：设

302354、将

?15x?10y?5t?t??1?6u解得?(15,10)?5?d2?上述方程等价于??5t?6z?19?z?4?5u?x??1?6u?2v?x?t?2v?从而，?故?y?1?6u?3v(u,v?z)y??t?30??z?4?5u?即

取u?v?0得x??1,y?1,z?419114????302355、求不定方程3x?6y?15的解.解：

(3,6)?315?方程有解

由辗转相除法，可以知道x??1,y?1是方程3x?6y?3(x?2y?1?a?1,b?2)的一个解

所以，x0??5,y0?5就是原方程的解；由定理2知??x??5?2t（t?z)

?y?5?t6、用辗转相除法求整数x、y使得1387x-162y=(1387,162).

解：作辗转相除：1387?(?162)?(?8)?91，?162?91?(?2)?20

91?20?4?11，20?11?1?9，11?9?1?2，9?2?4?1，2?1?2?0由此可得n?6，q1??8，q2??2，q3?4，q4?1，q5?1，q6?4

x=(?1)n?1Qn?73，

y=(?1)np?625,又(1387,162).=rn?1，

n故1387?73?162?625?1?(1387,162)

177、将写成三个既约分数之和，它们的分母分别是3，5和7（第四章习题一1）

105解：设

17xyz???，即35x?21y?15z?17.105357因(35,21)?7,(7,15)?1，117，故有解.分

别

解

5x?3y?t得?tx??t?3u,y?2t?5u,u?Z,t?11?15v,z??4?7v,v?Z

消去t得x??11?15v?3u,y?22?30v?5u,z??4?7v,u、v?Z.对于任意的确定的u和v的值，都给出一种表示法。8、求最大的正整数k，使得10199!

解：由定理3（设n是正整数，n!?p1?p2……pk?1?2?kk是n!的标准分解式，则?i??[r?1?n]）pir

从而得知，

199199199!的标准分解式中所含的5的幂指数是[]?[2]?……?4755（199!?10k?A?2k?5k?A）所以所求得的最大正整数是47.

9、若四个数2839,4582,5164,6522被同一个大于1的整数除所得的余数一致，且不等于零，求除数和余数各是多少？

解：设除数为d，余数为r，则由d4582?2836?1746，d5164?4582?582，

r?,d6522?5164?1358，知d(17,5684,123)5?189由4此得d?97d?194,r?120.

3510、将2?1?34359738367分解因数.（第三章第四节Euler定理例7）3557解：若p2?1，则p是2?1或2?1的素因数或者p?1(mod70).

或235其中有31和127，由于2?1?31?127?8727391，所以2?1分别是因数只能用

35p?1(mod70).来寻求

在数列71、211、281……中经检验8727391?71?122921显然，122921的素因数也在31、127或数列71、211、281……中

简单计算122921不能被31、127整除，也不能被数列71、211、281……（122921?351）整除.

所以122921是素数，故2?1?31?127?71?122921

四、证明题：1、求证：平方数的正因数个数是奇数.

证明：由于每个自然数n的正因数个数是成对出现的，若d是n的因数，则数

当d?n时，则d?35n也是n的因dn.dn当d?n时，则d?即当n为平方数时，n是n的因数，与其配对的是n自身.

d于是，当且仅当n为平方数时，n的正因数个数是奇数.2、求证：若(a,b)?1，则(a?b,a?b)?1或2.

证明：假设d是a?b的任意一个公约数，则有da?b且da?b.于是d2a，d2b.又

(a,b)?1?d2从而，d?1或d?2.

4nnnn3、假设a为正整数，则51?2?3?4的充要条件为4n.

证明：由于?(5)?4，所以，由费马定理有k?1(mod5)故

(1?k?4).(r，?则r?，若

n?4q?

1n?2n?3n?4n?1r?2r?3r?4r?1r?2r?(?2)r?(?1)r

nnnn用r?0、1、2、3分别代入上式，则当r?1、2、3时51?2?3?4

nnnn当r?0时，4n，5不整除1?2?3?4.

nnnn因此，若a为正整数，则51?2?3?4的充要条件为4n.

4、证明：对任意整数n，f(n)?3n5?5n3?7n被15整除.证明：对任意整数n记作n?15q?r(0?r?15)

k由于对任意的整数m有a?a1m?r1则a与r1被m除的余数一致

222r?0n2?(15q?r)2?(15q)2?30qr?r2?15A1?r即n与r被15除的余数是一致的

k记为r1.

4同理，n与r被15除的余数是一致的记为r2.即r2?15B1?r1，r?15B2?r2则

44n4?15A2?r4.

考虑3n?5n?7被15除的余数

423n4?5n2?7?3(15A2?r4)?5(15A1?r2)?7

?3?15A2?3?(15B2?r2)?5(15A1?15B1?r1)?7?15Q?3r2?5r1?7?15Q??R

R.可见，3n?5n?7与3r2?5r1?7的余数一致记为

42?f(n)?n?(3n4?5n2?7)?(15C?R)(15q?r)?15O?Rr且f(n)与Rr有一致的余数

记为R?.

当r?0时，R??0即15f(n).

14的情形通过计算列出下表：

r?1、14r?2、13r?3、12r?4、11r?5、10

r?6、9r?7、8

r1?1r2?1

R?0R??0

r1?4r1?4r2?6

R?10R??0

r1?1r2?1

R?0R??0

r1?10r1?6r2?6

R?10R??0

r1?4

r2?1

R?0R??0

r2?10

R?12

r2?1

R?0R??0

R??0

5、定理（带余除法）：若a、b是两个整数，其中b≠0，则存在着两个整数q和r，使得

a?bq?r,0?r?b成立.而且q及r是唯一的.

证明：存在性：若ba，则a?bq(q?z)可以取r?0

若ba，考虑集合A?{a?kb,k?z}集合A中有无限多个正整数，设其中最小的正整数为

r?a?k0b.

则必有0?r?b，否则就有r?b（?r?b，若r?b，则ba矛盾，于是r?b即

r?a?k0b?b?a?k0b?b?0这样集合A中又有正整数a?k0b?b?r与r的最小

值矛盾）

故0?r?b，取q??k0使得a?bq?r,0?r?b成立.存在性得证

唯一性：假设存在两对整数q1、r1及q2、r2都使得a?bq?r,0?r?b成立.即有a?bq1?r1?bq2?r2(0?r1，r1,r2?b)，则b(q1?q2)?r2?r2?r1?b.

?br1?r2r1?r2?0?r1?r2?q1?q26、设A?{x1,x2……xm}是模m的一个完全剩余系，以{x}表示x的小数部分，证明：若

(a,m)?1，则?{i?1maxi?b1}?(m?1)m2证明：当x通过模m的完全剩余系时，ax?bR通过模m的完全剩余系.

因此，对任意的i(1?i?m)，axi?b一定与且只与某个整数j(1?j?m)同余即存在整数k使得：axi?b?km?j(1?j?m)

mmm?1axi?bjjj1m(m?1)1从而，?{}??{k?}??{}?????(m?1)

mmmmm22i?1j?1j?1j?1f(m)m7、设m?1,(a,m)?1，x1,x2,…,xf(m)是模m的简化剩余系，证明：其中{x}表示x的小数部分。

?{m}?2f(m).

i?1axi1证明：由题可设：axi?mqi?ri(0?ri?m)由xi通过模m的简化剩余系知ri通过模m的最

小

f(m)非负简

f(m)化剩余

f(m)系，

f(m)i?1于是由定理可知：

axi{}??mi?1ri{q?}??imi?1ri1{}??mi?1m?{ri}?11mf(m)?f(m)2m2ba8、设a、b是正整数，b?2则2?12?1

ba证明：（1）若a?b且2?12?1成立，则2b?1?2a?1?2b?2a?2?2a(2b?a?1)?2

于是a?1，b?a?1即b?2与b?2矛盾，故命题结论成立.

baaaaaa（2）若a?b且2?12?1，则2?1(2?1)?2?2?12?2?1?2?2?3

于是b?a?1，与b?2矛盾，故命题结论成立.（3）若a?b，记a?kb?r(0?r?b)此时

2kb?1?(2k?1)(2(k?1)b?2(k?2)b?……?1)?(2b?1)Q(Q?z).

故

2a?1?2kb?r?1?2r(2kb?1?1)?2r[(2b?1)Q?1]?1?(2b?1)Q??(2r?1)(Q??z)

babr由2?12?1?2?12?1，在（1）中已经证明这是不可能的，故命题结论成

立.

9、证明：存在无穷多个正整数a,使得n?a(n?1,2……)都是合数（即分成两项乘积即可）。证

明

：

取

4a?4k4,

对任意的

n?N,

有

n4?4k4?(n?2k2)2?4n2k2?(n2?2k2?2nk)?(n2?2k2?2nk)

n2?2k2?2nk?(n?k)2?k2?k2??k?2.3?n?N??N?a都是合数。

2210、证明：a、b、c?N，c无平方因子且abc,证明：ab.

4证明：设(a,b)?d,则有a?da1与b?db1,(a1,b1)?1.

22222由abc得a1b1c，a1c

由于c无平方因子，所以a1?1，a?d，b?ab1.即ab..11、对任意的正整数a、b、c.证明下面的结论成立。

（1）由bac且(a,b)?1,可得出b|c.（2）由bc与ac,且(a,b)?1.可推出abc.证明：（1）

(a,b)?1.?存在整数x与y使得ax?by?1.?acx?bcy?c.

bac?bacx?bcy.即bc

(2).由(a,b)?1,存在整数

x与yy1.又由bc与ac,得使得ax?b?abac,abbc.

因此，abqx?abpy?c?abc

12、设m是整数且4m,{a1,a2,…am}与{b1,b2,…bm}是模m的两个完全剩余系，证明：

{a1b1,a2b2,…,ambm}不是模m的完全剩余系。

证明：由于4m，若{a1b1,a2b2,…,ambm}是模m的完全剩余系，则其中的奇数与偶数各半.

又由于{a1,a2,…am}与{b1,b2,…bm}也是模m的两个完全剩余系，从而有aibi必需使ai，

bi同为奇数或偶数.即aibi?2(mod4),这对于4m的模m的完全剩余系是不可能的。

13、设a、b、c、d是整数，并且a?b(modm),c?d(modm).求证：

(i)a?c?b?d(modm).(ii)ac?bd(modm)

证明：(i)由于a?b(modm),c?d(modm)，由定义知ma?b，mc?d.

从而，m(a?b)?(c?d)?(a?c)?(b?d)故，a?c?b?d(modm).

(ii)由定理1（3）知存在整数q1与q2，使得a?b?q1m，c?d?q1m,

从而

a?c(?b1)q(m?d)?qm1?(2bd?q因)m此，qd11q.?qbmac?bd(modm).

初等数论

1：[单项选择题]已知361a是一个4位数（其中a是个位数），它能被5整除，也能被3整除，则a的值是（）。A：0B：2C：5D：9参考答案：C

2：[单项选择题]下面的（）是模4的一个简化剩余系。A：4,17B：1,15C：3,23D：13,6参考答案：B

3：[单项选择题]小于20的正素数的个数是（）。A：11B：10C：9D：8参考答案：D4：[单项选择题]

下面的数是3的倍数的数是（）。

A：19B：119C：1119D：11119参考答案：C

5：[单项选择题]-4除-39的余数是（）。A：3B：2C：1D：0参考答案：C

6：[单项选择题]一个正整数n的各位上的数字是0或1，并且n能被2和3整除，则最小的n是（）。A：1110B：1101C：1011D：1001参考答案：A

7：[单项选择题][[4.5]+[3.7]]等于（）。A：3B：4C：7D：8参考答案：C

8：[单项选择题]{{1.8}+{2.9}}等于（）。A：0.4B：0.5C：0.6D：0.7参考答案：D9：[单项选择题]100与44的最小公倍数是（）。A：4400B：2200C：1100D：440参考答案：C

10：[单项选择题]使3的n次方对模7同余于1的最小的正整数n等于（）。A：6B：2C：3D：13参考答案：A11：[单项选择题]设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（）。A：0B：1C：2D：3参考答案：A12：[单项选择题]下面的（）是不定方程3x+7y=20的一个整数解。A：x=0,y=3B：x=2,y=1C：x=4,y=2D：x=2,y=2参考答案：D

13：[单项选择题]下面的（）是模4的一个完全剩余系。A：9，17，-5，-1B：25，27，13，-1C：0，1，6，7D：1，-1，2，-2参考答案：C

14：[单项选择题]下面的（）是模12的一个简化剩余系。A：0，1，5，11B：25，27，13，-1C：1，5，7，11D：1，-1，2，-2参考答案：C

15：[单项选择题]若a，b均为偶数，则a+b为（）。A：偶数B：奇数C：正整数D：负整数参考答案：A

16：[单项选择题]1到20之间的素数是（）。A：1，2，3，5，7，11，13，17，19B：2，3，5，7，11，13，17，19C：1，2，4，5，10，20D：2，3，5，7，12，13，15，17参考答案：B

17：[单项选择题]假使a|b，b|c，则（）。A：a=cB：a=-cC：a|cD：c|a参考答案：C18：[单项选择题]360与200的最大公约数是（）。A：10B：20C：30D：40参考答案：D19：[单项选择题]假使a|b，b|a，则（）。A：a=bB：a=-bC：a=b或a=-bD：a，b的关系无法确定参考答案：C

20：[单项选择题]假使5|n，7|n，则35（）n。A：不整除B：等于C：不一定D：整除参考答案：D

21：[单项选择题]整数6的正约数的个数是（）。A：1B：2C：3D：4参考答案：D

22：[单项选择题]设n，m为整数，假使3整除n，3整除m，则9（）mn。A：整除B：不整除C：等于D：小于参考答案：A

初等数论其次次作业

填空题

1．16除100的余数是4_。

2．假使今天是星期一，那么从今天起再过1010天后是星期四。3．{3.2}=0.8；[2.84]=3。4．[{3.6}+{1.7}]=0.9。5．{{?4.2}?{2.3}}=______-1.5________。6．15的所有正因数的和是24。7．1260的标准分解式是1260?2?3?5?7。

8．20！的标准分解式是20!?2?3?5?7?9?11?13?17?19。9．98!的末尾有______22_________个零。

10．890的标准分解式是2×5×89。11．欧拉函数值?(50)?20。12．7除3301的余数是3。

13．不定方程ax+by=c有解的充要条件是(a,b)c。

14．设m为正整数，a，b为两个整数，假使用m去除a与b所得的余数一致，那么就称a，b对模m同余。

15．一次同余式ax?b(modm)有解的充分必要条件是(a,m)b。

16．模7的最小非负完全剩余系是0，1，2，3，4，5，6。17．（1516，600）=4。

18．不定方程ax+by=c(其中a，b，c是整数)有整数解的充要条件是（a，b）︱c。

19．710被11除的余数是1。20．77的个位数是_______3________。

初等数论第三次作业参考答案

计算题

1．写出400与600的标准分解式，并求出400与600的最大公因数。

32解400?2?5，600?2?3?5，(400,600)?2?5?200。

4232221884222．求128121被11除的余数。

解由于?(11)=10，而128与11互素，所以12810≡1(mod11)，于是

128121≡128≡7(mod11)，所以128121被11除的余数为7。3．求1050与858的最大公因数。

解：由于1050=2?3?52?7，858=2?3?11?13，所以(1050，858)=2?3=6。4．求1001！中末尾0的个数。

解：由于10=2?5，所以1001！中末尾相当于1001！的质因数分解式中2?5的个数。由于2

9．解同余式3x?8(mod10)。

解：由于（3,10）=1,1|8，所以同余式有解，并且只有一个解。由3x?10y?8得一个解?所以同余式的解为x?6(mod10)。10．解同余式组：

?x0?6

，y?1?0

?x?1(mod2)??x?1(mod3)。?x?1(mod5)?解：由于2，3，5两两互质，所以由孙子定理该同余式组有一个解。由孙子定理可得该同余式组的解为x?1(mod30)。11．解同余式28x?21(mod35)。

解由于（28，35）=7，而7|21，所以同余式28x?21(mod35)有解，且有7个解。同余式28x?21(mod35)等价于4x?3(mod5)，解4x?3(mod5)得x?2(mod5)，故同余式28x?21(mod35)的7个解为x?2，7，12，17，22，27，32(mod35)。12．解同余式组：

?x?1(mod3)。??x?2(mod7)解：由x?1(mod3)得x?1?3t1,t1?Z，将其代入x?2(mod7)得

1?3t1?2(mod7)，即3t1?1(mod7)，解得t1?5(mod7)，所以

t1?5?7t2,t2?Z，于是x?1?3t1?1?3(5?7t2)?16?21t2,t2?Z。所以同余式组的解

为x?16(mod21)。

初等数论第四次作业参考答案

证明题

1．证明：若a?b(modm)，c?d(modm)，则a?c?b?d(modm)。

m)，c?d(modm)得m|(a?b)，m|(c?d)，由整除的性质得证明：由a?b(modm|[(a?b)?(c?d)]，即m|[(a?c)?(b?d)]，所以a?c?b?d(modm)。

2．证明：设m,n为整数，求证m+n,m-n与mn中一定有一个是3的倍数。证明：若m或n为3的倍数，则mn是3的倍数；

若m是3的倍数加1，n是3的倍数加1，则m-n是3的倍数；

若m是3的倍数加1，n是3的倍数加2，则m+n是3的倍数；若m是3的倍数加2，n是3的倍数加1，则m+n是3的倍数；

若m是3的倍数加2，n是3的倍数加2，则m-n是3的倍数，结论成立。3．证明：若a|c，b|d，则ab|cd。

证明：由a|c，b|d知存在整数p，q使得c?ap，d?bq，所以cd?apbq?abpq，由于pq为整数，所以由整除的定义知ab|cd。4．证明：若n为自然数，求证9n+1?8n+9(mod64)。

证明：由于9?1(mod8)，所以9k?1(mod8)，k=2，3，…，n-1，于是9n-1+…+92+9+1?n(mod8)，所以9(9n-1+…+92+9+1)?n(mod8)，

从而9?(9-1)?(9n-1+…+92+9+1)?8n(mod64)，即9(9n-1)?8n(mod64)，所以9n+1?8n+9(mod64)。

5．若p为奇质数，证明2p|(22p-1–2)。

证明：由于p为质数，所以?(p)=p-1，又p为奇质数，所以(2，p)=1，于是由欧拉定理得2p-1?1(modp)，两边平方得22p-2?1(modp)，再由同余的性质有2?22p-2?2(mod2p)，即：22p-1?2(mod2p)。所以2p|(22p-1-2)。

6．证明：整数a，b对模m同余的充分与必要条件是m|(a?b)。

证明：设a?mq1?r，则r1?r2，因1，b?mq2?r2，0?r1，r2?m。若a≡b（modm）此a?b?m(q1?q2)，即m｜a－b。反之，若m｜a－b，则m|mq(1q?2)?(r1r?2)即a≡b（modm）。

7．设a是大于1的整数，证明a4?4是合数。证明：a?4?(a)?4a?4?4a

42222，因此m|r1?r2，但故rr1?r2?m，1?r2，

?(a2?2)2?4a2?(a?2?2a)(a?2?2a)22

22由于a?1且是整数，所以a?2?2a?1,a?2?2a?1，且均为整数，故当a是大于1

的整