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的约数(因数或除数),记为ba;
|a。如果不存在整数c使得a = bc成立,则称a不能被b整除,记为b
在整除的定义中应特别注意:
(1)0不整除任何整数(即0不能作除数),但任何非零数整除0;
在记号“ba”中蕴含着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是整数,下面的结论成立:
(ⅰ) ab,bc ac(整除的传递性);
(ⅱ) ab ab,即a b |a||b|;
ma, nb
mnab;
(ⅲ) 若ba,且bc b(ka+lc)(其中k, l是任意的整数);
一般地,若mai,i = 1, 2, , n m(q1a1 q2a2 qnan),
此处qi(i = 1, 2, , n)是任意的整数;
(ⅳ) ba bcac,此处c是任意非零的整数;
(ⅴ) 若ba,a 0 |b| |a|;若ba,且|a| < |b| a = 0;
若ba,且ab,a>0, b>0, 则a=b.
证明 (ⅰ)由整除定义及a|b,b|c,知: 存在两个整数k1,k2使得:
bak1,cbk2, 因此c(k1k2)a, 由于k1k2是整数, 故
a|c.
(ⅱ) — (ⅳ)的结论类似可证. 证毕.
注 为了证明“b|a”,最为基本的手法是将a分解为b与某个整数之积,即abc,其中c是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如:
(Ⅰ)若n是正整数,则
anbn(ab)(an1an2babn2bn1);
(Ⅱ)若n是正奇数,则在上式中以(b)代换b得:
anbn(ab)(an1an2babn2bn1).
例1 证明十进制整数1001能被十进制整数1001整除.
50个02
证明 由分解因式公式(Ⅱ),有
17100110511(103)1
50个015(1031)[(103)16(103)1031],
所以,
10311001能整除1001.证毕
50个0想一想:此题目能变形推广吗?推广后的一般形式是什么?
例2 若n是正奇数,则8(n2 1).
证明 设n = 2k 1,(kZ),则 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为正整数,且mn0, 证明:
(21)|(2证明 由于mn0, 故mn10. 于是:2(2在公式(Ⅰ)中,令
a22,
b1,则:
n12n2m1).
2m2n12mn1)
3
21(2(22n12m2n12mn1)1(22n12mn121)[(22n12mn11))22n11]
所以
(2又
22n11)|(21),
2m2n11(21)(21),
2n2n12n2n因此
(21)|(21).
2n2mnm由定理1.1.1中 (ⅰ),即整除的传递性知:(21)|(21). 证毕.
注1 在此例中,直接证明“(221)|(221)”不易入手,因此尝试选择适当的“中间量(21)”,使之满足定理1.1.1中 (ⅰ)的条件,再利用整除的传递性导出所要的结论.
注2 在此例中,形如“Fn221(nN)”的数称为费马数.
当mn0时, 费马数满足:
Fn|(Fm2),即存在整数t,使得Fm2tFn.
例5 设正整数n的十进制表示为:
n2n1
naka1a0(0ai9,0ik,ak0),
且S(n)akak1a1a0,证明:9|n的充要条件是9|S(n).
k证明:由于nak10
S(n)akak1a110a0,
a1a0,
ai(10i1)a1(101),
nS(n)ak(10k1)i对于所有的0ik, 有9|(101),
由整除的性质知上式右端k个加项中每一项都是9的倍数,
由定理1.1.1之(ⅲ)知它们的和也被9整除,
即9|(nS(n)), 从而
9|n9|S(n). 证毕.
4
注 两个十进制正整数,其中一个被另一个正整数整除的条件,称为“整除的数字特征”.例5得出十进制正整数n被9整除的数字特征是:“9整除n的各位数字之和”.下面例题6得出十进制正整数n被11整除的数字特征是:“11整除n的各位数字的正负交错之和”.
例6 设正整数n的十进制表示为naka1a0(0ai9,ak0),n的个位为起始数字的正负交错和
T(n)a0a1证明:“11|n”的充分必要条件是“11|T(n)”.
kna10a110a0, 证明 由于
k(1)kak,
T(n)a0a1(1)kak,
ai(10i(1)i)a1(101)
nT(n)ak(10k(1)k)ii10(1)99当i为偶数时,
99 ,
其中有偶数个9,显然它是11的倍数;
iii10(1)101(101)s11s(sz), 当i为奇数时,它也是11的倍数,
ii11|(10(1)),(0ik). 即11|(nT(n))成立. 故总有从而11|n11|T(n).
习题1.1
1.设n是整数,则3|n(n1)(2n1).
2. 设正整数n的十进制表示为naka1a0(0ai9,0ik,ak0),n的个位为起始数字的正、负交错的和
T(n)a0a1(1)kak,证明:“11|n”的充分必要条件是“11|T(n)”.
5
2nn3. 若10个男孩和个女孩共买了8n2本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?
24.证明一个整数a若不能被2整除,也不能被3整除, 则a23必能被24整除.
5. 已知整数m,n,p,q适合: (m p) (mn pq),证明:
(m p)(mq np).
1.1.2 带余数除法
对任意两个整数a,b(b0),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的充分必要条件是r0.
证明: 存在性
作整数序列:
,3b,2b,b,0,b,2b,3b,
则a必在上述序列的某两项之间,即存在一个整数q,使得
qba(q1)b
成立. 令aqbr,则aqbr,而0rb.
6
惟一性 假设q1,r1是满足(2) 的两个整数,即
abq1r1(0r1b),
则
abqrbq1r1
于是
b(qq1)r1rb|qq1||r1r|
(3)
由上式推出:
b|r1r|,
由于
0r1,rb0|r1r|b
r1r,代入式(3)得
qq1,惟一性得证.
若abqr(0rb),则
b|ab|r,
因此必有|r1r|0,即
又
0rb, 则
b|rr0.故b|ar0. 证毕
注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.
定义:在式a = bq r(0 r < b)中,q称为a被b除的不完全商,r称为a被b除的余数, 也称为最小非负剩余.
带余数除法是一个重要的工具,数论的许多基本性质都是建立在带余数除法基础之上的.
例1 当
b15,a225时
r015,q17; 有
22515170,当
b15,a417时
0r1215,q27; 有
417152712,0r915,q6;
r60,q5; 且有
8115(5)(6), 此处r{0,1,2,,151},这时的余数r不是最小非负剩余。
7
当
b15,a81时,
有
8115(6)9,
2.带余数除法的变形
推论 若a,b,d(b0)是整数, 则存在惟一一对整数q和r满足:
abqr(dr|b|d)
证明 考虑整数ad及|b|,由带余数除法知,存在惟一的整数对q',r',
adbq'r',0r'|b|,
a|b|q(r'd)(dr'd|b|d)
令rr'd, 则
abqr,
(dr|b|d).
由于q'及r'的惟一性得知q及r是惟一性的. 证毕.
使得
注 这个推论是带余数除法的一种更为灵活的形式.
|b||b|1dd2|b2|b例如: 当时,取; 当时,取, 则
22|b||b|r,2|b,22abqr,
其中|b|1
|b|1r,2|b.22此形式可以统一为:
|b||b|rabqr,
其中.
22这种带余数除法中的余数r叫做绝对最小余数.
注 这里余数满足的不等式中第二个不等号是严格小于号.
例2 设a25,b13,(除数为奇数)
则
2513112(0r1213) (最小非负剩余)
8
对于最小非负剩余而言,存在唯一的整数对
q1,r12;
又
25132(1)(6r16) (绝对最小剩余)
对于绝对最小剩余而言, 存在唯一的整数对
q2,r1.
例3 设a63,b14,(除数为偶数)
(0r714) (最小非负余数)
对于最小非负剩余而言,存在唯一的一对整数q4,r7;
63145(7)则
631447(7r77) (绝对最小余数)
|14||14|r,则存在唯一的整数22对于绝对最小余数而言,若取对:
q5,r7;
|14||14|r对于绝对最小余数而言,若取
22,
由于631447145(7),
则存在两组整数对:q5,r7与q4,r7.(参见课本P4习题4的结论)
|b||b|r因而, 若取
,
则存在唯一的整数对q及r, 使得22abqr.
注: 使用绝对最小余数可以相对简化计算量.
若a = bq r (0 r < b), 则b|a的充分必要条件是r0.
9
注:这个结论揭示了整除与带余数除法之间的联系,因此,整除问题往往可以化归为带余数除法问题来解决.
例1(P4习题3)设a1, a2, , an为不全为零的n个整数,以y0表示集合
A = {y|y = a1x1 anxn,(xiZ,1 i n)}
中的最小正整数,则对于任何yA,有 y0y ;
特别地,有 y0ai
,(1 i n).
证明 设y0 = a1x1 anxnA,对于y = a1x1 anxnA,
由带余数除法存在整数q, rZ,使得
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,即y0y.
显然,ai0a11ai0anA(1 i n),
所以,由已证结论得:y0ai,(1 i n),即ai(1in)是y0的倍数。证毕.
注 此类题目证明方法具有一般性:将整除问题化归为带余数除法问题,通常针对所给“最小正整数”的概念进行反证,证明余数r0..
例2 任意给出的五个整数中,必有其中三个数之和能被3整除.
证明 设这五个整数分别为:ai(i1,2,3,4,5).
令ai = 3qi ri,0 ri < 3,即ri分别考虑以下两种情形:
0,1,2;i1,2,3,4,5.
10
(ⅰ)
若在余数r1, r2, , r5中0,1,2都出现,
不妨设r1 = 0,r2 = 1,r3 = 2
则
a1a2a3(3q13q23q3)(r1r2r3)
3(q1q2q3)(012)3(q1q2q3)3
故
3|(a1a2a3)
(ⅱ)
若在余数r1, r2, , r5中数0,1,2至少有一个不出现 ,
根据抽屉原理,5个整数只取两个不同的数值,至少有三个余数ri应取相同的一个数值,不妨设r1 = r2 = r3 = r,r{0,1,2},此时
a1a2a33(q1q2q3)(r1r2r3)
3(q1q2q3)3r
故
3|(a1a2a3)
综合(ⅰ) 、(ⅱ)可知, 所证结论成立.
证毕.
..Dirichlet原理:
注 例2涉及的抽屉原理也称为PG将m个元素放入n个(mn)抽屉之中,则在其中一个抽屉里至m1]1个元素. 少含有[n值得注意的是,利用带余数除法得到的余数进行分类来构造抽屉,这是初等数论解(证)题中常用的手法(蕴含分类的数学思想方法).
例3 设r是正奇数,证明对任意的正整数n,有
(n2)|[1r2r(n1)rnr]
证明 当n1时,结论显然成立.
rrrrS[12(n1)n], 则 现设n2,令2Sr[1r2r(n1)rnr][nr(n1)r2r1r]
11
2[2rnr][ir(n2i)r][nr2r]
因为r为奇数,上式等号的右边除第一项外,其余的每一加项:
ir(n2i)r[i(n2i)]m(n2)m(mZ)
因此
2S2(n2)Q1, 其中Q1是整数.
|2 显然,2S被n2除得的余数是2, 由于n22, 所以
(n2)|S. 证毕.
(n2)|2S, 从而(n2)注 例3的证明过程中, 关键在于将2S的表达式中满足“其和能被n2整除”的两项配成一对,这种“配对”思想方法,就是将整体对故
象中满足某种特性的对象组合配对, 再利用配对后的特性解决原问题,
它是数论解(证)题中常用的一种手法, 后续章节中也经常涉及配对思想方法.
例4 设a0(aN),证明a个连续整数有且仅有一个能被a整除.
证明 首先证明a个连续整数有一个能被a整除
设a个连续整数为:m,m1,,ma1,
令
maqr,0ra.
若r0, 则a|m.
若r0, 则1ra
1ara1.
由于mraqa|(mr), 从而有
a|[(mr)a],
即
a|[m(ar)],且
m(ar){m1,,m(a1)}
所以a个连续整数有一个能被a整除。
再证明a个连续整数中只有一个数被a整除。
设a|(mi),a|(mj),(0ija1),则
a|ij|
12
又因为0|ij|a,故必有
|ij|0,即ij。
因而a个连续整数有且仅有一个数能被a整除. 证毕.
注 “a个连续整数中有且仅有一个能被a整除”这是初等数论证明问题常用的结论.
进一步可以证明 “a个连续整数的乘积一定能被a!整除”.
例5 证明:任意的整数n,f(n) = 3n5 5n3 7n能被15整除。
证明 对于任意的整数n,欲证结论即:
3|f(n)3n55n37n,53
15|f(n)3n5n7n
535|f(n)3n5n7n.f(n)3n55n37n3(n52n32n)(nn3)3(n52n32n)n(n1)(n1)3|f(n)
f(n)3n55n37n5(n5n3n)2(nn5)5(n5n3n)2n(1n4)5(n52n32n)2n(n1)(n1)(n21)5(n2n2n)2n(n1)(n1)(n45)532
5(n52n32n)2(n2)(n1)n(n1)(n2)10n(n1)(n1)上式第二项是5个连续整数的积,它能被5整除,又其余两项也都都能被5整除,
5|f(n). 综上可知
15|f(n).
注 本题用到数论中的常用结论:“a个连续整数中有且仅有一个能被a整除”;
333例6若a,b,c为整数,且abc是24的倍数,求证:
13
120|[(a5b5c5)4(abc)].
534222a5a4aa(a5a4)a(a1)(a4) 证明 由于(a2)(a1)a(a1)(a2),
它是五个连续整数之积,因而是5!120的倍数.
5353c5c4c 都是120的倍数.
b5b4b同理可得 ,555333 因此,(abc)4(abc)5(abc)是120的倍数.
333333(abc)(abc)是120的倍数, 又已知 是24的倍数,故5
555(abc)4(abc)是120的倍数. 所以
(注 本题利用结论:a个连续整数的乘积一定能被a!整除).
习题1. 2
1. 设3( a2 b2),证明:3a且3b ,其中a,b是任意整数.
|a,则a21与a21有且仅有一个是5的倍数. 2. 对于整数a,若53. 证明:对于任意给定的n个整数,必可以从中找出若干个数作和,使得这个和能被n整除.
4. 证明:对于任何整数n,m,等式n2 (n 1)2 = m2 2不可能成立.
5. 设a1, a2, , an是整数,且a1 a2 an = 0,a1a2an = n,证明n必是4的倍数.
2006M579116. 设,求证: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, R2Z,使得
x3 = 9Q1 R1,y3 = 9Q2 R2
,
由例5可知R1和R2被9除的余数分别与r13和r23被9除的余数相同,
由于r10,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, , anZ,f(x) = anxn a1x a0
,若f(0)与f(1)15
都不是3的倍数,证明:若方程f(x) = 0有整数解,则
3f(1) = a0
a1 a2
(1)nan
.
证明 对任何整数x,都有 x = 3q r,(r = 0,1,2,qZ).
(ⅰ) 若r = 0,即x = 3q,qZ,则
f(x) = f(3q) = an(3q)n a1(3q) a0 = 3Q1 a0 = 3Q1 f(0),
其中Q1Z,由于f(0)不是3的倍数,所以f(x) 0;
(ⅱ) 若r = 1,即x = 3q 1,qZ,则
f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0
= 3Q2 an a1 a0 = 3Q2 f(1),其中Q2Z.
由于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), 其中Q3Z.
所以 3f(1) = a0
a1 a2
(1)nan
.
m|(2n1).
例9 设m,n为正整数,m2,证明:(21)证明 对正整数m,n分以下三种情形讨论.
nn(ⅰ) 当nm时,21(21)2,由于nm,m2,
n|2, 故(2n1)|(2n1). 所以
2n12,因而(21)nm1(ⅱ) 当nm时,有nm1,有
2121
m1m注意到m2,于是2m122m12m12m,即2121
综合上述两式得:
2n12m112m1,
m|(2n1); 故
(21)16
(ⅲ) 当nm时,设nmqr,(0rm,qN),
nmqr1(2mq1)2r(2r1), 由于
212mmq由于
(21)|(21).
nmqm当r0时,
21(21)2(21)M2,(MZ),
|(2n1);
|2, 从而
(2m1)由于m2,故2m12, 因此(2m1)|(2r1). 当0rm时, 由(ⅱ)知:(2m1)m|(2n1) 证毕. 故
(21)注
此例题解答过程中用到分类的思想方法,以及带余数的除法。
习题
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的约数(因数或除数),记为ba;
|a。如果不存在整数c使得a = bc成立,则称a不能被b整除,记为b
在整除的定义中应特别注意:
(1)0不整除任何整数(即0不能作除数),但任何非零数整除0;
在记号“ba”中蕴含着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是整数,下面的结论成立:
(ⅰ) ab,bc ac(整除的传递性);
(ⅱ) ab ab,即a b |a||b|;
ma, nb
mnab;
(ⅲ) 若ba,且bc b(ka+lc)(其中k, l是任意的整数);
一般地,若mai,i = 1, 2, , n m(q1a1 q2a2 qnan),
此处qi(i = 1, 2, , n)是任意的整数;
(ⅳ) ba bcac,此处c是任意非零的整数;
(ⅴ) 若ba,a 0 |b| |a|;若ba,且|a| < |b| a = 0;
若ba,且ab,a>0, b>0, 则a=b.
证明 (ⅰ)由整除定义及a|b,b|c,知: 存在两个整数k1,k2使得:
bak1,cbk2, 因此c(k1k2)a, 由于k1k2是整数, 故
a|c.
(ⅱ) — (ⅳ)的结论类似可证. 证毕.
注 为了证明“b|a”,最为基本的手法是将a分解为b与某个整数之积,即abc,其中c是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如:
(Ⅰ)若n是正整数,则
anbn(ab)(an1an2babn2bn1);
(Ⅱ)若n是正奇数,则在上式中以(b)代换b得:
anbn(ab)(an1an2babn2bn1).
例1 证明十进制整数1001能被十进制整数1001整除.
50个02
证明 由分解因式公式(Ⅱ),有
17100110511(103)1
50个015(1031)[(103)16(103)1031],
所以,
10311001能整除1001.证毕
50个0想一想:此题目能变形推广吗?推广后的一般形式是什么?
例2 若n是正奇数,则8(n2 1).
证明 设n = 2k 1,(kZ),则 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为正整数,且mn0, 证明:
(21)|(2证明 由于mn0, 故mn10. 于是:2(2在公式(Ⅰ)中,令
a22,
b1,则:
n12n2m1).
2m2n12mn1)
3
21(2(22n12m2n12mn1)1(22n12mn121)[(22n12mn11))22n11]
所以
(2又
22n11)|(21),
2m2n11(21)(21),
2n2n12n2n因此
(21)|(21).
2n2mnm由定理1.1.1中 (ⅰ),即整除的传递性知:(21)|(21). 证毕.
注1 在此例中,直接证明“(221)|(221)”不易入手,因此尝试选择适当的“中间量(21)”,使之满足定理1.1.1中 (ⅰ)的条件,再利用整除的传递性导出所要的结论.
注2 在此例中,形如“Fn221(nN)”的数称为费马数.
当mn0时, 费马数满足:
Fn|(Fm2),即存在整数t,使得Fm2tFn.
例5 设正整数n的十进制表示为:
n2n1
naka1a0(0ai9,0ik,ak0),
且S(n)akak1a1a0,证明:9|n的充要条件是9|S(n).
k证明:由于nak10
S(n)akak1a110a0,
a1a0,
ai(10i1)a1(101),
nS(n)ak(10k1)i对于所有的0ik, 有9|(101),
由整除的性质知上式右端k个加项中每一项都是9的倍数,
由定理1.1.1之(ⅲ)知它们的和也被9整除,
即9|(nS(n)), 从而
9|n9|S(n). 证毕.
4
注 两个十进制正整数,其中一个被另一个正整数整除的条件,称为“整除的数字特征”.例5得出十进制正整数n被9整除的数字特征是:“9整除n的各位数字之和”.下面例题6得出十进制正整数n被11整除的数字特征是:“11整除n的各位数字的正负交错之和”.
例6 设正整数n的十进制表示为naka1a0(0ai9,ak0),n的个位为起始数字的正负交错和
T(n)a0a1证明:“11|n”的充分必要条件是“11|T(n)”.
kna10a110a0, 证明 由于
k(1)kak,
T(n)a0a1(1)kak,
ai(10i(1)i)a1(101)
nT(n)ak(10k(1)k)ii10(1)99当i为偶数时,
99 ,
其中有偶数个9,显然它是11的倍数;
iii10(1)101(101)s11s(sz), 当i为奇数时,它也是11的倍数,
ii11|(10(1)),(0ik). 即11|(nT(n))成立. 故总有从而11|n11|T(n).
习题1.1
1.设n是整数,则3|n(n1)(2n1).
2. 设正整数n的十进制表示为naka1a0(0ai9,0ik,ak0),n的个位为起始数字的正、负交错的和
T(n)a0a1(1)kak,证明:“11|n”的充分必要条件是“11|T(n)”.
5
2nn3. 若10个男孩和个女孩共买了8n2本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?
24.证明一个整数a若不能被2整除,也不能被3整除, 则a23必能被24整除.
5. 已知整数m,n,p,q适合: (m p) (mn pq),证明:
(m p)(mq np).
1.1.2 带余数除法
对任意两个整数a,b(b0),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的充分必要条件是r0.
证明: 存在性
作整数序列:
,3b,2b,b,0,b,2b,3b,
则a必在上述序列的某两项之间,即存在一个整数q,使得
qba(q1)b
成立. 令aqbr,则aqbr,而0rb.
6
惟一性 假设q1,r1是满足(2) 的两个整数,即
abq1r1(0r1b),
则
abqrbq1r1
于是
b(qq1)r1rb|qq1||r1r|
(3)
由上式推出:
b|r1r|,
由于
0r1,rb0|r1r|b
r1r,代入式(3)得
qq1,惟一性得证.
若abqr(0rb),则
b|ab|r,
因此必有|r1r|0,即
又
0rb, 则
b|rr0.故b|ar0. 证毕
注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.
定义:在式a = bq r(0 r < b)中,q称为a被b除的不完全商,r称为a被b除的余数, 也称为最小非负剩余.
带余数除法是一个重要的工具,数论的许多基本性质都是建立在带余数除法基础之上的.
例1 当
b15,a225时
r015,q17; 有
22515170,当
b15,a417时
0r1215,q27; 有
417152712,0r915,q6;
r60,q5; 且有
8115(5)(6), 此处r{0,1,2,,151},这时的余数r不是最小非负剩余。
7
当
b15,a81时,
有
8115(6)9,
2.带余数除法的变形
推论 若a,b,d(b0)是整数, 则存在惟一一对整数q和r满足:
abqr(dr|b|d)
证明 考虑整数ad及|b|,由带余数除法知,存在惟一的整数对q',r',
adbq'r',0r'|b|,
a|b|q(r'd)(dr'd|b|d)
令rr'd, 则
abqr,
(dr|b|d).
由于q'及r'的惟一性得知q及r是惟一性的. 证毕.
使得
注 这个推论是带余数除法的一种更为灵活的形式.
|b||b|1dd2|b2|b例如: 当时,取; 当时,取, 则
22|b||b|r,2|b,22abqr,
其中|b|1
|b|1r,2|b.22此形式可以统一为:
|b||b|rabqr,
其中.
22这种带余数除法中的余数r叫做绝对最小余数.
注 这里余数满足的不等式中第二个不等号是严格小于号.
例2 设a25,b13,(除数为奇数)
则
2513112(0r1213) (最小非负剩余)
8
对于最小非负剩余而言,存在唯一的整数对
q1,r12;
又
25132(1)(6r16) (绝对最小剩余)
对于绝对最小剩余而言, 存在唯一的整数对
q2,r1.
例3 设a63,b14,(除数为偶数)
(0r714) (最小非负余数)
对于最小非负剩余而言,存在唯一的一对整数q4,r7;
63145(7)则
631447(7r77) (绝对最小余数)
|14||14|r,则存在唯一的整数22对于绝对最小余数而言,若取对:
q5,r7;
|14||14|r对于绝对最小余数而言,若取
22,
由于631447145(7),
则存在两组整数对:q5,r7与q4,r7.(参见课本P4习题4的结论)
|b||b|r因而, 若取
,
则存在唯一的整数对q及r, 使得22abqr.
注: 使用绝对最小余数可以相对简化计算量.
若a = bq r (0 r < b), 则b|a的充分必要条件是r0.
9
注:这个结论揭示了整除与带余数除法之间的联系,因此,整除问题往往可以化归为带余数除法问题来解决.
例1(P4习题3)设a1, a2, , an为不全为零的n个整数,以y0表示集合
A = {y|y = a1x1 anxn,(xiZ,1 i n)}
中的最小正整数,则对于任何yA,有 y0y ;
特别地,有 y0ai
,(1 i n).
证明 设y0 = a1x1 anxnA,对于y = a1x1 anxnA,
由带余数除法存在整数q, rZ,使得
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,即y0y.
显然,ai0a11ai0anA(1 i n),
所以,由已证结论得:y0ai,(1 i n),即ai(1in)是y0的倍数。证毕.
注 此类题目证明方法具有一般性:将整除问题化归为带余数除法问题,通常针对所给“最小正整数”的概念进行反证,证明余数r0..
例2 任意给出的五个整数中,必有其中三个数之和能被3整除.
证明 设这五个整数分别为:ai(i1,2,3,4,5).
令ai = 3qi ri,0 ri < 3,即ri分别考虑以下两种情形:
0,1,2;i1,2,3,4,5.
10
(ⅰ)
若在余数r1, r2, , r5中0,1,2都出现,
不妨设r1 = 0,r2 = 1,r3 = 2
则
a1a2a3(3q13q23q3)(r1r2r3)
3(q1q2q3)(012)3(q1q2q3)3
故
3|(a1a2a3)
(ⅱ)
若在余数r1, r2, , r5中数0,1,2至少有一个不出现 ,
根据抽屉原理,5个整数只取两个不同的数值,至少有三个余数ri应取相同的一个数值,不妨设r1 = r2 = r3 = r,r{0,1,2},此时
a1a2a33(q1q2q3)(r1r2r3)
3(q1q2q3)3r
故
3|(a1a2a3)
综合(ⅰ) 、(ⅱ)可知, 所证结论成立.
证毕.
..Dirichlet原理:
注 例2涉及的抽屉原理也称为PG将m个元素放入n个(mn)抽屉之中,则在其中一个抽屉里至m1]1个元素. 少含有[n值得注意的是,利用带余数除法得到的余数进行分类来构造抽屉,这是初等数论解(证)题中常用的手法(蕴含分类的数学思想方法).
例3 设r是正奇数,证明对任意的正整数n,有
(n2)|[1r2r(n1)rnr]
证明 当n1时,结论显然成立.
rrrrS[12(n1)n], 则 现设n2,令2Sr[1r2r(n1)rnr][nr(n1)r2r1r]
11
2[2rnr][ir(n2i)r][nr2r]
因为r为奇数,上式等号的右边除第一项外,其余的每一加项:
ir(n2i)r[i(n2i)]m(n2)m(mZ)
因此
2S2(n2)Q1, 其中Q1是整数.
|2 显然,2S被n2除得的余数是2, 由于n22, 所以
(n2)|S. 证毕.
(n2)|2S, 从而(n2)注 例3的证明过程中, 关键在于将2S的表达式中满足“其和能被n2整除”的两项配成一对,这种“配对”思想方法,就是将整体对故
象中满足某种特性的对象组合配对, 再利用配对后的特性解决原问题,
它是数论解(证)题中常用的一种手法, 后续章节中也经常涉及配对思想方法.
例4 设a0(aN),证明a个连续整数有且仅有一个能被a整除.
证明 首先证明a个连续整数有一个能被a整除
设a个连续整数为:m,m1,,ma1,
令
maqr,0ra.
若r0, 则a|m.
若r0, 则1ra
1ara1.
由于mraqa|(mr), 从而有
a|[(mr)a],
即
a|[m(ar)],且
m(ar){m1,,m(a1)}
所以a个连续整数有一个能被a整除。
再证明a个连续整数中只有一个数被a整除。
设a|(mi),a|(mj),(0ija1),则
a|ij|
12
又因为0|ij|a,故必有
|ij|0,即ij。
因而a个连续整数有且仅有一个数能被a整除. 证毕.
注 “a个连续整数中有且仅有一个能被a整除”这是初等数论证明问题常用的结论.
进一步可以证明 “a个连续整数的乘积一定能被a!整除”.
例5 证明:任意的整数n,f(n) = 3n5 5n3 7n能被15整除。
证明 对于任意的整数n,欲证结论即:
3|f(n)3n55n37n,53
15|f(n)3n5n7n
535|f(n)3n5n7n.f(n)3n55n37n3(n52n32n)(nn3)3(n52n32n)n(n1)(n1)3|f(n)
f(n)3n55n37n5(n5n3n)2(nn5)5(n5n3n)2n(1n4)5(n52n32n)2n(n1)(n1)(n21)5(n2n2n)2n(n1)(n1)(n45)532
5(n52n32n)2(n2)(n1)n(n1)(n2)10n(n1)(n1)上式第二项是5个连续整数的积,它能被5整除,又其余两项也都都能被5整除,
5|f(n). 综上可知
15|f(n).
注 本题用到数论中的常用结论:“a个连续整数中有且仅有一个能被a整除”;
333例6若a,b,c为整数,且abc是24的倍数,求证:
13
120|[(a5b5c5)4(abc)].
534222a5a4aa(a5a4)a(a1)(a4) 证明 由于(a2)(a1)a(a1)(a2),
它是五个连续整数之积,因而是5!120的倍数.
5353c5c4c 都是120的倍数.
b5b4b同理可得 ,555333 因此,(abc)4(abc)5(abc)是120的倍数.
333333(abc)(abc)是120的倍数, 又已知 是24的倍数,故5
555(abc)4(abc)是120的倍数. 所以
(注 本题利用结论:a个连续整数的乘积一定能被a!整除).
习题1. 2
1. 设3( a2 b2),证明:3a且3b ,其中a,b是任意整数.
|a,则a21与a21有且仅有一个是5的倍数. 2. 对于整数a,若53. 证明:对于任意给定的n个整数,必可以从中找出若干个数作和,使得这个和能被n整除.
4. 证明:对于任何整数n,m,等式n2 (n 1)2 = m2 2不可能成立.
5. 设a1, a2, , an是整数,且a1 a2 an = 0,a1a2an = n,证明n必是4的倍数.
2006M579116. 设,求证: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, R2Z,使得
x3 = 9Q1 R1,y3 = 9Q2 R2
,
由例5可知R1和R2被9除的余数分别与r13和r23被9除的余数相同,
由于r10,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, , anZ,f(x) = anxn a1x a0
,若f(0)与f(1)15
都不是3的倍数,证明:若方程f(x) = 0有整数解,则
3f(1) = a0
a1 a2
(1)nan
.
证明 对任何整数x,都有 x = 3q r,(r = 0,1,2,qZ).
(ⅰ) 若r = 0,即x = 3q,qZ,则
f(x) = f(3q) = an(3q)n a1(3q) a0 = 3Q1 a0 = 3Q1 f(0),
其中Q1Z,由于f(0)不是3的倍数,所以f(x) 0;
(ⅱ) 若r = 1,即x = 3q 1,qZ,则
f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0
= 3Q2 an a1 a0 = 3Q2 f(1),其中Q2Z.
由于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), 其中Q3Z.
所以 3f(1) = a0
a1 a2
(1)nan
.
m|(2n1).
例9 设m,n为正整数,m2,证明:(21)证明 对正整数m,n分以下三种情形讨论.
nn(ⅰ) 当nm时,21(21)2,由于nm,m2,
n|2, 故(2n1)|(2n1). 所以
2n12,因而(21)nm1(ⅱ) 当nm时,有nm1,有
2121
m1m注意到m2,于是2m122m12m12m,即2121
综合上述两式得:
2n12m112m1,
m|(2n1); 故
(21)16
(ⅲ) 当nm时,设nmqr,(0rm,qN),
nmqr1(2mq1)2r(2r1), 由于
212mmq由于
(21)|(21).
nmqm当r0时,
21(21)2(21)M2,(MZ),
|(2n1);
|2, 从而
(2m1)由于m2,故2m12, 因此(2m1)|(2r1). 当0rm时, 由(ⅱ)知:(2m1)m|(2n1) 证毕. 故
(21)注
此例题解答过程中用到分类的思想方法,以及带余数的除法。
习题
17