tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

2012江苏省数学竞赛《提优教程》教案:第35讲


第 16 讲

整数的性质

初等数论的基本研究对象是整数.两个整数的和、差、积都是整数,但商却不一定是整 数.由此引出了数论中最基本的概念:整除. 整除性理论是初等数论中最基础的部分,它是在带余除法的基础上建立起来的. 整数 a 除以整数 b (b≠0),可以将 a 表示为 a=bq+r,这里 q,r 是整数,且 0?r<b.q 称为 a

除以 b 所得的商,r 称为 a 除以 b 所得的余数. 当 r=0 时,a=bq,称 a 能被 b 整除,或称 b 整除 a,记为 b | a,b 叫做 a 的因数,a 叫 做 b 的倍数;q 取 1,则 a=b,a 也是它本身的因数. 当 r≠0 时,称 a 不能被 b 整除,b 不整除 a,记作 b├ a. 若 c | a,c | b,则称 c 是 a,b 的公因数,a,b 的最大公因数 d 记为(a,b). 若 a | c,b | c,则称 c 是 a,b 的公倍数,a,b 的最小公倍数 M 记为[a,b]. 一个正整数,按它的正因数个数可以分为三类.只有一个正因数的正整数是 1;有两个正 因数的正整数称为素数(质数),素数的正因数只有 1 和它本身;正因数个数超过两个的正整数 称为合数,合数除了 1 和它本身外还有其他正因数. 任何一个大于 1 的整数均可分解为素数的乘积,若不考虑素数相乘的前后顺序,则分解 式是惟一的.一个整数分解成素数的乘积时,其中有些素数可能重复出现,把分解式中相同 的素数的积写成幂的形式,大于 1 的整数 a 可以表示为: a= p1 1 ? p2 2 …pi i …pS S ,其中 i=l,2,?,s. 以上式子称为 a 的标准分解式. 大于 l 的整数的标准分解式是惟一的(不考虑乘积的先后顺序). 若 a 的标准分解式是 a= p1 1 ? p2 2 …pi i …pS S ,其中 i=l,2,?,s,则 d 是 a 的正因数的 充要条件是 d= p1 1 ? p2 2 …pi i …pS S ,其中
? ? ? ?
? ? ? ?
? ? ? ?

0?βi?αi,i=l,2,?,s. 由此可知,a 的正因数的个数为 d(a)=(α1+1) (α2+1)?(αs+1) . 由 a 的标准分解式 a= p1 1 ? p2 2 …pi i …pS S (i=l, 2, ?, s), 若 a 是整数的 k 次方, 则 αi(i=l, 2,?,s)是 k 的倍数.若 a 是整数的平方,则 αi(i=l,2,?,s)是偶数. 推论:设 a=bc,且(b,c)=1,若 a 是整数的 k 次方,则 b,c 也是整数的 k 次方.若 a 是整数的平方,则 b,c 也是整数的平方.
? ? ? ?

A 类例题
例 1. 若任何三个连续自然数的立方和都能被正整数 a 整除, 则这样的 a 的最大值是 ( A. 9 分析 B. 3 C. 2 D. 1 )

观察最小的三个连续自然数的立方和 36,a 是它的约数,a 不会超过 36,不能排

除任何选择支;观察第二个小的三个连续自然数的立方和,进一步缩小 a 的范围,可以排除 取偶数的可能。当前面几个都是某数的倍数时,可以猜想出 a 的最大值,但最好能证明所有

“三个连续自然数的立方和”都是某数的倍数。 解 记 an=n3+(n+1)3+(n+2)3,则 a1=13+23+33=36=4×9,

a2=23+33+43=99 为奇数,则 a | a1,a | a2, (a1,a2)=9,故 a | 9,所以 a=1,3,9。 又 an=n3+(n+1)3+(n+2)3=3n3+9n2+15n+9=3n3+9n2+6n+9n+9=3n(n2+3n +2)+9(n+1)=3n(n+1)(n+2)+9(n+1), ∴9 | an,故 amax=9,选 A。 说明 解法中, 把 3n3+9n2+15n+9 分为 3n(n2+3n+2)与 9(n+1)两部分, 分别说明其

