当前位置:首页 >> 学科竞赛 >>

第五讲 整除续


第五讲

整除续

(接第四讲) Ⅲ.方幂问题 一个正整数 n 能否表成 m 个整数的 k 次方和的问题称为方幂和问题.特别地, m ? 1 时 当 称为 k 次方问题,当 k ? 2 时,称为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数,关于平方数,明显有如下一些简 单的性质和结论: (1)平方数的个位数字只可能是 0,

1,4,5,6,9. (2)偶数的平方数是 4 的倍数,奇数的平方数被 8 除余 1,即任何平方数被 4 除的余数 只能是 0 或 1. (3)奇数平方的十位数字是偶数. (4)十位数字是奇数的平方数的个位数一定是 6. (5)不能被 3 整除的数的平方被 3 除余 1,能被 3 整除的数的平方能被 3 整除.因而, 平方数被 9 除的余数为 0,1,4,7,且此平方数的各位数字的和被 9 除的余数也只能为 0, 1,4,7. (6)平方数的约数的个数为奇数. (7)任何四个连续整数的乘积加 1,必定是一个平方数. 进一步研究可得到有关平方和的几个结论: 定理三:奇素数 p 能表示成两个正整数的平方和的充要条件是 p ? 4m ? 1. 定理四:设正整数 n ? m p ,其中 p 不再含平方因数,n 能表示成两个整数的平方的充
2

要条件是 p 没有形如 4q ? 3 的质因数. 定理五:每个正整数都能表示成四个整数的平方和. 这几个定理的证明略.这里重点是介绍有关 k 方幂的解法技巧. k 方幂中许多问题实质上 是不定方程的整数解问题,比如著名的勾股数问题. 赛题精讲 例 1:证明:对于任何自然数 n 和 k ,数 f (n, k ) ? 2n 个连续的正整数之积. (1981 年全国高中联赛试题) 【证明】由性质 9 知,只需证明数 f (n, k ) 不能被一个很小的自然数 n 整除.因
3k

? 4n k ? 10 都不能分解成若干

f (n, k ) ? 3n 3k ? 3n k ? n 3k ? n k ? 10 ? 3(n 3k ? n k ? 3) ? n k (n k ? 1)( n k ? 1) ? 1, 3 | 3(n 3k ? n k ? 3),3 | n k (n k ? 1)( n k ? 1), 3 1,故 3
1

f (n, k ) ,因而 f (n, k ) 不能分解成三

个或三个以上的连续自然数的积. 再证 f (n, k ) 不能分解成两个连续正整数的积. 由上知, f (n, k ) ? 3q ? 1(q ? N ) ,因而只需证方程: 3q ? 1 ? x( x ? 1) 无正整数解.而 这一点可分别具体验算 x ? 3r ,34 ? 1,34 ? 2 时, x( x ? 1) 均不是 3q ? 1 形的数来说明. 故 f (n, k ) 对任何正整数 n 、 k 都不能分解成若干个连续正整数之积. 例 2: 设 p 和 q 均为自然数,使得

p 1 1 1 1 ? 1? ? ??? ? . q 2 3 1318 1319
证明: p 可被 1979 整除. 【证明】 (第 21 届 IMO 试题)

