当前位置:首页 >> 学科竞赛 >> 第二讲 整除

第二讲 整除


初等代数选讲-----第二讲

第二讲 整 除 【基础知识】

一.整除的概念及其性质
1、 定义: 设 a , b 是给定的数,b ? 0 , 若存在整数 c , 使得 a ? bc 则称 b 整除 a , 记作 b | a , 并称 b 是 a 的一个约数(或因数),称 a 是 b 的一个倍数,如果不存在上述 c ,则称 b

不能整 除 a 记作 b

a.

2、整除的性质 (1) 若 b | c 且 c | a ,则 b | a (传递性质); (2) 若 b | a 且 b | c ,则 b | (a ? c) ; 若反复运用这一性质,易知 b | a 及 b | c ,则对于任意的整数 u , v 有 b | (au ? cv) ; 更一般,若 a | bi ,则 a |

?c b
i ?1

n

i i

其中 ci ? Z , i ? 1 ,2 , , n ;

(3) 若 b | a ,则或者 a ? 0 ,或者 | a |?| b | ,因此若 b | a 且 a | b ,则 a ? ?b ; (4) (带余除法) 设 a , b 为整数, b ? 0 ,则存在一对整数 q 和 r ,使得 a ? bq ? r ,其中 0 ? r ? b ,满 足以上条件的整数 q 和 r 是唯一确定.整数 q 被称为 a 被 b 除得的(不完全)商,数 r 称为 a 被

b 除得的余数。
注意: r 共有 b 种可能的取值:0,1,……, b ? 1 ;若 r ? 0 ,即为 a 被 b 整除的情形; (5)若 n 是正整数,则 x ? y ? ( x ? y)(x
n n n?1

? x n?2 y ? ? ? xy n?2 ? y n?1 ) ;

在上式中用 ? y 代 y : 若 n 是正奇数,则 x ? y ? ( x ? y)(x
n n n?1

? x n?2 y ? ? ? xy n?2 ? y n?1 ) ; ? xy n?2 ? y n?1 ) ;