为 9 的倍数。在考虑整除的证明时,把整数 n 的多项式分成几组分别因式分解是常用的方法。 例 2.若 p 是大于 3 的质数,则 p2 除以 24 的余数为 1。 分析:即证明 p2-1 是 24 的倍数,也即证明 p2-1 既是 3 的倍数又是 8 的倍数。p-1、 p+1 之间只有一个质数 p,而连续的两个自然数中必有 2 的倍数,连续的三个自然数中必有 3 的倍数。 证明 1 ∵ p 是大于 3 的质数,∴p 不是偶数,不是 3 的倍数, 又∵ p2-1=(p-1)(p+1),连续的三个整数中必有 3 的倍数, ∴ p-1、p+1 中必有 3 的倍数,且 p-1、p+1 是连续的两个偶数,(p-1)(p+1)是 8 的 倍数。 ∴ p2-1=(p-1)(p+1)是 24 的倍数,即 p2 除以 24 的余数为 1。 证明 2 设 p=6n± 1 (6n,6n± 2,6n+3 均为合数), 则 (6n± 1)2=36n2± 12n+1=12n(3n± 1)+1,

∵ n 和 3n± 1 必为一奇一偶,∴n(3n± 1)为偶数。 ∴ 12n(3n± 1)必为 24 的倍数,∴(6n± 1)2=24k+1 即 p2 除以 24 的余数为 1。 说明 大于 3 的质数,必定是奇数,又不是 3 的倍数,所以一定是形如 6n± 1 的数。6

是 24 的约数,用这样的形式表出后再变形,容易推出结论。 21p+4 例 3.试证明 14p+3 是既约分数。 分析 即证明(21p+4,14p+3)=1。若 a、b、c 是三个不全为 0 的整数,且有整数 t 使得

a=bt +c,则 a、b 与 b、c 有相同的公约数,因而(a,b)= (b,c),即(a,b) = (a-bt,b)。可 以用此法化简。 证明 ∵(21p+4,14p+3)= (21p+4―14p―3,14p+3)

= (7p+1,14p+3)= (7p+1,14p+3―14p―2) = (7p+1,1)=1, 21p+4 ∴ 14p+3 是既约分数。 说明 证明过程中用到性质(a,b)= (a-bt,b),因为,若 d是a 、b 的任一公约数,则

由 d | a, d | b和a ? bt ? c知d | c,即d是b 、c 的公约数;反之,若 d 是 b、c 的任一公约数,d 也是 a、b 的公约数,所以 a,b 与 a-bt,b 有相同的最大公约数。求两个正整数的最大公约 数常用辗转相除法。

链接 辗转相除法: 设 a、b∈N*,且 a>b,由带余除法有

? ? b ? r1q2 ? r2 , 0 ? r2 ? r1 , ? ? ? ? rn ? 2 ? rn ?1qn ? rn , 0 ? rn ? rn ?1 , ? ? rn ?1 ? rn qn ?1 ? rn ?1 , ? rn ?1 ? 0. ? ?
因为每进行一次带余除法,余数至少减 1,即 b>r1>r2>? >rn>rn+1,而 b 为有限数,因此,必有一个最多不超过 b 的正整 数 n 存在,使得 rn≠0,而 rn+1=0,故得: rn= (rn+1,rn)= (rn,rn-1)=?=(r2,r1)= (r1,b)= (a,b) 例如, (3960,756)=(756,180)=(180,36)=36。 例 4. 一个自然数,它的末位数字移到首位时,数值便为原来的 5 倍,求满足条件的最小 自然数。 分析 正整数有多种表示形式,选择适当的形式有利于问题解决。由题目的条件,此表

a ? bq1 ? r1 , 0 ? r1 ? b,

示形式应该把数的末位数字反映出来,而其他位置上的数字可以整体的看待。 ————— ————— ————— 解 设所求数为a1a2?an-1an,由已知得ana1a2?an-1=5a1a2?an-1an, ———— ———— ∴ an×10n-1+a1a2?an-1=5(10×a1a2?an-1+an),

———— ∴ (10n-1-5)an=49a1a2?an-1,∴an× 99

95 =49a1a2?an-1,①

————

( n ?2) 个

