2024年3月9日发(作者：赧易)

主要内容:

1．1.整除的概念

1．2.带余数除法

1．3.最大公因数的理论与性质

1．4.最小公倍数的理论与性质

1．5.辗转相除法

1．6.素数与合数

1．7.算术基本定理

1．8.高斯函数[x]与{x}及其应用

1.1.1 整除的定义与性质

1.整除的定义

定义 设a，b∈Z，b  0，若存在整数c，使得a = bc成立，则称a被b整除（或b整除a），并称a是b的倍数，b是a的约数（因数或除数），记为ba；

|a。如果不存在整数c使得a = bc成立，则称a不能被b整除，记为b

在整除的定义中应特别注意：

（1）0不整除任何整数（即0不能作除数），但任何非零数整除0；

在记号“ba”中蕴含着b  0成立。

（2）显然每个非零整数a都有约数 1， a，称这四个数为a的平凡约数（平凡因子），a的除1， a外的约数称为非平凡约数（或真因数）。

（3）能被2整除的整数称为偶数，不能被2整除的整数称为奇数。

若整数a  0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

2.整除的性质

定理1.1.1 设a,b,c,m,n是整数,下面的结论成立：

(ⅰ) ab，bc  ac（整除的传递性）；

(ⅱ) ab  ab，即a b  |a||b|;

ma, nb

 mnab；

(ⅲ) 若ba，且bc  b(ka+lc)（其中k, l是任意的整数）；

一般地，若mai，i = 1, 2, , n  m（q1a1  q2a2    qnan），

此处qi（i = 1, 2, , n）是任意的整数；

(ⅳ) ba  bcac，此处c是任意非零的整数；

(ⅴ) 若ba，a  0  |b|  |a|；若ba，且|a| < |b|  a = 0；

若ba，且ab，a>0, b>0, 则a=b.

证明 (ⅰ)由整除定义及a|b，b|c,知: 存在两个整数k1,k2使得:

bak1,cbk2, 因此c(k1k2)a, 由于k1k2是整数, 故

a|c.

(ⅱ) — (ⅳ)的结论类似可证. 证毕.

注 为了证明“b|a”，最为基本的手法是将a分解为b与某个整数之积，即abc，其中c是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如：

（Ⅰ）若n是正整数，则

anbn(ab)(an1an2babn2bn1);

（Ⅱ）若n是正奇数，则在上式中以（b）代换b得:

anbn(ab)(an1an2babn2bn1).

例1 证明十进制整数1001能被十进制整数1001整除.

50个02

证明 由分解因式公式(Ⅱ),有

17100110511（103）1

50个015（1031）[(103)16（103）1031],

所以,

10311001能整除1001.证毕

50个0想一想:此题目能变形推广吗?推广后的一般形式是什么?

例2 若n是正奇数，则8（n2  1）.

证明 设n = 2k  1，(kZ)，则 n2  1= (2k  1)2  1 = 4k (k  1).

由于k和k  1中必有一个是偶数，所以8（n2  1）. 证毕

注 由此得到一个重要且常用的结论：

“任何奇数的平方与1的差都能被8整除”.

诸如此类的还有，“任何整数的平方被4除的余数为0或1，被3除的余数为0或1; 任何整数的立方被9除的余数为 0，1或8”等，解题后可及时总结归纳, 并灵活运用这些性质.

例3 设n是奇数，则16(n4  4n2  11).

解 因为 n4  4n2  11 = (n2

 1)(n2  5)  16.

由于n是奇数,有8(n2

 1)，且2(n2  5),

故16(n2

 1)(n2  5).

从而16(n2

 1)(n2  5)+16,

即16(n4  4n2  11).

例4 设m,n为正整数，且mn0, 证明:

(21)|(2证明 由于mn0, 故mn10. 于是:2(2在公式(Ⅰ)中，令

a22,

b1，则:

n12n2m1).

2m2n12mn1)

3

21(2(22n12m2n12mn1)1(22n12mn121)[(22n12mn11))22n11]

所以

(2又

22n11)|(21),

2m2n11(21)(21),

2n2n12n2n因此

(21)|(21).

2n2mnm由定理1.1.1中 (ⅰ),即整除的传递性知：(21)|(21). 证毕．

注1 在此例中，直接证明“(221)|(221)”不易入手，因此尝试选择适当的“中间量（21）”，使之满足定理1.1.1中 (ⅰ)的条件，再利用整除的传递性导出所要的结论.

注2 在此例中，形如“Fn221(nN)”的数称为费马数.

当mn0时, 费马数满足:

Fn|(Fm2)，即存在整数t，使得Fm2tFn.

例5 设正整数n的十进制表示为:

n2n1

naka1a0(0ai9,0ik,ak0)，

且S(n)akak1a1a0，证明：9|n的充要条件是9|S(n).

k证明：由于nak10

S(n)akak1a110a0,

a1a0，

ai(10i1)a1(101),

nS(n)ak(10k1)i对于所有的0ik, 有9|(101),

由整除的性质知上式右端k个加项中每一项都是9的倍数，

由定理1.1.1之(ⅲ)知它们的和也被9整除，

即9|(nS(n)), 从而

9|n9|S(n). 证毕.

4