p 1 1 1 1 1 1 ? (1 ? ? ? ? ) ? 2( ? ? ? ? ) q 2 3 1319 2 4 1318
1 1 1 1 1 ? ??? ) ? (1 ? ? ? ? ) 2 3 1319 2 659 1 1 1 1 1 1 =( ? )?( ? ) ??? ( ? ) 660 1319 661 1318 989 990 1 1 1 =1979×( ? ??? ) 660 ? 1319 661 ? 1318 989 ? 990
= (1 ?

两端同乘以 1319!得 1319!? 1979 为质数,且 1979

p ? 1979 ? m(m ? N *). 此式说明 1979|1319!× p. 由于 q

1319! ,故 1979| p.

【评述】把 1979 换成形如 3k ? 2 的质数,1319 换成 2k ? 1(k ? N *) ,命题仍成立. 牛顿二项式定理和 (a ? b) | a ? b , (a ? b) | a ? b (n 为偶数), (a ? b) | a ? b (n 为
n n n n n n

奇数)在整除问题中经常用到. 例 3 :对于整数 n 与 k ,定义 F (n, k ) ?

?r
r ?1

n

2 k ?1

, 求证: F (n,1) 可整除 F (n, k ).
(1996 加拿大数学竞赛试题)

【证明】当 n ? 2m 时, F (2m,1) ?

? r ? m(2m ? 1),
r ?1

2m

2

F (2m, k ) ? ? r 2 k ?1 ?
r ?1
m

m

r ? m ?1
m

?r

2m

2 k ?1

? ? r 2 k ?1 ? ? (2m ? 1 ? r ) 2 k ?1
r ?1 m r ?1

? ? [r 2 k ?1 ? (2m ? 1 ? r ) 2 k ?1 ],
r ?1

由于[…]能被 r ? (2m ? 1 ? r ) ? 2m ? 1 整除,所以 F (2m, k ) 能被 2m ? 1 整除,另一方 面,

F (2m, k ) ?

? [r
r ?1

m ?1

2 k ?1

? (2m ? r ) 2 k ?1 ] ? m 2 k ?1 ? (2m) 2 k ?1 ,

上式中[…]能被 r ? (2m ? r ) ? 2m 整除,所以 F (2m, k ) 也能被 m 整除.因 m 与 2 m +1 互质,所以 F (2m, k ) 能被 m (2 m +1) (即 F (m,1) )整除. 类似可证当 n ? 2m ? 1 时,F(2 m +1, k )能被 F(2 m +1,1)整除. 故 F (n, k ) 能 被

F (n,1) 整除.
例 4 :求一对整数 a, b ,满足:(1) ab(a ? b) 不能被 7 整除; (2) (a ? b) ?a ? b 能
7 7 7

被 77 整除.
7 7 7 5 5 3 3 2

(第 25 届 IMO 试题)
2

【解】 (a ? b) ?a ? b = 7ab[( a ? b ) ? 3ab(a ? b ) ? 5a b (a ? b)] = 7ab(a ? b)( a ? b ? ab) .
2 2 2

根据题设要求(1)(2)知, 7 | (a ? b ? ab) |, 即 7 | a ? b ? ab.
6 2 2 2 3 2 2

令 a ? b ? ab ? 7 , 即 (a ? b) ? ab ? 343, 即 a ? b ? 19 ,则 ab ? 19 ? 343 . 故可令
2 2 3 2

2

a ? 18, b ? 1 即合要求.
(第 15 届美国普特南数学竞赛试题) 【评述】数学归纳法在整除问题中也有广泛应用. 例 5:是否存在 1000000 个连续整数,使得每一个都含有重复的素因子,即都能被某个 素数的平方所整除? 【解】存在.用数学归纳法证明它的加强命题:对任何正整数 m, 存在 m 个连续的整数,
3

使得每一个都含有重复的素因子. 当 m =1 时,显然成立.这只需取一个素数的平方. 假设当 m = k 时命题成立,即有 k 个连续整数 n ? 1, n ? 2,?, n ? k ,它们分别含有重复的 素 因 子 p1 , p 2 ,?, p k , 任 取 一 个 与 p1 , p 2 ,?, p k 都 不 同 的 素 数 p k ?1 ( 显 然 存 在 ), 当
2 2 2 t ? 1,2, ? p k ?1 时 , tp12 p 2 ? p k ? n ? (k ? 1) 这 p k2?1 个 数 中 任 两 个 数 的 差 是 形 如 2 2 2 ap12 p 2 ? p k (1 ? a ? p k ?1 ? 1) 的数,不能被 p k2?1 整除,故这 p k2?1 个数除以 p k2?1 后,余数两两不

同.但除以 p k ?1 后的余数只有 0, …,p k ?1 -1 这 p k ?1 个, 1, 从而恰有一个数 t 0 (1 ? t 0 ? p k ?1 ) ,
2 2 2 2

使 t 0 p1 p 2 ? p k ? n ? (k ? 1) 能被 p k ?1 整除.这时, k ? 1) 个连续整数: (
2 2 2 2 2 2 2 2 2 2 t 0 p12 p 2 ? p k ? n ? 1, t 0 p12 p 2 ? p k ? n ? 2 , … , t 0 p12 p 2 ? p k ? n ? k , 2 2 t 0 p12 p 2 ? p k ? n ? ( k +1)

分别能被 p1 , p 2 ? p k , p k ?1 整除,即 m ? k ? 1 时命题成立.故题对一切正整数 m 均成立.
2 2 2 2

例 6:求证:

[a, b, c] 2 (a, b, c) 2 ? . [a, b][b, c][c, a] (a, b)(b, c)(c, a)
(第 1 届美国数学奥林匹克竞赛试题)

【证明】设 a ?

? p? i, b ? ? p ? i, c ? ? p? i, 其中 p i 为质数, ? i , ? i , ? i 为非负整数,则
n n n i i i i ?1 i ?1 i ?1

[a, b, c] ? ? pimax( ? i , ? i ,? i ) ,
i ?1

n

[a, b] ? ? pimax( ? i , ? i ) ?,
i ?1

n

(a, b, c) ? ? ? pim i n? i(, ? i ,? i ) ,
i ?1

n

(a, b) ? ? pimin( ? i , ? i ) ?,
i ?1

n

因此只需证明
4

2 max( ? i , ? i , ? i ) ? max( ? i , ? i ) ? max( ? i , ? i ) ? max( ? i ,? i ) =2 min( ? i , ? i , ? i ) ? min(? i , ? i ) ? min( ? i , ? i ) ? min(? i ,? i ) 上式关于 ? i , ? i , ? i 对称,则不妨设 ? i ? ? i ? ? i ,于是上式变为:

2? i ? ? i ? ? i ? ? i ? 2? i ? ? i ? ? i ? ? i . 此式显然成立,故得证.
例 7 : 设 a 和 b 是 两 个 正 整 数 , (a, b) ? 1, p 为 大 于 或 等 于 3 的 质 数 ,

c ? (a ? b,

ap ?bp ) ,试证: (1) (c, a) ? 1 ; (2) c ? 1 或 c ? p. (1985 新加坡数学竞赛试题) a?b ap ?bp ? cs(t , s ? N ) , 两 式 相 乘 得 a?b

【 证 明 】 由 已 知 得 a ? b ? ct,

c 2 st ? a p ? b p ? a p ? (ct ? a) p ? c p t p ? pac p ?1t p ?1 ? ? ? pa p ?1ct, 于是 cs ? c p ?1t p ?1 ? pac p ?2 t p ?2 ? ? ? pa p ?1 , 故 c | pa p ?1 .
(1)现用反证法来证明 (c, a) ? 1 .若 (c, a) ? k ? 1, 令 q 是 k 的一个质因子,则有

q | c, q | a. 因 c | a ? b ,则 q | a ? b ,从而 q | b. 于是 q 是 a 、 b 的一个公约数,这与 (a, b) =1
矛盾,故 (c, a) ? 1 . (2)因为 c | pa 例 8:设 S n ?
n
p ?1

, (c, a) ? 1, 所以 c | p. 而 p 为质数且 p ? 3 ,故 c ? 1 或 c ? p.
5

? (k
k ?1

? k 7 ) ,求最大公约数 d ? (S n , S 3n ). (第 26 届 IMO 预选题)

【解】能过具体计算可猜想

S n ? 2(1 ? 2 ? ? ? n) 4 ? 2(

n(n ? 1) 4 ) . 2

此式不难用数学归纳法获证.

为求 d ? ( S n , S 3n ) ,对 n 分奇偶来讨论. (1)当 n ? 2k 时,

d ? (2[

2k (2k ? 1) 4 6k (6k ? 1) 4 ] ,2[ ] ) ? (2k 4 (2k ? 1) 4 ,2 ? 81k 4 (6k ? 1) 4 ). 2 2
5

由于 2k ? 1

和 6k ? 1 互质,所以 d ? 2k (( 2k ? 1) ,81). 而当 k ? 3t ? 1 时
4 4

(2k ? 1) 4 ? 81(2t ? 1) 4 , k ? 3t ? 1 时, (2k ? 1) 4 与 81 互质.故此时有

? n 4 81 4 4 ?2 ? 81k ? 2 ? 81 ? 4 ? n , 当n ? 6t ? 2 时; ? 8 2 d ?? ?2k 4 ? 1 n 4 , 当n ? 6t ? 6或6t ? 4时(t ? 0). ? 8 ?
(2)当当 n ? 2k ? 1 时 d ? (2[( 2k ? 1)( k ? 1)] ,2[3(2k ? 1)(3k ? 2) ).
4 4

因3k ? 2与2k ? 1, k ? 1 与质,所以 k ? 2(2k ? 1) 4 (( k ? 1) 4 ,34 ). 而当 k ? 3t ? 2 时,
k ? 1 ? 3(t ? 1), k ? 3k ? 2 时, k ? 1与 34 互质.故此时有
4 4 4 4 ? ?2( 2k ? 1) ? 3 ? 2n ? 3 ? 162 n , 当n ? 6t ? 5时; d ?? ?2( 2k ? 1) 4 ? 2n 4当n ? 6t ? 1或6t ? 3时). ?

例 9: m 盒子中各若干个球,每一次在其中 n(n ? m) 个盒中加一球.求证:不论开始的 分布情况如何,总可按上述方法进行有限次加球后使各盒中球数相等的充要条件是

(m, n) ? 1.

(第 26 届 IMO 预选题)

【证明】设 (m, n) ? 1 ,则有 u, v ? Z 使得 un ? vm ? 1 ? v(m ? 1) ? (v ? 1) ,此式说明: 对盒子连续加球 u 次,可使 m ? 1 个盒子各增加了 v 个,一个增加 (v ? 1) 个.这样可将多增加 了一个球的盒子选择为原来球数最少的那个,于是经过 u 次加球之后,原来球数最多的盒子 中的球与球数最少的盒子中的球数之差减少 1,因此,经过有限次加球后,各盒球数差为 0, 达到各盒中的球数相等. 用反证法证明必要性.若 (m, n) ? d ? 1 ,则只要在 m 个盒中放 m ? 1 个球,则不管加球 多少次,例如,加球 k 次,则这时 m 个盒中共有球 m ?1 ? kn(个) ,因为 d | m, d | n, d ? 1, 所以 m ?1 ? kn 不可能是 d 的倍数,更不是 m 的倍数,各盒中的球决不能一样多,因此,必 须 (m, n) ? 1 . 例 10:求所有这样的自然数 n ,使得 2 ? 2 ? 2 是一个自然数的平方.
8 11 n

(1980 年第 6 届全俄数学竞赛试题)
6

【证明】 (1)当 n ? 8 时, N ? 2 ? 2 ? 2 ? (2
8 11 n

8? n

? 211?n ? 1) ,因(…)为奇数,所

以要使 N 为平方数, n 必为偶数.逐一验证 n ? 2,4,6,8 知,N 都不是平方数. (2)当 n ? 9 时, N ? 2 ? 2 ? 2 ? 2 ? 11 不是平方数.
8 11 9 8

(3)当 n ? 10 时, N ? 2 (9 ? 2
8

n ?8

) ,要 N 为平方数, 9 ? 2 n ?8 应为奇数的平方,不

妨假设 9 ? 2

n ?8

= (2k ? 1) ,则 2
2

n ?10

? (k ? 1) ? (k ? 2). 由于 k ? 1 和 k ? 2 是一奇一偶,左边

为 2 的幂,因而只能 k ? 1 =1,于是得 k ? 2 ,由 2 n?10 ? 2 2 知 n ? 12 为所求.

7


相关文章:
第五讲:数的整除(教师)
第五讲:数的整除(教师)_学科竞赛_小学教育_教育专区。小学奥数-数的整除人教版小学奥数数的整除我们在已经学习了能被 2,3,5 整除的数的特征,这一讲我们将讨论...
小升初专题第五讲整除问题
小升初专题第五讲整除问题 小升初专题小升初专题隐藏>> 第五讲 整数问题之一整数是最基本的数,它产生了许多有趣的数学问题.在中、小学生的数学竞赛中,有 关...
整除
整除_四年级数学_数学_小学教育_教育专区。整数 整除 代数 小学 奥数今日...第四讲 整除 5页 免费 整除 21页 免费 第五讲 整除续 7页 免费 整数—整除...
题目1bbad5bbfd0a79563c1e727c
满足条件的事件是连续输出的4个数字之和能被3整除,即连续输出的4个数字中有两个1和两个2,表示为1,1,2,2;1,2,1,2;1,2,2,1;2,1,1,2;2,2,1,1...
第五讲 能被25整除的数的特征(老师用)
第五讲 能被25整除的数的特征(老师用)_学科竞赛_小学教育_教育专区。第五讲 能被 2,5 整除的数的特征 同学们都知道,自然数和 0 统称为(非负)整数。同学...
涉及三个连续自然数的整除问题
涉及三个连续自然数的整除问题_学科竞赛_小学教育_教育专区。王凯成(笔名王凯),教授,全国优秀教师,教育部第三批国培计划专家库专家,曾宪梓奖获得者,全国初等数学...
更多相关标签:
李丰吉特巴教学第五讲 | 王建军慢四教学第五讲 | 第五讲 乾卦的智慧 | 王建军慢三教学第五讲 | 李丰吉特巴花第五讲 | 王建军慢四第五讲 | 辞赋写作第五讲 | 缠论完美教程第五讲 |