∵ an 是个位数字,不能被 49 整除,∴ 99?95 至少能被 7 整除, ∴ 它最小时应为 99995,此时 n=6, ———— 若有解,则①式为 a6×99995=49a1a2a3a4a5, ———— ∴ a6×14285=7a1a2a3a4a5, ———— ∵ 14285 不能被 7 整除,∴ a6=7, ∴ a1a2a3a4a5=14285, ∴ 满足条件的最小自然数为 142857。 说明 99?95 能被 7 整除是必要条件, 99995 是满足被 7 整除条件的最小数, 但 99995

———— ———— 是不是问题的解还要进一步探讨, 如果寻找到满足条件的 a6 和 a1a2a3a4a5, 则a1a2a3a4a5a6就 ———— 是问题的解;如果找不到满足条件的 a6 和 a1a2a3a4a5,则要考虑比 99995 略大的形如 99? 95 的数。

情景再现
1.一个六位数,如果它的前三位数字与后三位数字完全相同,顺序也相同,则它可以不 是 A.7 的倍数 C.11 的倍数 ( )

B.9 的倍数 D.13 的倍数

2.若 p 与 d 都是正整数,其中 d 不能被 6 整除,当 p、p+d、p+2d 都是质数时,则 p + 3d 一定是 A.质数 C. 3 的倍数 3. .已知 n 为正整数,若 于 . 4.求具有下列性质的最小正整数 n: (1) 它以数字 6 结尾; (2) 如果把数字 6 移到第一位之前,所得的数是原数的 4 倍。 ( )

B. 9 的倍数 D.质数或是 9 的倍数

n 2 ? 3n ? 10 是一个既约分数,那么这个分数的值等 n 2 ? 6n ? 16

B 类例题
例 5.试证 1999 | (19981998+20002000-2001). 分析:19981998 和 20002000 是很大的数字,它们除以 1999 的余数常常借助于二项式定理 或 xn+yn,xn-yn 的因式分解公式。
0 n 1 n-1 k n-k k n n 证明:由二项式定理(a+b)n= Cn a + Cn a b+?+ Cn a b +?+ Cn b,

知 (a+b)n=aM+bn,由此可得 19981998=(1999-1) 1998=1999M+1, 20002000-=(1999+1) 2000-=1999N+1, 这里 M,N∈Z.于是 19981998+20002000-2001=1999M+1999N-1999=1999(M+N-1), 从而 1999 | (19981998+20002000-2001). 说明 对于整数的高次方幂的整除,除了运用同余的性质,二项式定理和因式分解的裴

蜀定理是常用的工具。 链接 因式分解公式(裴蜀定理) : 对大于 1 的整数 n 有 xn-yn =(x-y)(xn-1+xn-2y+xn-3y2+??+xyn-2+yn-1); 对大于 1 的奇数 n 有 xn+yn =(x+y)(xn-1-xn-2y+xn-3y2-??-xyn-2+yn-1); 对大于 1 的偶数 n 有 xn-yn =(x+y)(xn-1-xn-2y+xn-3y2-??+xyn-2-yn-1); 二项式定理:
0 n 1 n-1 k n-k k n n (a+b)n= Cn a + Cn a b+?+ Cn a b +?+ Cn b;

k n(n-1)(n-2)?(n-k+1) 其中 Cn = 是整数。 k(k-1)?3×2×1

若 a,b 是整数,则(a+b)n=aM+bn。 例 6.已知自然数 a、b、c 满足[a,b]=24,(b,c)=6,[c,a]=36,则满足上述条件的数 组(a,b,c)有多少组? 分析 条件[a,b]=24 及[c,a]=36 意味着 a、b、c 不大,都是 24 或 36 的约数,对于 a,

它既是 24 又是 36 的约数,所以它是 12 的约数。而 b,满足(b,c)=6,则是 6 的倍数,是 24 的约数,只能取 6,12,24。注意到 a 的取值,b 更是只能取 24。 解 a | 24,a | 36 ? a|12?a=1,2,3,4,6,12. 6 | b,b | 24 ? b=6,12,24.

6 | c,c | 36 ? c=6,12,18,36. 若 a=1,2,3,4,6,12 时,由[a,b]=24,得 b=24, a 不是 9 的倍数,由[a,c]=36,则 c 是 9 的倍数, 再由(b,c)=6,得 c=36 或 18(a=4,12 时), 但(24,36)=12,矛盾.故 c=18. ∴ a=12,b=24,c=18 或 a=4,b=24,c=18. 即有(12,24,18) ,(4,24,18)二组. 说明 例 6 的解法是数论中常用筛法,先粗选出可能的值,再从中筛出满足要求的数来。