注 两个十进制正整数,其中一个被另一个正整数整除的条件，称为“整除的数字特征”.例5得出十进制正整数n被9整除的数字特征是:“9整除n的各位数字之和”.下面例题6得出十进制正整数n被11整除的数字特征是:“11整除n的各位数字的正负交错之和”.

例6 设正整数n的十进制表示为naka1a0(0ai9,ak0)，n的个位为起始数字的正负交错和

T(n)a0a1证明：“11|n”的充分必要条件是“11|T(n)”.

kna10a110a0, 证明 由于

k(1)kak，

T(n)a0a1(1)kak，

ai(10i(1)i)a1(101)

nT(n)ak(10k(1)k)ii10(1)99当i为偶数时，

99 ，

其中有偶数个9，显然它是11的倍数；

iii10(1)101(101)s11s(sz)， 当i为奇数时，它也是11的倍数,

ii11|(10(1)),(0ik). 即11|(nT(n))成立. 故总有从而11|n11|T(n).

习题1.1

1．设n是整数，则3|n(n1)(2n1).

2. 设正整数n的十进制表示为naka1a0(0ai9,0ik,ak0)，n的个位为起始数字的正、负交错的和

T(n)a0a1(1)kak，证明：“11|n”的充分必要条件是“11|T(n)”.

5

2nn3. 若10个男孩和个女孩共买了8n2本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?

24．证明一个整数a若不能被2整除，也不能被3整除, 则a23必能被24整除.

5. 已知整数m,n,p,q适合: (m  p) (mn  pq)，证明:

(m  p)(mq  np).

1.1.2 带余数除法

对任意两个整数a,b(b0)，a未必能被b整除. 为了能在整数范围内研究除法，引入整数的除法算法——带余数除法，它是初等数论证明中最重要、最基本、最常用的工具. 本节中，我们将介绍带余数除法及其简单应用. 我们约定, 以Z表示所有整数的集合，N表示所有正整数的集合. 除特别声明外，在涉及到带余数除法时总假定除数是正整数.

1. 带余数除法

定理1.2.1 (带余数除法) 设a与b是两个整数，b>0，则存在惟一的一对整数q和r，使得:

a = bq  r，0  r

若a = bq  r (0  r < b), 则b|a的充分必要条件是r0.

证明: 存在性

作整数序列:

,3b,2b,b,0,b,2b,3b,

则a必在上述序列的某两项之间,即存在一个整数q,使得

qba(q1)b

成立. 令aqbr,则aqbr,而0rb.

6

惟一性 假设q1,r1是满足(2) 的两个整数，即

abq1r1(0r1b),

则

abqrbq1r1

于是

b(qq1)r1rb|qq1||r1r|

(3)

由上式推出:

b|r1r|,

由于

0r1,rb0|r1r|b

r1r，代入式(3)得

qq1，惟一性得证.

若abqr(0rb)，则

b|ab|r,

因此必有|r1r|0,即

又

0rb, 则

b|rr0.故b|ar0. 证毕

注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.

定义：在式a = bq  r（0  r < b）中，q称为a被b除的不完全商，r称为a被b除的余数, 也称为最小非负剩余.

带余数除法是一个重要的工具，数论的许多基本性质都是建立在带余数除法基础之上的.

例1 当

b15,a225时

r015,q17; 有

22515170,当

b15,a417时

0r1215,q27; 有

417152712,0r915,q6;

r60,q5; 且有

8115(5)(6), 此处r{0,1,2,,151}，这时的余数r不是最小非负剩余。

7

当

b15,a81时,

有

8115(6)9,

2.带余数除法的变形

推论 若a,b,d(b0)是整数, 则存在惟一一对整数q和r满足:

abqr(dr|b|d)

证明 考虑整数ad及|b|，由带余数除法知，存在惟一的整数对q',r'，

adbq'r'，0r'|b|，

a|b|q(r'd)(dr'd|b|d)

令rr'd, 则

abqr,

(dr|b|d).

由于q'及r'的惟一性得知q及r是惟一性的. 证毕.

使得

注 这个推论是带余数除法的一种更为灵活的形式.

|b||b|1dd2|b2|b例如: 当时,取; 当时,取, 则

22|b||b|r,2|b,22abqr,

其中|b|1

|b|1r,2|b.22此形式可以统一为：

|b||b|rabqr,

其中.

22这种带余数除法中的余数r叫做绝对最小余数.

注 这里余数满足的不等式中第二个不等号是严格小于号.

例2 设a25,b13,(除数为奇数)

则

2513112(0r1213) (最小非负剩余)

8

对于最小非负剩余而言,存在唯一的整数对

q1,r12;

又

25132(1)(6r16) (绝对最小剩余)

对于绝对最小剩余而言, 存在唯一的整数对

q2,r1.

例3 设a63,b14,(除数为偶数)

(0r714) (最小非负余数)

对于最小非负剩余而言,存在唯一的一对整数q4,r7;

63145(7)则

631447(7r77) (绝对最小余数)

|14||14|r，则存在唯一的整数22对于绝对最小余数而言，若取对：

q5,r7；

|14||14|r对于绝对最小余数而言，若取

22，

由于631447145(7)，

则存在两组整数对：q5,r7与q4,r7.（参见课本P4习题4的结论）

|b||b|r因而, 若取

,

则存在唯一的整数对q及r, 使得22abqr.

注: 使用绝对最小余数可以相对简化计算量.