若 n 是正偶数,则 x ? y ? ( x ? y)( x
n n
n m

n?1

? x n?2 y ?

(6) 如果在等式

其余项均为 c 的倍数, 则去掉项也是 c 的倍数; ? ai ? ? bk 中取掉某一项外,
i ?1 k ?1

(7) m(m≥2)个连续整数中,有且只有一个是 m 的倍数; (8) 任何 n(n≥2)个连续的整数之积一定是 n!的倍数,特别地,三个连续正整数之积能被 6

1

初等代数选讲-----第二讲

整除; (9)若一个整数的未位数字能被 2(或 5)整除,则这个数能被 2(或 5)整除,否则不能; (10)一个整数的数码之和能被 3(或 9)整除,则这个数能被 3(或 9)整除,否则不能; (11)若一个整数的未两位数字能被 4(或 25)整除,则这个数能被 4(或 25)整除,否则 不能; (12)若一个整数的未三位数字能被 8(或 125)整除,则这个数能被 8(或 125)整除,否 则不能; (13)若一个整数的奇位上的数码之和与偶位上的数码之和的差是 11 的倍数,则这个数能 被 11 整除,否则不能。

二、奇数、偶数的性质
(1) 奇数 ? 奇数=偶数,偶数 ? 偶数=偶数,奇数 ? 偶数=奇数,偶数 ? 偶数=偶数,奇数

? 偶数=偶数,奇数 ? 奇数=奇数;即任意多个偶数的和、差、积仍为偶数,奇数个奇数的
和、差仍为奇数,偶数个奇数的和、差为偶数,奇数与偶数的和为奇数,偶数与偶数的和为 偶数; (2)奇数的平方都可以表示成 8m ? 1 的形式,偶数的平方可以表示为 8m 或 8m ? 4 的形式; (3)任何一个正整数 n ,都可以写成 n ? 2 l 的形式,其中 m 为负整数, l 为偶数。
m

(4)若有限个整数之积为奇数,则其中每个整数都是奇数;若有限个整数之积为偶数,则 这些整数中至少有一个是偶数; 两个整数的和与差具有相同的奇偶性; 偶数的平方根若是整 数,它必为偶数。 三、完全平方数及其性质 能表示为某整数的平方的数称为完全平方数,简称平方数。平方数有以下性质与结论: (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;

2

初等代数选讲-----第二讲

(6)平方数的约数的个数为奇数; (7)任何四个连续整数的乘积加 1,必定是一个平方数。 四.整数的尾数及其性质 整数 a 的个位数也称为整数 a 的尾数,并记为 G ( a ) 。 G ( a ) 也称为尾数函数,尾数函数 具有以下性质: (1)G (G (a)) ? G ( a ) ; (2)G(a1 ? a2 ? ? ? an ) = G[G(a1 ) ? G(a2 ) ? ? ? G(an )] ; (3) G(a1 ? a2 ? ? ? an ) ? G[G(a1 ) ? G(a2 ) ? ?? G(an )] ; (4) G(10a) ? 0 ; G(10a ? b) ? G(b) ; (5)若 a ? b ? 10c ,则 G (a) ? G (b) ; 五.质数与合数及其性质 1.正整数分为三类: (1)单位数 1; (2)质数(素数) :一个大于 1 的正整数,如果它 的因数只有 1 和它本身,则称为质(素)数; (3)合数:如果一个正整数包含有大于 1 且小 于其本身的因子,则称这个正整数为合数。 2.有关质(素)数的一些性质 (1) a , b 互质,若 a | c, b | c ,则 ab | c ; (2)若 p 是质(素)数, a 为任一整数,则必有 p | a 或( a, p )=1; (3) 设 a1, a2 ,?, an 为 n 个整数,p 为质 (素) 数, 且 p | a1a2 ?an , 则 p 必整除某个 a( , i 1? i ? n )
n 特别地,若 p 是质数,若 p | a ,则 p | a ;

(4) (算术基本定理,也叫整数的唯一分解定理)任何一个大于 1 的正整数 a ,能唯一地表 示成质(素)因数的乘积(不计较因数的排列顺序) ;
a1 a2 (5)任何大于 1 的整数 a 能唯一地写成 a ? p1 p2 ? pk k , i ? 1,2, ,?, k a



的形式,其中 pi 为质(素)数( pi ? p j (i ? j ) ) 。上式叫做整数 a 的标准分解式; (6)若 a 的标准分解式为①, a 的正因数的个数记为 f ( a ) ,则 f (a) ? (a1 ? 1)(a2 ? 1) ? (ak ? 1) 。

六、最大公约数及性质
1、定义(最大公约数) 设 a , b 不全为零,同时整除 a , b 的整数(如 ? 1 )称为它们的公约

3

初等代数选讲-----第二讲

数。 因为 a , b 不全为零, 故 a , b 只有有限多个, 我们将其中最大一个称为 a , b 的最大公约数, 用符号( a , b )表示。显然,最大公约数是一个正整数。 当( a , b )=1(即 a , b 的公约数只有 ? 1 )时,我们称 a 与 b 互素(互质) 。 同样,如果对于多个(不全为零)的整数 a, b,? , c ,可类似地定义它们的最大公约数 ( a, b,? , c ) 。若( a, b,? , c )=1,则称 a, b,? , c 互素。请注意,此时不能推出 a, b,? , c 两两互素;但反过来,若 a, b,? , c 两两互素,则显然有( a, b,? , c )=1。 2、最大公约数的性质 例如任意改变 a , b 的符号,不改变( a , b )的值,即 (? a,?b) ? (a, b) ; ( a , b )可以交 换, ( a, b ) = ( b, a ) ; ( a, b ) 作为 b 的函数, 以 a 为周期, 即对于任意的实数 x , 有 ( a, b ? ax ) =( a , b )等等。为了更详细地介绍最大公约数,我们给出一些常用的一些性质: (1)设 a , b 是不全为 0 的整数,则存在整数 x, y ,使得 ax ? by ? (a, b) ; (2)两个整数 a , b 互素的充要条件是存在整数 x, y ,使得 ax ? by ? 1 ; 事实上,条件的必要性是性质(1)的一个特例。反过来,若有 x, y 使等式成立,不妨 设 (a, b) ? d ,则 d | a, d | b ,故 d | ax 及 d | by ,于是 d | (ax ? by) ,即 d | 1 ,从而 d ? 1 。 (3) 若 m | a, m | b ,则 m | (a, b) ,即 a , b 的任何一个公约数都是它们的最大公约数的约数; (4)若 m ? 0 ,则 (m a, m b) ? m(a, b) ; (5)若 (a, b) ? d ,则 ? 整数; (6)若 (a, m) ? 1, (b, m) ? 1 ,则 (ab, m) ? 1 ,也就是说,与一个固定整数互素的整数集关于乘法
k 封 闭 。 并 由 此 可 以 推 出 : 若 (a, b) ? 1 , 对 于 ?k ? 0 有 (a , b) ? 1 , 进 而 有 对 ?l ? 0 有

?a b? , ? ? 1 ,因此两个不互素的整数,可以自然地产生一对互素的 ?d d ?

(a k , b l ) ? 1 。
(7)设 b | ac ,若 (b, c) ? 1 ,则 b | a ;

4

初等代数选讲-----第二讲

(8)设正整数 a , b 之积是一个正整数的 k 次方幂( k ? 2 ) ,若( a , b )=1,则 a , b 都是整 数的 k 次方幂。一般地,设正整数 a, b,? , c 之积是一个正整数的 k 次方幂( k ? 2 ) ,若

a, b,? , c 两两互素,则 a, b,? , c 都是正整数的 k 次方幂。

(9)辗转相除法:
设两数为 a、b(b<a),求它们最大公约数(a、b)的步骤如下: ① 用 b 除 a,得 a ? bq1 ? r 1 ? 0 ,则(a,b)=b; 1, ?0 ? r 1 ? b ? ,若 r ② 若 r1 ? 0 ,则再用 r1 除 b,得 b ? rq 2 ? 0 ,则(a,b)= r 1. 1 2 ?r 2 , ?0 ? r 2 ? b ? ,若 r ③ 若 r2 ? 0 ,则继续用 r2 除 r1 ,……如此下去,直到能整除为止,其中最后一个非零余数 即为(a,b).例如:求 212 与 36 的最大公因数.

七、最小公倍数及性质
1、最小公倍数定义: 设 a , b 是两个非零整数,一个同时为 a , b 倍数的数称为它们的公 倍数, a , b 的公倍数有无穷多个,这其中最小的一个称为 a , b 的最小公倍数,记作 ?a, b? , 对于多个非零实数 a, b,? , c ,可类似地定义它们的最小公倍数[ a, b,? , c ] 。 2、最小公倍数的性质 (1) a 与 b 的任一公倍数都是 ?a, b? 的倍数,对于多于两个数的情形,类似结论也成立; (2)两个整数 a , b 的最大公约数与最小公倍满足: (a, b)?a, b? ?| ab | (但请注意,这只限 于两个整数的情形,对于多于两个整数的情形,类似结论不成立) ; (3)若 a, b,? , c 两两互素,则[ a, b,? , c ]=| a ? b ?

? c |; ?c | d 。

(4)若 a | d , b | d ,?, c | d ,且 a, b,? , c 两两互素,则 a ? b ?

【练习】
1.证明: 10 ? 01 被 1001 整除。 ? ? ?
2000 个 0

证明: 10 ? 01 ? 10 ? ? ?
2000 个0
3

2001

? 1 ? (103 ) 667 ? 1 ? (103 ? 1)[(103 ) 666 ? (103 ) 665 ? ? ? 103 ? 1]

所以 10 ? 1(? 1001 ? 01 。 ) 整除 10 ? ? ?
2000 个 0

2.对正整数 n ,记 S (n) 为 n 的十进制表示中数码之和。证明:9 | n 的充要条件是 9 | S (n) 。

5

初等代数选讲-----第二讲

证明: 设 n ? ak ?10k ? ? ? a1 ?10 ? a0 (这里 0 ? ai ? 9 , 且 ak ? 0 ) , 则 S (n) ? a0 ? a1 ? ? ? an , 于是有 n ? S (n) ? ak ? (10k ? 1) ? ? ? a1 ? (10 ? 1) ①

对于 1 ? i ? k ,知 9 | (10i ? 1) ,故①式右端 k 个加项中的每一个都是 9 的倍数,从而由整 除的性质可知它们的和也能被 9 整除,即 9 | (n ? S (n)) 。由此可易推出结论的两个方面。 3.设 k ? 1 是一个奇数,证明:对于任意正整数 n ,数1k ? 2 k ? ? ? n k 不能被 n ? 2 整除。 证明: n ? 1 时,结论显然成立。设 n ? 2 ,记 A ? 1k ? 2k ?

? nk ,则

2 A ? 2 ? (2 k ? n k ) ? (3k ? (n ? 1) k ) ? ? ? (n k ? 2 k ) 。
由 k 是正奇数,从而结于每一个 i ? 2 ,数 i k ? (n ? 2 ? i) k 被 i ? (n ? 2 ? i) ? n ? 2 整除, 故 2 A 被 n ? 2 除得余数为 2,从而 A 不可能被 n ? 2 整除(注意 n ? 2 ? 2 ) 。 4.设 m, n 是正整数, m ? 2 ,证明: ( 2 ? 1) ( 2 ? 1 ) 。
m n

证明:首先,当 n ? m 时,易知结论成立。事实上, m ? n 时,结论显然;当 n ? m 时,结 果可由 2 ? 1 ? 2
n m ?1

? 1 ? 2 m ? 1 推出来(注意 m ? 2 ) 。

最后, n ? m 的情形可化为上述特殊情形:
n mq r r 由带余除法 n ? mp ? r ,0 ? r ? m 而 q ? 0 ,于是 2 ? 1 ? (2 ? 1)2 ? 2 ? 1 ,由 n 是正

整数,则 x ? y ? ( x ? y)(x
n n

n?1

? x n?2 y ? ? ? xy n?2 ? y n?1 ) 知: (2 m ? 1) | (2 mq ? 1) ;
,从 (2 r ? 1) (注意 r ? 0 时结论易证)

m 而 0 ? r ? m ,故由上面证明了的结论知 (2 ? 1)

而当 n ? m 时,也有( 2 ? 1 ) ( 2 ? 1 ) ,这就证明了本题的结论。
m n

5.设正整数 a, b, c, d 满足 ab ? cd ,证明: a ? b ? c ? d 不是质(素)数。

a d m a m a ? ? 其中 (m, n) ? 1 。由 ? 意味着有理数 的分子、 c b n c n c m 分母约去了某个正整数 u 后得既约分数 ,因此, a ? mu , c ? nu ① n
证法一:由 ab ? cd ,可设 同理,存在正整数 v 使得 b ? nv, d ? mv 因此, a ? b ? c ? d = (m ? n)(u ? v) 是两个大于 1 的整数之积,从而不是素数。 注:若正整数 a, b, c, d 适合 ab ? cd ,则 a, b, c, d 可分解为①及②的形式,这一结果在某些 问题的解决中很有作用。 ②

6

初等代数选讲-----第二讲

cd cd (a ? c)( a ? d ) ?c?d ? ,因此 a ? b ? c ? d ? a ? , a a a ( a ? c )( a ? d ) 因为 a ? b ? c ? d 是整数,故 也是整数。 a
证法二:由 ab ? cd ,得 b ? 若它是一个素数,设为 p ,则由 (a ? c)(a ? d ) ? ap ③

可 见 p 整 除 (a ? c)(a ? d ) , 从 而 素 数 p 整 除 a ? c 或 a ? d 。 不 妨 设 p | a ? c , 则

a ? c ? p ,结合③推出 a ? d ? a ,而这是不可能的(因为 d ? 1 ) 。
6.求出有序整数对( m, n )的个数,其中 1 ? m ? 99 ,1 ? n ? 99 , (m ? n) 2 ? 3m ? n 是 完全平方数。 解:由于 1 ? m ? 99 , 1 ? n ? 99 可得:

(m ? n) 2 ? 3m ? n < (m ? n) 2 ? 4(m ? n) ? 4 ? (m ? n ? 2) 2 。
又 (m ? n) 2 ? (m ? n) 2 ? 3m ? n ,于是 (m ? n) 2 ? (m ? n) 2 ? 3m ? n ? (m ? n ? 2) 2 若 (m ? n) 2 ? 3m ? n 是完全平方数,则必有 (m ? n) 2 ? 3m ? n = (m ? n ? 1) 2 。 然而 (m ? n) 2 ? 3m ? n = (m ? n ? 1) 2 ? n ? m ? 1, 于是必有 n ? m ? 1 ? 0 , 即 m ? n ? 1, 此时 n ? 2,3,?,99 , m ? 1,2,?,98 。所以所求的有序整数对( m, n )共有 98 对:

(m, n) ? (1,2), (2,3), (3,4),?, (98,99) 。
7.证明:若正整数 a , b 满足 2a ? a ? 3b ? b ,则 a ? b 和 2a ? 2b ? 1 都是完全平方数。
2 2

2 2 2 证法一:已知关系式即为 2a ? a ? 3b ? b ? 2(a ? b ) ? (a ? b) ? b
2 2 2 ( 2a ? 2b ? 1 )= b ?( a ? b )



若 a ? b ? 0 (或者说 a , b 中有一个为 0 时) ,结论显然。 不妨设 a ? b 且 ab ? 0 ,令 (a, b) ? d ,则 a ? a1d , b ? b1d , (a1 , b1 ) ? 1 从而 a ? b = (a1 ? b1 )d ,将其代入①得 2a1 d ? a1 ? b1 ? 3b1 d 因为 d | 2a1 d ,所以 d | (a1 ? b1 ) ,从而 d ? a1 ? b1 ; 而②式又可写成 (a1 ? b1 ) (2a1 ? 2b1 ? 1) ? b1d ;
2

2

2



2

因为 (a, b) ? d 且 (a1 , b1 ) ? 1 ,所以 (a1 ? b1 , b1 ) ? 1 ? (a1 ? b1 )

7

初等代数选讲-----第二讲

所以 (a1 ? b1 ) | d ,从而 a1 ? b1 ? d 。 所以 d ? a1 ? b1 ,所以 a ? b = (a1 ? b1 )d ? d 2 ,从而 a ? b 为完全平方数。 所以 2a ? 2b ? 1 ?

b2 b ? ( ) 2 也是完全平方数。 2 d d
2 2

证法二:已知关系式即为 2a ? a ? 3b ? b ? 2(a 2 ? b 2 ) ? (a ? b) ? b 2
2 ( 2a ? 2b ? 1 )= b ?( a ? b )



论证的关键是证明正整数 a ? b 与 2a ? 2b ? 1 互素。 记 d ? ( a ? b , 2a ? 2b ? 1 ) 。若 d ? 1 ,则 d 有素因子 p ,从而由①知 p | b 2 。因为 p 是 素数,故 p | b ,结合 p | (a ? b) 知 p | a ,从而由 p | 2a ? 2b ? 1 得 p | 1,这是不可能的。 故 d ? 1 ,从而由①推知正整数 a ? b 与 2a ? 2b ? 1 都是完全平方数。 8.证明不存在正整数 n ,使 2n2+1,3n2+1,6n2+1 都是完全平方数。 证明:假设存在这样的正整数 n ,使 2n2+1,3n2+1,6n2+1 都是完全平方数,那么 (2n2+1) (3n2+1) (6n2+1)也必定是完全平方数。 而(2n2+1) (3n2+1) (6n2+1)=36n6+36n4+11n2+1;

(6n 3 ? 3n) 2 ? 36n6+36n4+9n2; (6n 3 ? 3n ? 1) 2 ? 36n6+36n4+12n3+9n2+6n+1;
所以 (6n ? 3n) ? (2n2+1) (3n2+1) (6n2+1) < (6n ? 3n ? 1) 与 (2n2+1) (3n2+1) (6n2+1)
3 2 3 2

为完全平方数矛盾。
? 1 ? 5 ?n ? 1 ? 5 ?n ? + 9.数列 ? f n ? 的通项公式为 f ? 1 ?? ? ,n?Z . ? ? ? ? ? n ? ? ? ? 2 2 5 ?? ? ? ? ? ??
2 n 记 Sn ? C1 n f1 +Cn f 2 +Cn f n ,求所有的正整数 n ,使得 Sn 能被 8 整除.

解:记 ? ?

1? 5 1? 5 ,? ? ,则 2 2
1 n i i 1 n i i i C ? ? ? ? Cn ?? ? ? i ? ? ? ? ? n 5 i ?1 5 i ?0 1 ? n i i n i i? 1 ? n n 1 ? ? ? ? ?1 ? ? ? ? ? ? ? Cn? ? ? Cn ? ? ? ? 5 ? i ?0 5? i ?0 ?

Sn ?    ?

n n 1 ?? 3 ? 5 ? ? 3 ? 5 ? ? ?? ?    ? ? ? ?? ? 2 ? ? ? 2 5 ?? ? ? ? ? ??

注意到

3? 5 ? 2

3 ? 2

5 ? 3,

? 3 2
8

?

5 ?3 5 ? 1 可得 , 2

初等代数选讲-----第二讲

? 3? 5 ? ? 3? 5 ? 1 ? ?? Sn ? 2 ? ? ? ? ? ?? ? 2 ? ? 2 ? 5 ? ?? ? ? ? ? ?? ? 3Sn ?1 ? Sn         ? ??
n ?1

n ?1

? ?? 3 ? 5 ? ? 3 ? 5 ? ? ?? 3 ? 5 ? n ? 3 ? 5 ? n ? ? ? ?? ?? ?? ?? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 ? ? 2 ?? ?? ?? 2 ? ? 2 ? ? ? ? ? ? ? ? ??

因此,Sn+2 除以 8 的余数,完全由 Sn+1、Sn 除以 8 的余数确定
1 1 2 S1 ? C1 f1, S2 ? C2 f1 ? C2 f2 ? 3 ,故由(*)式可以算出 ?Sn ? 各项除以 8 的余数依次是 1,3,

0,5,7,0,1,3,……,它是一个以 6 为周期的数列,从而 8 Sn ? 3 n 故当且仅当 3 n时, 8 Sn . 10、 设 x, y 是正整数, x ? y 且 x ? y ? 667,它们的最小公倍数是最大公约数的 120 倍, 求 x, y 。 解:设 ( x, y) ? d ,则 x ? m d, y ? nd ,其中 (m, n) ? 1 且 m ? n ,于是 [ x, y ] ? m nd 。

? ?m d ? nd ? 667 ?(m ? n)d ? 23? 29 即? 3 ? 120 ? mn ? 2 ? 3 ? 5 ? ? d 由 m ? n 及(2)可得:
所以 ? m nd

(1) ( 2)

? m ?1 ?m ? 2 ;? ; ? ?n ? 120 ?n ? 60

? m ? 3 ? m ? 4 ? m ? 5 ? m ? 6 ? m ? 8 ?m ? 10 。 ;? ;? ;? ;? ;? ? ?n ? 40 ?n ? 30 ?n ? 24 ?n ? 20 ?n ? 15 ? n ? 12
? m ? 5 ?m ? 8 ;? ; ?n ? 24 ?n ? 15

由(1)可知只能取 ?

, y ? 552 或 x ? 232, y ? 435。 从而 d ? 23 或 29,故 x ? 115
11、设 m, n ? 0 , mn | (m ? n ) ,则 m ? n 。
2 2

证明:设 (m, n) ? d ,则 m ? m1 d , n ? n1d ,其中 (m1 , n1 ) ? 1 。于是,已知条件转化为
2 2 2 2 2 m1n1 | (m1 ? n1 ) ,故更有 m1 | (m1 ? n1 ) ,从而转化为 m1 | n1 ,但是 (m1 , n1 ) ? 1 ,故

(m1 , n1 ) ? 1,结合 m1 | n1 ,知必有 m1 ? 1 ,同时 n1 ? 1 ,因此 m ? n 。
2 2

12.设正整数 a, b, c 的最大公约数是 1,并且

ab ? c ,证明 a ? b 是一个完全平方数。 a ?b

b ? b1d , 证明: 设 (a, b) ? d , 则 a ? a1d , 其中 (a1 , b1 ) ? 1 , 由于 (a, b, c) ? 1 , 故 (b, c) ? 1 ,
现在问题中的等式可以转化为 da1b1 ? ca1 ? cb1 ①

由此可见 a1 整除 cb1 。因为 (a1 , b1 ) ? 1 ,故 a1 | c ,同样可得 b1 | c ,再由 (a1 , b1 ) ? 1 便可以
9

初等代数选讲-----第二讲

推出 a1b1 | c 。设 c ? a1b1k ,其中 k 是一个正整数。一方面,显然 k 整除 c ;另一方面,结 合①式,得 d ? k (a1 ? b1 ) ,故 k | d ,从而 k | (c, d ) ,但 (c, d ) ? 1 ,故 k ? 1 。 因此, d ? a1 ? b1 ,故 a ? b ? d (a1 ? b1 ) ? d 2 ,这样就证明了 a ? b 是一个完全平方数。 13. a , b 都是正整数,是否存在整数 p, q 使得对任意的正整数 n , p ? na 与 q ? nb 互质? 解:令 L ? [a, b] , r ?

L L , s ? ,则 (r , s) ? 1,于是存在整数 x, y 使得 rx ? sy ? 1 , a b

令 p ? x, q ? ? y , 则对任意的正整数 n , 设 dn ? ( p ? na, q ? nb) , 有 dn | (r ( p ? na) ? s(q ? nb)) 即 dn | (rp ? sq ? n(ra ? sb)) ,而 rp ? sq ? rx ? sy ? 1, ra ? L ? sb ,所以 dn | 1 ? dn ? 1 , 即对任意的正整数 n , ( p ? na , q ? nb )=1。 14. 已知 f ( x) ? x 2002 ? x 2001 ? 1 ,证明:对于任意的正整数 m ,都有

m, f (m), f ( f (m)), f ( f ( f (m))),? 两两互素。
证明:设 pn ( x) ? f ( f ( f (?( x)?))) (其中 f 出现 n 次) 。由 f (0) ? 1, f (1) ? 1 ,故对于

?n ? N 有 pn (0) ? 1 , 则 pk ( x) 是含有 0 次项 pk (0) ? 1 的多项式。 因此,pn (m) 除以 m ? 1
的余数为 1。 设整数 d ? 1 可整除 pk (m) 和 pk ?l (m) , 又 pk ?l (m) = pl ( pk (m)) , 则当 pl ( pk (m)) 除以 pk (m) 时余数为 1,即 pk ?l (m) = Q ? pk (m) +1。所以 d | 1 ,矛盾! 从而可知 m, f (m), f ( f (m)), f ( f ( f (m))),? 两两互素。

15.求出所有的正整数对 (m, n) ,使得
3 3

n3 ? 1 是一个整数。 m n?1
3 3 3 3 3

解:由于 (m , mn ? 1) ? 1 且 mn? 1 | n ? 1 ? mn? 1 | m (n ? 1) ? mn ? 1 | m n ? 1 ? m ? 1

? mn ? 1 | m3 ? 1,所以 m, n 是对称的。不妨设 m ? n 。
当 m ? n 时,则

n3 ? 1 n 2 ? n ? 1 1 ? ? n? ? N * ? n ? 2 ,从而 m ? n =2; 2 n ?1 n ?1 n ?1

当 m ? n 时,若 n ? 1 时,则有 m ? 1 | 2 ,所以 m ? 2 或 3; 若 n ? 2 时,由于

n3 ? 1 * 3 是一个整数,从而 ?k ? N 使得 n ? 1 ? (kn ? 1)(mn? 1) m n?1
10

初等代数选讲-----第二讲

即 kn ? 1 ?

1 n3 ? 1 n3 ? 1 1 ?n? ? 2 ,所以 kn ? 1 < 1 ? 。 n ?1 n ?1 m n?1 n ?1

* 又由于 n ? 2 , k ? N ,所以 k ? 1 。





n3 ? 1 ? (n ? 1)(mn? 1) ? mn3 ? n ? mn? 1 , 从 而

m?

n2 ?1 2 ? n ?1? ? N * 得 n ? 2 或 3,所以 m ? 5 ; n ?1 n ?1

综上知所有的 (m, n) 为(2,2),(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).

16.已知 a, b, m, n ? N * ,且 (a, b) ? 1, a ? 2 ,试问 a n ? b n | a m ? b m 的充要条件是 n | m 吗? 分析: 因为 a k ? b k ? a k ?n (a n ? b n ) ? b n (a k ?n ? b k ?n ) , 所以 a n ? b n | a k ? b k ? a n ? b n | a k ?n ? b k ?n ; 又 a r ? b r ? a r ?n (a n ? b n ) ? b n (a r ?n ? b r ?n ) ,所以 a n ? b n | a r ? b r ? a n ? bn | a r ? n ? br ? n ; 令 m ? nq ? r (0 ? r ? n) ,则有 an ? bn | anq ? r ? bnq ? r ? a n ? bn | a( q ?1) n ? r ? b( q ?1) n ? r

? an ? bn | a( q ?2) n ? r ? b( q ?2) n ? r ? ? ? an ? bn | ar ? (?1)q br
r q r 又因为 n ? r ,所以 a ? (?1) b ? a ? b
n n

n n m m 从而上式 ? r ? 0 且 q 为奇数,即 a ? b | a ? b 的充要条件是 n | m 且 2 3 17.我们知道 2 ? 1 ? 9 有 1 个质因子,且 3 | 2 ? 1 ;
3

m 为奇数。 n

23 ? 1 ? 513 ? 33 ?19 有 2 个质因子,且 33 | 23 ? 1
……………… 如此下去, 我们可以猜想:k ? N , 2
*
3k 3 k ?1 且 3 | 2 ? 1。 试证明之。 ? 1 至少有 k 个质因子,
k

2

2

证明:令 ak = 2

3k

? 1 ,则 ak = 3k ?1 bk ,即要证 bk 是整数且有 k ? 1 个质因子。下用数学归

纳法证明 bk 是整数。

k ? 1 时,结论显然; 假设 n ? k 时,成立;
当 n ? k +1 时,因为 ak ?1 ? ( ak -1)3+1= ak 3-3 ak 2+3 ak ; 因为 3
k ?1

| ak ,所以 3k ?2 | ak ?1 ,即 bk ?1 是整数。

11

初等代数选讲-----第二讲

下证 bk ?1 至少有 k 个质因子。

ak ?1 ? 3k ? 2 bk ?1 = ak 3-3 ak 2+3 ak =( 3 k ?1 bk )3-3( 3 k ?1 bk )2+3( 3 k ?1 bk ).
2 因为 bk ?1 = bk ( 32k ?1 bk ? 3k ?1 bk ?1 ),令 ck ? 32k ?1 bk2 ? 3k ?1 bk ?1 ,则 bk ?1 = bk ck

由于( ck ,3)=1,所以( ck , bk )=1,从而 ck 必有异于 bk 质因子的质因子, 所以 bk ?1 至少有 k 个质因子。证毕!

18.证明:如果 p 和 p ? 2 都是大于 3 的素数,则 6 是 p ? 1 的因子。 证明:因为 p 是奇数,所以 2 是 p ? 1 的因子。又因为 p , p ? 1 , p ? 2 除以 3 的余数各 不相同,而 p 与 p ? 2 都不能被 3 整数。于是 6 是 p ? 1 的因子。 19.设 m ? n ? 0 ,证明: (22 ? 1) | (22 ? 1) ; 解:由 2 又因为 2
n
n m

2m

? 1 ? (22

n ?1

? 1)[(22 ) 2
n

n ?1

m ? n ?1

? ? ? 22
n

n ?1

? 1] ,故 (22
n ?1

n ?1

。 ?1) |( 2 2 ? 1 )

m

2n ?1

? 1 ? (2 2 ? 1) (2 2 ? 1) ,从而 (2 2 ? 1) | (22
m

n

? 1) ,于是由整除的性质知

(22 ? 1) | (22 ? 1) 。
20.证明:对于任意正整数 n ,数 1 证明:只需证 2( n ? 2 )2( 1
n n
2005

2005

? 22005 ? ? ? n2005

不能被 n ? 2 整除。

? 22005 ? ? ? n2005 )即可。
n?1

因为若 n 是正整数,则 x ? y ? ( x ? y)(x 若 n 是正奇数,则 x ? y ? ( x ? y)(x
n n n?1

? x n?2 y ? ? ? xy n?2 ? y n?1 ) ;

? x n?2 y ? ? ? xy n?2 ? y n?1 ) ;

故n ? 2|2

2005

? n2005 ; n ? 2 | 32005 ? (n ? 1)2005 ,……, n ? 2 | n 2005 ? 2 2005
2005

所以 n ? 2 |2( 2

? ? ? n 2005 ) 。
2,所以 n ? 2 2( 2
2005

又因为 n ? 2 ? 3 ? 2 ,所以 n ? 2 即( n ? 2 )2( 1
2005

? ? ? n 2005 )+2

? 22005 ? ? ? n2005 )命题得证。
n n n

21.已知 n 为正奇数,求证: 60 | 6 ? 3 ? 2 ? 1。 证明:因为若 n 是正整数,则 x ? y ? ( x ? y)(x
n n n?1

? x n?2 y ? ? ? xy n?2 ? y n?1 ) ;

12

初等代数选讲-----第二讲

若 n 是正奇数,则 x n ? y n ? ( x ? y)(x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) ; 所以 3 | 6 n ? 3n , 3 | 2 n ? 1 ,从而 3 | 6 n ? 3n ? 2 n ? 1 ;

4 | 6 n ? 2 n , 4 | 3n ? 1 ,从而 4 | 6 n ? 3n ? 2 n ? 1 ;

5 | 6 n ? 1, 5 | 3n ? 2 n ,从而 5 | 6 n ? 3n ? 2 n ? 1 ;
又 (3,4,5) ? 1 且 3 ? 4 ? 5 ? 60 ,所以 60 | 6 n ? 3n ? 2 n ? 1。

22.设 a、b、c 为满足不等式 1<a<b<c 的整数,且(ab-1)(bc-1)(ca-1)能被 abc 整除,求所有可能数组(a,b,c).
解 ∵(ab-1)(bc-1)(ca-1)=a b c -abc(a+b+c)+ab+ac+bc-1,① ∵abc|(ab-1)(bc-1)(ca-1). ∴存在正整数 k,使 ab+ac+bc-1=kabc, ②
2 2 2

k=









∴k=1.

若 a≥3,此时 1= 已知 a>1. ∴只有 a=2.

-



矛盾.

当 a=2 时,代入②中得 2b+2c-1=bc,即 ∴0<b<4,知 b=3,从而易得 c=5.

1=



说明:在此例中通过对因数 k 的范围讨论,从而逐步确定 a、b、c 是一项重要解题技巧. 23.若 n ? N , m 是奇数,则 (2 ? 1,2 ? 1) ? 1 。
m n

分析: 要证明 2 ? 1 与 2 ? 1 互质, 我们只需要证明它们的公因子为 1 即可, 但是这对于 m, n
m n

不好处理,由 m 为奇数这一条件,我们可以想到 2 | 2
n m

m

mn

? 1 从而找到思路。
m n

mn mn 证明:由于 m 为奇数,故 2 ? 1 | 2 ? 1 ,又 2 ? 1 | 2 ? 1 ,从而( 2 ? 1 , 2 ? 1 ) ?

13

初等代数选讲-----第二讲

( 2 mn ? 1, 2

mn

mn ? 1) ,而( 2 mn ? 1, 2 ? 1 )=( 2 mn ? 1, 2)=1,故 (2 m ? 1,2 n ? 1) ? 1 。

24.若 17|(2a+3b),试证:17|(9a+5b). 证明:注意到 2(9a+5b)=9(2a+3b)-17b,于是 17|2(9a+5b).但是(17,2)=1,即得 17|(9a+5b). 25.设 n , a 是正整数,若 n a 不是整数,则必为无理数。

c c 证明: 设 n a 是非整数的有理数, 则可设 n a ? , b ? 1, (b, c) ? 1 , 于是 a ? n 。 因为 (b, c) ? 1 b b cn 故可知 (b , c ) ? 1 。但 b ? 1 ,因而 b | c 。这与 n ? a 是整数矛盾!证毕。 b
n n
n

n

n

n

14


更多相关文档:

第二讲 整除

第二讲 整除_学科竞赛_高中教育_教育专区。http://www.ehappystudy.com 快乐学习,尽在苏州中学网校 数学奥赛辅导 第二讲 整除 知识、方法、技能 整除是整数的...

第二讲 整除

第二讲 整除_学科竞赛_高中教育_教育专区。高中竞赛初等数论选讲,共6讲初等代数选讲---第二讲 第二讲 整除 【基础知识】 一.整除的概念及其性质 1、 定义:...

第二讲 数的整除

第二讲 数的整除_学科竞赛_小学教育_教育专区。第二讲 学习目标: 数的整除 1. 让学生再合作与交流中掌握数的整除的有关概念,明确概念之间的区别与联系; 2. ...

第二讲 数的整除性

第二讲 数的整除性_学科竞赛_小学教育_教育专区。第二讲一、填空题 数的整除性(二) 1. 四位数“3AA1”是 9 的倍数,那么 A=___. 2. 在“25□79 这个...

数学奥赛辅导 第二讲 整 除

数学奥赛辅导 第二讲 整除_学科竞赛_高中教育_教育专区。数学奥赛辅导整除知识、方法、技能 第二讲 整除是整数的一个重要内容, 这里仅介绍其中的几个方面: 整数的...

第二讲 数的整除特征

方法决定速度 习惯决定成绩 第二讲 【典型例题】 数的整除特征(2) 例 1:判断哪些数能被 7 整除,哪些能被 11 整除,哪些能被 13 整除。 143 625790 111605...

第二讲 整除

第二讲 整除 分享到: X 分享到: 使用一键分享,轻松赚取财富值, 了解详情 嵌入播放器: 普通尺寸(450*500pix) 较大尺寸(630*500pix) 预览复制 收藏此文...

第2讲 数的整除

第2讲 数的整除_学科竞赛_小学教育_教育专区。第二讲 数的整除 知识要点定义:设 a,b 为二整数,且 b≠0,如果有一整数 c,使 a=bc,则称 b 是 a 的...

第二讲 数的整除(2)

第二讲 数的整除复习 【知识点】 1、素数和合数 一个数,如果只有1和它本身两个因数,这样的数叫做素数,也叫质数. 一个数,如果除了1和它本身以外还有别的...

第二讲 数的整除

第二讲 数的整除_五年级数学_数学_小学教育_教育专区。数学数的整除【知识点回顾】 数的整除特征: 1、能被 9 整出的书的特征:各个数位数字之和是 9 的倍...
更多相关标签:
李丰吉特巴教学第二讲 | 孙全圣画牡丹第二讲 | 王建军慢四教学第二讲 | 第二讲专家教师的特征 | 乾隆扇分解教学第二讲 | 谈谈历史安阳 第二讲 | 工匠精神读本第二讲 | 修身贤文第二讲观后感 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com