例 7.已知 n 是三位奇数,它的所有正因数(包括 1 和 n)的末位数字之和是 33,求满足 条件的数 n。 分析:条件中隐含了整数的正因数个数是奇数。联想算术基本定理: n=pkqi?ts,正因 数个数为 d(n)=(k+1)(i+1)?(s+1),题中每个因数均为奇数,因数的个数也是奇数,故 k,i, s 是偶数,所以 n 完全平方数。三位奇数是完全平方数,范围缩小到 11 个。 还能把范围缩小点吗? 解:由题,所有因数是奇数,所有因数的个数是奇数, 所以,每个质因数的指数是偶数,n 是完全平方数; 若是质数的平方数,则有 3 个因数,个位数字之和不能超过 27, 故为合数的完全平方数; 这样的三位数只能在下列数中间:152,212,252,272。 逐个验算,得 n=729。 说明 本例题的解法实质上还是筛选法,三位数有 900 个,三位奇数是其中一半,但如

果能从条件中发现是完全平方数,范围就非常有限了。 例 8.已知 m、n、k 是正整数,且 mn | nm,nk | kn。证明:mk | km。 (2004 年新西兰数 学奥林匹克) 分析 条件 mn | nm,说明 mn 是 nm 的约数,对于给定的 m、n,怎样去找到 mn 与 nm

的联系?必须具体一些。mn 是 nm 的约数,则 mn 的每一个因数都是 nm 的约数,考虑 证明 设 m、n、k 中所有的质因数分别是 p1,p2,?,ps,不妨设 p1<p2<?<ps,且
? ? ? ?

表示 m = p1 1 ? p2 2 …pi i …pS S ,n = p1 1 ? p2 2 …pi i …pS S ,k = p1 1 ? p2 2 …pi i …pSS ,其中 αi, βi,γi?0,i=l,2,?,s.

?

?

?

?

?

?

?

?

由 mn | nm 得 0?nαi?mβi, 由 nk | kn 得 0?kβi?nγi, 两式相乘得 0?knαiβi?mnβiγi,即 0?kαi?mγi,i=l,2,?,s. ∴ mk | km。 说明 整除和约数问题中,可以借助算术基本定理把抽象的关系式转化为较具体的形式 处理。这里用到性质: 若 a 的标准分解式是 a= p1 1 ? p2 2 …pi i …pS S ,其中 i=l,2,?,s,则 d 是 a 的正因数的 充要条件是 d= p1 1 ? p2 2 …pi i …pS S ,其中
? ? ? ?
? ? ? ?

0?βi?αi,i=l,2,?,s.

情景再现
5.设 m > n ?0,证明:( 2 +1) | ( 2 -1)。 6.证明:当 n 为任何整数时,2n6 – n4 – n2 能被 36 整除。 7.a 是正整数,且 a4 + a3 + a2 + a + 1 是完全平方数,求所有满足条件的 a。 8.设 n 为整数,则 13 除 n2+5n+23 的余数的集合是 。
2n 2m

C 类例题
例 9.设 p 是质数,且 p2 +71 的不同正因数的个数不超过 10 个,求 p. (2006 年江苏初 赛) 分析 分解因数,可以先从 p 的起始值开始探索.由例 2,p2-1 是 24 的倍数,p2+71 =

p2-1+72,72 也是 24 的倍数。所以 23,31 都是 p2+71 的因数。p2+71 正因数个数显然超过 8 个。 解 当 p=2 时,p2+71=75=52×3,此时共有正因数(2+1)×(1+1)=6 个,p=2 满足条件;

当 p=3 时,p2+71=80=24×5,此时共有正因数(4+1)×(1+1)=10 个,p=3 满足条件;

当 p>3 时,p2+71 = p2-1+72=(p-1)( p+1)+72,质数 p 必为 3k±1 型的奇数,p-1、 p+1 是相邻的两个偶数,且其中必有一个是 3 的倍数,所以(p-1)(p+1)是 24 的倍数,所以 p2+71 是 24 的倍数. p2+71=24×m,m?4. 若 m 有不同于 2,3 的质因数,那么 p2+71 的正因数个数?(3 +1)×(1+1)×(1+1)>10;