若a = bq  r (0  r < b), 则b|a的充分必要条件是r0.

9

注:这个结论揭示了整除与带余数除法之间的联系,因此，整除问题往往可以化归为带余数除法问题来解决.

例1（P4习题3）设a1, a2, , an为不全为零的n个整数，以y0表示集合

A = {y|y = a1x1    anxn，（xiZ，1  i  n）}

中的最小正整数，则对于任何yA，有 y0y ；

特别地，有 y0ai

，(1  i  n).

证明 设y0 = a1x1    anxnA，对于y = a1x1    anxnA，

由带余数除法存在整数q, rZ，使得

y = qy0  r

(0 r< y0

).

因此 r = y

 qy0 = a1(x1  qx1)    an(xn  qxn)A.

如果r  0，那么必有0 < r

< y0，所以r是A中比y0还小的正整数，

这与y0的定义矛盾. 所以r = 0，即y0y.

显然，ai0a11ai0anA（1  i  n），

所以，由已证结论得：y0ai，（1  i  n），即ai(1in)是y0的倍数。证毕.

注 此类题目证明方法具有一般性：将整除问题化归为带余数除法问题，通常针对所给“最小正整数”的概念进行反证，证明余数r0..

例2 任意给出的五个整数中，必有其中三个数之和能被3整除.

证明 设这五个整数分别为：ai(i1,2,3,4,5).

令ai = 3qi  ri，0  ri < 3，即ri分别考虑以下两种情形：

0,1,2;i1,2,3,4,5.

10

(ⅰ)

若在余数r1, r2, , r5中0，1，2都出现，

不妨设r1 = 0，r2 = 1，r3 = 2

则

a1a2a3(3q13q23q3)(r1r2r3)

3(q1q2q3)(012)3(q1q2q3)3

故

3|(a1a2a3)

(ⅱ)

若在余数r1, r2, , r5中数0，1，2至少有一个不出现 ，

根据抽屉原理，5个整数只取两个不同的数值，至少有三个余数ri应取相同的一个数值，不妨设r1 = r2 = r3 = r，r{0,1,2}，此时

a1a2a33(q1q2q3)(r1r2r3)

3(q1q2q3)3r

故

3|(a1a2a3)

综合(ⅰ) 、(ⅱ)可知, 所证结论成立.

证毕.

..Dirichlet原理:

注 例2涉及的抽屉原理也称为PG将m个元素放入n个(mn)抽屉之中，则在其中一个抽屉里至m1]1个元素. 少含有[n值得注意的是,利用带余数除法得到的余数进行分类来构造抽屉，这是初等数论解(证)题中常用的手法（蕴含分类的数学思想方法）.

例3 设r是正奇数，证明对任意的正整数n，有

(n2)|[1r2r(n1)rnr]

证明 当n1时，结论显然成立.

rrrrS[12(n1)n], 则 现设n2，令2Sr[1r2r(n1)rnr][nr(n1)r2r1r]

11

2[2rnr][ir(n2i)r][nr2r]

因为r为奇数，上式等号的右边除第一项外，其余的每一加项：

ir(n2i)r[i(n2i)]m(n2)m(mZ)

因此

2S2(n2)Q1, 其中Q1是整数.

|2 显然,2S被n2除得的余数是2, 由于n22, 所以

(n2)|S. 证毕.

(n2)|2S, 从而(n2)注 例3的证明过程中, 关键在于将2S的表达式中满足“其和能被n2整除”的两项配成一对，这种“配对”思想方法，就是将整体对故

象中满足某种特性的对象组合配对, 再利用配对后的特性解决原问题,

它是数论解(证)题中常用的一种手法, 后续章节中也经常涉及配对思想方法.

例4 设a0(aN)，证明a个连续整数有且仅有一个能被a整除.

证明 首先证明a个连续整数有一个能被a整除

设a个连续整数为:m,m1,,ma1,

令

maqr,0ra.

若r0, 则a|m.

若r0, 则1ra

1ara1.

由于mraqa|(mr), 从而有

a|[(mr)a],

即

a|[m(ar)]，且

m(ar){m1,,m(a1)}

所以a个连续整数有一个能被a整除。

再证明a个连续整数中只有一个数被a整除。

设a|(mi),a|(mj),(0ija1),则

a|ij|

12

又因为0|ij|a，故必有

|ij|0,即ij。

因而a个连续整数有且仅有一个数能被a整除. 证毕.

注 “a个连续整数中有且仅有一个能被a整除”这是初等数论证明问题常用的结论.

进一步可以证明 “a个连续整数的乘积一定能被a!整除”.

例5 证明：任意的整数n，f(n) = 3n5  5n3  7n能被15整除。

证明 对于任意的整数n，欲证结论即：

3|f(n)3n55n37n,53

15|f(n)3n5n7n

535|f(n)3n5n7n.f(n)3n55n37n3(n52n32n)(nn3)3(n52n32n)n(n1)(n1)3|f(n)

f(n)3n55n37n5(n5n3n)2(nn5)5(n5n3n)2n(1n4)5(n52n32n)2n(n1)(n1)(n21)5(n2n2n)2n(n1)(n1)(n45)532

5(n52n32n)2(n2)(n1)n(n1)(n2)10n(n1)(n1)上式第二项是5个连续整数的积，它能被5整除，又其余两项也都都能被5整除,

5|f(n). 综上可知

15|f(n).

注 本题用到数论中的常用结论：“a个连续整数中有且仅有一个能被a整除”;

333例6若a,b,c为整数，且abc是24的倍数，求证：

13

120|[(a5b5c5)4(abc)].

534222a5a4aa(a5a4)a(a1)(a4) 证明 由于(a2)(a1)a(a1)(a2),

它是五个连续整数之积，因而是5!120的倍数.

5353c5c4c 都是120的倍数.

b5b4b同理可得 ，555333 因此，(abc)4(abc)5(abc)是120的倍数.

333333(abc)(abc)是120的倍数， 又已知 是24的倍数，故5

555(abc)4(abc)是120的倍数. 所以

(注 本题利用结论:a个连续整数的乘积一定能被a!整除).

习题1. 2

1. 设3( a2  b2)，证明：3a且3b ,其中a,b是任意整数.

|a,则a21与a21有且仅有一个是5的倍数. 2. 对于整数a,若53. 证明：对于任意给定的n个整数，必可以从中找出若干个数作和，使得这个和能被n整除.

4. 证明：对于任何整数n，m，等式n2  (n  1)2 = m2  2不可能成立.

5. 设a1, a2, , an是整数，且a1  a2    an = 0，a1a2an = n，证明n必是4的倍数.

2006M579116. 设，求证：8|M. 将此题进行推广并证明你的结论.

4.习题选讲

14

例6

设a，b，x，y∈Z，k，m∈Z+，且

a = a1m  r1，0  r1 < m，

b = b1m  r2，0  r2 < m，

则ax  by被m除的余数与r1x  r2y被m除的余数相同；

ab被m除的余数与r1r2被m除的余数相同；

特别地，ak被m除的余数与r1k被m除的余数相同.

解 因为： a = a1m  r1，0  r1 < m，

b = b1m  r2，0  r2 < m，

所以ax  by = (a1m  r1)x  (b1m  r2)y = (a1x  b1y)m （r1x  r2y）

由此可知，若r1x  r2y被m除的余数是r，则ax  by被m除的余数其余数也是r.

同样方法可以证明其余结论.

例7 证明：若a被9除的余数是3，4，5或6，则方程

x3  y3 = a 没有整数解。

证明 对任意的整数x，y，记

x = 3q1  r1，y = 3q2  r2，0  r1, r2 < 3.

则存在Q1, R1, Q2, R2Z，使得

x3 = 9Q1  R1，y3 = 9Q2  R2

，

由例5可知R1和R2被9除的余数分别与r13和r23被9除的余数相同,

由于r10,1,2, 故 R1 = 0，1或8; 同理, R2 = 0，1或8. (*)

因此 x3  y3 = 9(Q1  Q2) ( R1  R2).

又由例5及式(*)可知，R1  R2被9除的余数只可能是0，1，2，7或8，

所以，x3  y3不可能等于a

, 否则,将与已知条件矛盾.

即

x3  y3 = a 没有整数解。

例8

设a0, a1, , anZ，f(x) = anxn    a1x  a0

，若f(0)与f(1)15

都不是3的倍数，证明：若方程f(x) = 0有整数解，则

3f(1) = a0

 a1  a2

   (1)nan

.

证明 对任何整数x，都有 x = 3q  r，(r = 0,1,2，qZ).

(ⅰ) 若r = 0，即x = 3q，qZ，则

f(x) = f(3q) = an(3q)n    a1(3q)  a0 = 3Q1  a0 = 3Q1  f(0)，

其中Q1Z，由于f(0)不是3的倍数，所以f(x)  0；

(ⅱ) 若r = 1，即x = 3q  1，qZ，则

f(x) = f(3q  1) = an(3q  1)n    a1(3q  1)  a0

= 3Q2  an    a1  a0 = 3Q2  f(1)，其中Q2Z.

由于f(1)不是3的倍数，所以f(x)  0.

因此若f(x) = 0有整数解x，则x必是形如:

x = 3q  2 = 3q

 1，(q

Z)，

于是 0 = f(x) = f(3q



 1) = an(3q



 1)n    a1(3q



 1)  a0

= 3Q3  a0

 a1  a2

   ( 1)nan = 3Q3  f(1)， 其中Q3Z.

所以 3f(1) = a0

 a1  a2

   (1)nan

.

m|(2n1).

例9 设m,n为正整数，m2，证明：(21)证明 对正整数m,n分以下三种情形讨论.

nn(ⅰ) 当nm时，21(21)2，由于nm,m2，

n|2, 故(2n1)|(2n1). 所以

2n12，因而(21)nm1(ⅱ) 当nm时，有nm1,有

2121

m1m注意到m2，于是2m122m12m12m，即2121

综合上述两式得：

2n12m112m1，

m|(2n1)； 故

(21)16

(ⅲ) 当nm时，设nmqr,(0rm,qN),

nmqr1(2mq1)2r(2r1), 由于

212mmq由于

(21)|(21).

nmqm当r0时,

21(21)2(21)M2,(MZ),

|(2n1);

|2, 从而

(2m1)由于m2,故2m12, 因此(2m1)|(2r1). 当0rm时, 由(ⅱ)知：(2m1)m|(2n1) 证毕. 故

(21)注

此例题解答过程中用到分类的思想方法，以及带余数的除法。

习题

17

2024年3月9日发(作者：赧易)

主要内容:

1．1.整除的概念

1．2.带余数除法

1．3.最大公因数的理论与性质

1．4.最小公倍数的理论与性质

1．5.辗转相除法

1．6.素数与合数

1．7.算术基本定理

1．8.高斯函数[x]与{x}及其应用

1.1.1 整除的定义与性质

1.整除的定义

定义 设a，b∈Z，b  0，若存在整数c，使得a = bc成立，则称a被b整除（或b整除a），并称a是b的倍数，b是a的约数（因数或除数），记为ba；

|a。如果不存在整数c使得a = bc成立，则称a不能被b整除，记为b

在整除的定义中应特别注意：

（1）0不整除任何整数（即0不能作除数），但任何非零数整除0；

在记号“ba”中蕴含着b  0成立。

（2）显然每个非零整数a都有约数 1， a，称这四个数为a的平凡约数（平凡因子），a的除1， a外的约数称为非平凡约数（或真因数）。

（3）能被2整除的整数称为偶数，不能被2整除的整数称为奇数。

若整数a  0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

2.整除的性质

定理1.1.1 设a,b,c,m,n是整数,下面的结论成立：

(ⅰ) ab，bc  ac（整除的传递性）；

(ⅱ) ab  ab，即a b  |a||b|;

ma, nb

 mnab；

(ⅲ) 若ba，且bc  b(ka+lc)（其中k, l是任意的整数）；

一般地，若mai，i = 1, 2, , n  m（q1a1  q2a2    qnan），

此处qi（i = 1, 2, , n）是任意的整数；

(ⅳ) ba  bcac，此处c是任意非零的整数；

(ⅴ) 若ba，a  0  |b|  |a|；若ba，且|a| < |b|  a = 0；

若ba，且ab，a>0, b>0, 则a=b.

证明 (ⅰ)由整除定义及a|b，b|c,知: 存在两个整数k1,k2使得:

bak1,cbk2, 因此c(k1k2)a, 由于k1k2是整数, 故

a|c.

(ⅱ) — (ⅳ)的结论类似可证. 证毕.

注 为了证明“b|a”，最为基本的手法是将a分解为b与某个整数之积，即abc，其中c是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如：

（Ⅰ）若n是正整数，则

anbn(ab)(an1an2babn2bn1);

（Ⅱ）若n是正奇数，则在上式中以（b）代换b得:

anbn(ab)(an1an2babn2bn1).

例1 证明十进制整数1001能被十进制整数1001整除.

50个02

证明 由分解因式公式(Ⅱ),有

17100110511（103）1

50个015（1031）[(103)16（103）1031],

所以,

10311001能整除1001.证毕

50个0想一想:此题目能变形推广吗?推广后的一般形式是什么?

例2 若n是正奇数，则8（n2  1）.

证明 设n = 2k  1，(kZ)，则 n2  1= (2k  1)2  1 = 4k (k  1).

由于k和k  1中必有一个是偶数，所以8（n2  1）. 证毕

注 由此得到一个重要且常用的结论：

“任何奇数的平方与1的差都能被8整除”.

诸如此类的还有，“任何整数的平方被4除的余数为0或1，被3除的余数为0或1; 任何整数的立方被9除的余数为 0，1或8”等，解题后可及时总结归纳, 并灵活运用这些性质.

例3 设n是奇数，则16(n4  4n2  11).

解 因为 n4  4n2  11 = (n2

 1)(n2  5)  16.

由于n是奇数,有8(n2

 1)，且2(n2  5),

故16(n2

 1)(n2  5).

从而16(n2

 1)(n2  5)+16,

即16(n4  4n2  11).

例4 设m,n为正整数，且mn0, 证明:

(21)|(2证明 由于mn0, 故mn10. 于是:2(2在公式(Ⅰ)中，令

a22,

b1，则:

n12n2m1).

2m2n12mn1)

3

21(2(22n12m2n12mn1)1(22n12mn121)[(22n12mn11))22n11]

所以

(2又

22n11)|(21),

2m2n11(21)(21),

2n2n12n2n因此

(21)|(21).

2n2mnm由定理1.1.1中 (ⅰ),即整除的传递性知：(21)|(21). 证毕．

注1 在此例中，直接证明“(221)|(221)”不易入手，因此尝试选择适当的“中间量（21）”，使之满足定理1.1.1中 (ⅰ)的条件，再利用整除的传递性导出所要的结论.

注2 在此例中，形如“Fn221(nN)”的数称为费马数.

当mn0时, 费马数满足:

Fn|(Fm2)，即存在整数t，使得Fm2tFn.

例5 设正整数n的十进制表示为:

n2n1

naka1a0(0ai9,0ik,ak0)，

且S(n)akak1a1a0，证明：9|n的充要条件是9|S(n).

k证明：由于nak10

S(n)akak1a110a0,

a1a0，

ai(10i1)a1(101),

nS(n)ak(10k1)i对于所有的0ik, 有9|(101),

由整除的性质知上式右端k个加项中每一项都是9的倍数，

由定理1.1.1之(ⅲ)知它们的和也被9整除，

即9|(nS(n)), 从而

9|n9|S(n). 证毕.

4

注 两个十进制正整数,其中一个被另一个正整数整除的条件，称为“整除的数字特征”.例5得出十进制正整数n被9整除的数字特征是:“9整除n的各位数字之和”.下面例题6得出十进制正整数n被11整除的数字特征是:“11整除n的各位数字的正负交错之和”.

例6 设正整数n的十进制表示为naka1a0(0ai9,ak0)，n的个位为起始数字的正负交错和

T(n)a0a1证明：“11|n”的充分必要条件是“11|T(n)”.

kna10a110a0, 证明 由于

k(1)kak，

T(n)a0a1(1)kak，

ai(10i(1)i)a1(101)

nT(n)ak(10k(1)k)ii10(1)99当i为偶数时，

99 ，

其中有偶数个9，显然它是11的倍数；

iii10(1)101(101)s11s(sz)， 当i为奇数时，它也是11的倍数,

ii11|(10(1)),(0ik). 即11|(nT(n))成立. 故总有从而11|n11|T(n).

习题1.1

1．设n是整数，则3|n(n1)(2n1).

2. 设正整数n的十进制表示为naka1a0(0ai9,0ik,ak0)，n的个位为起始数字的正、负交错的和

T(n)a0a1(1)kak，证明：“11|n”的充分必要条件是“11|T(n)”.

5

2nn3. 若10个男孩和个女孩共买了8n2本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?

24．证明一个整数a若不能被2整除，也不能被3整除, 则a23必能被24整除.

5. 已知整数m,n,p,q适合: (m  p) (mn  pq)，证明:

(m  p)(mq  np).

1.1.2 带余数除法

对任意两个整数a,b(b0)，a未必能被b整除. 为了能在整数范围内研究除法，引入整数的除法算法——带余数除法，它是初等数论证明中最重要、最基本、最常用的工具. 本节中，我们将介绍带余数除法及其简单应用. 我们约定, 以Z表示所有整数的集合，N表示所有正整数的集合. 除特别声明外，在涉及到带余数除法时总假定除数是正整数.

1. 带余数除法

定理1.2.1 (带余数除法) 设a与b是两个整数，b>0，则存在惟一的一对整数q和r，使得:

a = bq  r，0  r

若a = bq  r (0  r < b), 则b|a的充分必要条件是r0.

证明: 存在性

作整数序列:

,3b,2b,b,0,b,2b,3b,

则a必在上述序列的某两项之间,即存在一个整数q,使得

qba(q1)b

成立. 令aqbr,则aqbr,而0rb.

6

惟一性 假设q1,r1是满足(2) 的两个整数，即

abq1r1(0r1b),

则

abqrbq1r1

于是

b(qq1)r1rb|qq1||r1r|

(3)

由上式推出:

b|r1r|,

由于

0r1,rb0|r1r|b

r1r，代入式(3)得

qq1，惟一性得证.

若abqr(0rb)，则

b|ab|r,

因此必有|r1r|0,即

又

0rb, 则

b|rr0.故b|ar0. 证毕

注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.

定义：在式a = bq  r（0  r < b）中，q称为a被b除的不完全商，r称为a被b除的余数, 也称为最小非负剩余.

带余数除法是一个重要的工具，数论的许多基本性质都是建立在带余数除法基础之上的.

例1 当

b15,a225时

r015,q17; 有

22515170,当

b15,a417时

0r1215,q27; 有

417152712,0r915,q6;

r60,q5; 且有

8115(5)(6), 此处r{0,1,2,,151}，这时的余数r不是最小非负剩余。

7

当

b15,a81时,

有

8115(6)9,

2.带余数除法的变形

推论 若a,b,d(b0)是整数, 则存在惟一一对整数q和r满足:

abqr(dr|b|d)

证明 考虑整数ad及|b|，由带余数除法知，存在惟一的整数对q',r'，

adbq'r'，0r'|b|，

a|b|q(r'd)(dr'd|b|d)

令rr'd, 则

abqr,

(dr|b|d).

由于q'及r'的惟一性得知q及r是惟一性的. 证毕.

使得

注 这个推论是带余数除法的一种更为灵活的形式.

|b||b|1dd2|b2|b例如: 当时,取; 当时,取, 则

22|b||b|r,2|b,22abqr,

其中|b|1

|b|1r,2|b.22此形式可以统一为：

|b||b|rabqr,

其中.

22这种带余数除法中的余数r叫做绝对最小余数.

注 这里余数满足的不等式中第二个不等号是严格小于号.

例2 设a25,b13,(除数为奇数)

则

2513112(0r1213) (最小非负剩余)

8

对于最小非负剩余而言,存在唯一的整数对

q1,r12;

又

25132(1)(6r16) (绝对最小剩余)

对于绝对最小剩余而言, 存在唯一的整数对

q2,r1.

例3 设a63,b14,(除数为偶数)

(0r714) (最小非负余数)

对于最小非负剩余而言,存在唯一的一对整数q4,r7;

63145(7)则

631447(7r77) (绝对最小余数)

|14||14|r，则存在唯一的整数22对于绝对最小余数而言，若取对：

q5,r7；

|14||14|r对于绝对最小余数而言，若取

22，

由于631447145(7)，

则存在两组整数对：q5,r7与q4,r7.（参见课本P4习题4的结论）

|b||b|r因而, 若取

,

则存在唯一的整数对q及r, 使得22abqr.

注: 使用绝对最小余数可以相对简化计算量.

若a = bq  r (0  r < b), 则b|a的充分必要条件是r0.

9

注:这个结论揭示了整除与带余数除法之间的联系,因此，整除问题往往可以化归为带余数除法问题来解决.

例1（P4习题3）设a1, a2, , an为不全为零的n个整数，以y0表示集合

A = {y|y = a1x1    anxn，（xiZ，1  i  n）}

中的最小正整数，则对于任何yA，有 y0y ；

特别地，有 y0ai

，(1  i  n).

证明 设y0 = a1x1    anxnA，对于y = a1x1    anxnA，

由带余数除法存在整数q, rZ，使得

y = qy0  r

(0 r< y0

).

因此 r = y

 qy0 = a1(x1  qx1)    an(xn  qxn)A.

如果r  0，那么必有0 < r

< y0，所以r是A中比y0还小的正整数，

这与y0的定义矛盾. 所以r = 0，即y0y.

显然，ai0a11ai0anA（1  i  n），

所以，由已证结论得：y0ai，（1  i  n），即ai(1in)是y0的倍数。证毕.

注 此类题目证明方法具有一般性：将整除问题化归为带余数除法问题，通常针对所给“最小正整数”的概念进行反证，证明余数r0..

例2 任意给出的五个整数中，必有其中三个数之和能被3整除.

证明 设这五个整数分别为：ai(i1,2,3,4,5).

令ai = 3qi  ri，0  ri < 3，即ri分别考虑以下两种情形：

0,1,2;i1,2,3,4,5.

10

(ⅰ)

若在余数r1, r2, , r5中0，1，2都出现，

不妨设r1 = 0，r2 = 1，r3 = 2

则

a1a2a3(3q13q23q3)(r1r2r3)

3(q1q2q3)(012)3(q1q2q3)3

故

3|(a1a2a3)

(ⅱ)

若在余数r1, r2, , r5中数0，1，2至少有一个不出现 ，

根据抽屉原理，5个整数只取两个不同的数值，至少有三个余数ri应取相同的一个数值，不妨设r1 = r2 = r3 = r，r{0,1,2}，此时

a1a2a33(q1q2q3)(r1r2r3)

3(q1q2q3)3r

故

3|(a1a2a3)

综合(ⅰ) 、(ⅱ)可知, 所证结论成立.

证毕.

..Dirichlet原理:

注 例2涉及的抽屉原理也称为PG将m个元素放入n个(mn)抽屉之中，则在其中一个抽屉里至m1]1个元素. 少含有[n值得注意的是,利用带余数除法得到的余数进行分类来构造抽屉，这是初等数论解(证)题中常用的手法（蕴含分类的数学思想方法）.

例3 设r是正奇数，证明对任意的正整数n，有

(n2)|[1r2r(n1)rnr]

证明 当n1时，结论显然成立.

rrrrS[12(n1)n], 则 现设n2，令2Sr[1r2r(n1)rnr][nr(n1)r2r1r]

11

2[2rnr][ir(n2i)r][nr2r]

因为r为奇数，上式等号的右边除第一项外，其余的每一加项：

ir(n2i)r[i(n2i)]m(n2)m(mZ)

因此

2S2(n2)Q1, 其中Q1是整数.

|2 显然,2S被n2除得的余数是2, 由于n22, 所以

(n2)|S. 证毕.

(n2)|2S, 从而(n2)注 例3的证明过程中, 关键在于将2S的表达式中满足“其和能被n2整除”的两项配成一对，这种“配对”思想方法，就是将整体对故

象中满足某种特性的对象组合配对, 再利用配对后的特性解决原问题,

它是数论解(证)题中常用的一种手法, 后续章节中也经常涉及配对思想方法.

例4 设a0(aN)，证明a个连续整数有且仅有一个能被a整除.

证明 首先证明a个连续整数有一个能被a整除

设a个连续整数为:m,m1,,ma1,

令

maqr,0ra.

若r0, 则a|m.

若r0, 则1ra

1ara1.

由于mraqa|(mr), 从而有

a|[(mr)a],

即

a|[m(ar)]，且

m(ar){m1,,m(a1)}

所以a个连续整数有一个能被a整除。

再证明a个连续整数中只有一个数被a整除。

设a|(mi),a|(mj),(0ija1),则

a|ij|

12

又因为0|ij|a，故必有

|ij|0,即ij。

因而a个连续整数有且仅有一个数能被a整除. 证毕.

注 “a个连续整数中有且仅有一个能被a整除”这是初等数论证明问题常用的结论.

进一步可以证明 “a个连续整数的乘积一定能被a!整除”.

例5 证明：任意的整数n，f(n) = 3n5  5n3  7n能被15整除。

证明 对于任意的整数n，欲证结论即：

3|f(n)3n55n37n,53

15|f(n)3n5n7n

535|f(n)3n5n7n.f(n)3n55n37n3(n52n32n)(nn3)3(n52n32n)n(n1)(n1)3|f(n)

f(n)3n55n37n5(n5n3n)2(nn5)5(n5n3n)2n(1n4)5(n52n32n)2n(n1)(n1)(n21)5(n2n2n)2n(n1)(n1)(n45)532

5(n52n32n)2(n2)(n1)n(n1)(n2)10n(n1)(n1)上式第二项是5个连续整数的积，它能被5整除，又其余两项也都都能被5整除,

5|f(n). 综上可知

15|f(n).

注 本题用到数论中的常用结论：“a个连续整数中有且仅有一个能被a整除”;

333例6若a,b,c为整数，且abc是24的倍数，求证：

13

120|[(a5b5c5)4(abc)].

534222a5a4aa(a5a4)a(a1)(a4) 证明 由于(a2)(a1)a(a1)(a2),

它是五个连续整数之积，因而是5!120的倍数.

5353c5c4c 都是120的倍数.

b5b4b同理可得 ，555333 因此，(abc)4(abc)5(abc)是120的倍数.

333333(abc)(abc)是120的倍数， 又已知 是24的倍数，故5

555(abc)4(abc)是120的倍数. 所以

(注 本题利用结论:a个连续整数的乘积一定能被a!整除).

习题1. 2

1. 设3( a2  b2)，证明：3a且3b ,其中a,b是任意整数.

|a,则a21与a21有且仅有一个是5的倍数. 2. 对于整数a,若53. 证明：对于任意给定的n个整数，必可以从中找出若干个数作和，使得这个和能被n整除.

4. 证明：对于任何整数n，m，等式n2  (n  1)2 = m2  2不可能成立.

5. 设a1, a2, , an是整数，且a1  a2    an = 0，a1a2an = n，证明n必是4的倍数.

2006M579116. 设，求证：8|M. 将此题进行推广并证明你的结论.

4.习题选讲

14

例6

设a，b，x，y∈Z，k，m∈Z+，且

a = a1m  r1，0  r1 < m，

b = b1m  r2，0  r2 < m，

则ax  by被m除的余数与r1x  r2y被m除的余数相同；

ab被m除的余数与r1r2被m除的余数相同；

特别地，ak被m除的余数与r1k被m除的余数相同.

解 因为： a = a1m  r1，0  r1 < m，

b = b1m  r2，0  r2 < m，

所以ax  by = (a1m  r1)x  (b1m  r2)y = (a1x  b1y)m （r1x  r2y）

由此可知，若r1x  r2y被m除的余数是r，则ax  by被m除的余数其余数也是r.

同样方法可以证明其余结论.

例7 证明：若a被9除的余数是3，4，5或6，则方程

x3  y3 = a 没有整数解。

证明 对任意的整数x，y，记

x = 3q1  r1，y = 3q2  r2，0  r1, r2 < 3.

则存在Q1, R1, Q2, R2Z，使得

x3 = 9Q1  R1，y3 = 9Q2  R2

，

由例5可知R1和R2被9除的余数分别与r13和r23被9除的余数相同,

由于r10,1,2, 故 R1 = 0，1或8; 同理, R2 = 0，1或8. (*)

因此 x3  y3 = 9(Q1  Q2) ( R1  R2).

又由例5及式(*)可知，R1  R2被9除的余数只可能是0，1，2，7或8，

所以，x3  y3不可能等于a

, 否则,将与已知条件矛盾.

即

x3  y3 = a 没有整数解。

例8

设a0, a1, , anZ，f(x) = anxn    a1x  a0

，若f(0)与f(1)15

都不是3的倍数，证明：若方程f(x) = 0有整数解，则

3f(1) = a0

 a1  a2

   (1)nan

.

证明 对任何整数x，都有 x = 3q  r，(r = 0,1,2，qZ).

(ⅰ) 若r = 0，即x = 3q，qZ，则

f(x) = f(3q) = an(3q)n    a1(3q)  a0 = 3Q1  a0 = 3Q1  f(0)，

其中Q1Z，由于f(0)不是3的倍数，所以f(x)  0；

(ⅱ) 若r = 1，即x = 3q  1，qZ，则

f(x) = f(3q  1) = an(3q  1)n    a1(3q  1)  a0

= 3Q2  an    a1  a0 = 3Q2  f(1)，其中Q2Z.

由于f(1)不是3的倍数，所以f(x)  0.

因此若f(x) = 0有整数解x，则x必是形如:

x = 3q  2 = 3q

 1，(q

Z)，

于是 0 = f(x) = f(3q



 1) = an(3q



 1)n    a1(3q



 1)  a0

= 3Q3  a0

 a1  a2

   ( 1)nan = 3Q3  f(1)， 其中Q3Z.

所以 3f(1) = a0

 a1  a2

   (1)nan

.

m|(2n1).

例9 设m,n为正整数，m2，证明：(21)证明 对正整数m,n分以下三种情形讨论.

nn(ⅰ) 当nm时，21(21)2，由于nm,m2，

n|2, 故(2n1)|(2n1). 所以

2n12，因而(21)nm1(ⅱ) 当nm时，有nm1,有

2121

m1m注意到m2，于是2m122m12m12m，即2121

综合上述两式得：

2n12m112m1，

m|(2n1)； 故

(21)16

(ⅲ) 当nm时，设nmqr,(0rm,qN),

nmqr1(2mq1)2r(2r1), 由于

212mmq由于

(21)|(21).

nmqm当r0时,

21(21)2(21)M2,(MZ),

|(2n1);

|2, 从而

(2m1)由于m2,故2m12, 因此(2m1)|(2r1). 当0rm时, 由(ⅱ)知：(2m1)m|(2n1) 证毕. 故

(21)注

此例题解答过程中用到分类的思想方法，以及带余数的除法。

习题

17