唯一性：假设存在两对整数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?r2 r1?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参考答案：D 4：[单选题]

下面的数是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参考答案：D 9：[单选题]100与44的最小公倍数是（ ）。 A：4400B：2200C：1100D：440参考答案：C

10：[单选题]使3的n次方对模7同余于1的最小的正整数n等于（ ）。 A：6B：2C：3D：13参考答案：A 11：[单选题]设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（ ）。 A：0B：1C：2D：3参考答案：A 12：[单选题]下面的（ ）是不定方程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参考答案：C 18：[单选题]360与200的最大公约数是（ ）。 A：10B：20C：30D：40参考答案：D 19：[单选题]如果 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(mod 11)，于是

128121≡128≡7(mod 11)，所以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<5，所以1001！的质因数分解式中2的个数比5的个数要多，因此，只要考察1001！中因子5的个数即可。因为：1001÷5=200……1，1001÷5=40……1，1001÷5=8……1，1000÷5=1……375，又因为200+40+8+1=249，所以答案为249。即1001！中末尾0的个数为249个。

5．求不定方程3x + 5y = 20的一切非负整数解。

解：因为（3，5）=1，所以不定方程有整数解。由观察知x0 = 0，y0 = 4是不定方程3x+5y=20的一个整数解，所以不定方程3x+5y=20的一切整数解是

4

2

3

?x?5t??y?4?3t，其中t取一切整数。

?x?04?0?t?y?0可解得3，所以t?0,1，故不定方程的一切非负整数解为 由??x?0?x?5??y?1。 y?4?，?6．求出不定方程7x + 2y = 1的一个整数解，并写出其一切整数解的表达式。 解：因为（7,2）=1,1|1，所以不定方程有解。观察知其一个整数解是

?x0?1。 ?y??3?0?x?1?2t于是其一切整数解为?，t取一切整数。

y??3?7t?7．求不定方程15x + 10y + 6z = 61的一切整数解。

解：不定方程的一切整数解为

?x?5?2u?6v??y??5?3u?6v?z?6?5v?，其中u，v取一切整数。

8．计算欧拉函数值：?（100）。 解：100 = 22?52，由公式有

1122?52?(1?)?(1?)25= 40。 ?（100）=