若 m 中含有质因数 3,那么 p2+71 的正因数个数?(3 +1)×(2+1)>10; 若 m 中仅含有质因数 2,那么 p2+71 的正因数个数?(5+1)×(1+1)>10; 所以 p>3 不满足条件; 综上所述,所求的质数 p 是 2 或 3. 说明 数公式: 若 n 的标准分解式是 n= p1 1 ? p2 2 …pi i …pS S ,其中 i=l,2,?,s,则 a 是 n 的正因数的 充要条件是 a= p1 1 ? p2 2 …pi i …pS S ,其中 0?βi?αi,i=l,2,?,s.由此可知,n 的正因数 的个数为 d(n)=(α1+1) (α2+1)?(αs+1). 例 10.称自然数为“完全数” ,如果它等于自己的所有不包括自身的正约数的和,例如 6 = 1 + 2 + 3。如果大于 6 的“完全数”可被 3 整除,证明它必能被 9 整除。 分析 要证明一个大于 6 且能被 3 整除的“完全数”3n,必定是 9 的倍数,可以从反面
? ? ? ?
? ? ? ?

本题中,对于 p>3 时的情况,也可以设 p=6n± 1 来讨论。注意数 n 的正因数个

考虑——假如它不是 9 的倍数。此时 n 不是 3 的倍数,设集合 A={d |d 是 n 的正约数},则集 合 A 与集合 B={3d |d 是 n 的正约数}的并集恰好是 3n 的正约数集合, “完全数”3n 的所有正 3n n 约数的和 3n +3n 是 4 的倍数,故 n 是偶数。所以 ,n, 都是“完全数”3n 的约数。只要 2 2 还有其它的正约数,即可以说明 3n 不是“完全数”。 解 设“完全数”等于 3n(n>2),假设其中 n 不是 3 的倍数,于是 3n 的所有正约数(包

括它自己)总可以分为两类:能被 3 整除的正约数和不能被 3 整除的正约数,若其中 d 是不 可被 3 整除的正约数,则 3d 是可被 3 整除的正约数,且 d→3d 是一一对应。从而 3n 的所有 正约数的和是 4 的倍数。又由题意,所有正约数的和(包括自身)为 6n,因此,n 是 2 的倍 数。 3n n 因为 n>2,所以 ,n, 和 1 是 3n 的互不相同的正约数,它们的和等于 3n+1>3n,与 2 2 “完全数”的定义矛盾。所以 n 必须是 3 的倍数,即这类“完全数”是 9 的倍数。 说明 本题涉及到两个概念, “完全数”和所有正因数的和。n 是完全数,则它的所有正
? ? ? ?

因 数 的 和 为 2n , 另 外 , 若 n = p1 1 ? p2 2 …pi i …pS S , 则 n 的 所 有 正 因 数 的 和 是 σ
2 2 2 (n)=(1+p1+ p1 +?+ p1 1 )(1+p2+ p2 +?+ p2 2 )?(1+ps+ ps +?+ ps s )=

?

?

?

?i ?1 p1 ?1 。请思考, ? pi ? 1 i ?1
s

能否延此方向解决问题。

情景再现
9.求所有使 p2+2543 具有少于 16 个不同正因数的质数 p。 (2003 年泰国数学奥林匹克) 10. (1) 若 n(n∈N*) 个棱长为正整数的正方体的体积之和等于 2005, 求 n 的最小值, 并说 明理由; (2) 若 n(n∈N*)个棱长为正整数的正方体的体积之和等于 20022005, 求 n 的最小值, 并 说明理由.(2005 年江苏)

习题 13
1.对于正整数 n,如果能找到正整数 a、b,使 n=a+b+ab,则称 n 为“好数” ,则在 前 100 个正整数中,共有“好数”( A.78 个 B.74 个 ) C.70 个 D.66 个

2.设 a 为正奇数,则 a2-1 必是 A. 5 的倍数 B. 3 的倍数 C. 7 的倍数 D. 8 的倍数

3.设 n 为奇质数,求证:2n-1 与 2n+1 不能同时是质数. 4.
100 2001 的整数部分末三位数字是几? 50 2001 ? 95

5.设 n 是正整数,且 4n2+17n-15 表示两个相邻正整