haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

初中数学竞赛专题选讲 数的整除(三)(含答案)

发布时间:2014-04-14 16:55:01  

初中数学竞赛专题选讲

数的整除(三)

一、内容提要

在《数的整除(一)》和《数的整除(二)》中,分别介绍了数的整除特征和运用因式分解法解答数的整除问题,本讲介绍应用“同余”方面的知识.

一. 同余的概念 两个整数a和b被同一个正整数m除,所得的余数相同时,称a,关于模m 同余.记作a≡b(mod m).

如:8和15除以7同余1,记作8≡15(mod 7), 读作8和15关于模7同余. ∵2003=7×286+1,

∴2003≡1 (mod 7);

∵-7和6对于模13同余6(余数是非负数)

∴-7≡6(mod 13);

∵35和0除以5,余数都是0(即都能整除)

∴35≡0(mod 5).

二. 用同余式判定数的整除

若a≡b(mod m), 则m|(a-b).

即a-b≡0(mod m)?m|(a-b).

例如:11≡25(mod 7)?7|(25-11); 或 7|(11-25).

∵25+35≡2+3≡0 (mod 5),

∴5|25+35.

三. 同余的性质 (注意同余式与等式在变形中的异同点)

1. 传递性: a?b(modm)?

b?c(modm)???a?c(momd).

2. 可加可乘性:a?b(modm),??a?c?b?d(modm);

c?d(modm).?????ac?bd(modm).

推论 可移性:a≡b+c (mod m)?(a-b)≡c(mod m).

可倍性:a≡b(mod m)?ka≡kb(mod m) (k为正整数).

可乘方:a≡b(mod m)? an≡bn(mod m) (n为正整数).

- 1 - b

3. 当d 是a, b, m的正公因数时, a≡b(mod m)?abm?(mod ). ddd 如:2是20,26,6的正公因数, 20≡26(mod 6)?10?13(mod 3).

四. 根据抽屉原则:任给m+1个整数,其中至少有两个数对于模m同余. 即至少有两个,其差能被m 整除.

例如:任给5个数a, b, c, d, e.其中至少有两个,它们的差能被4整除. ∵除以4的余数只有0,1,2,3四种.

∴5个数除以4至少有两个同余.

二、例题

例1. 已知:69,90,125除以正整数n有相同的余数.

求:n的值

解:∵69≡90(mod n), 90≡125(mod n).

∴ n|(90-69), n|(125-90).

而21,35的最大公约数是7, 记作(21,35)=7 (7是质数).

∴n=7

例2. 求388除以5的余数.

解:∵38≡3 (mod 5),

∴388≡38≡(32)4≡(-1)4≡1 (mod 5).

(注意 9除以5余4,-1除以5也是余4,∴32≡-1 (mod 5)

例3. 求7的个位数字.

解: ∵74k+n与7n的个位数字相同, 且9≡1 ( mod 4),

∴ 99≡19 ≡1 (mod 4).

∴7与71的个位数字相同都是7.

例4. 求证:7|(22225555+55552222).

证明:∵22225555+55552222=(22225)1111+(55552)1111

∵2222=7×317+3 , 5555=7×793+4.

∴2222≡3 ( mod 7); 5555≡4 (mod 7).

∴22225≡35≡5(mod 7); 55552≡42≡2 (mod 7). 9999

- 2 -

∴22225+55552≡5+2≡0 ( mod 7).

即22225≡-55552 (mod 7).

∴(22225)1111≡(-55552)1111≡-(55552)1111 (mod 7).

∴22225555+55552222≡0 (mod 7).

∴7|(22225555+55552222).

例5. 求使32n-1能被5整除的一切自然数n.

解:∵32≡-1 (mod 5) ,

∴(32)n≡(-1)n (mod 5).

32n-1≡(-1) n-1 (mod 5)

∵当且仅当n为偶数时,(-1) n-1=0.

∴使32n-1能被5整除的一切自然数n是非负偶数

例6. 已知:a, b, c是三个互不相等的正整数.

求证:a3b-ab3, b3c-bc3, c3a-ca3三个数中,至少有一个数能被10整除.

证明:用同余式判定整除法证明

当正整数n的个位数是0,1,4,5,6,9时,n3 的个位数也是0,1,4,5,6,9.

∴这时n3≡ n (mod 10);

当正整数n的未位数为2,3,7,8时,n3 的个位数分别是8,7,3,2.

∵8与-2,7与-3,3与-7,2与-8,除以10是同余数,

∴这时n3≡-n (mod 10);

把三个正整数a, b, c按个位数的情况,分为上述两类时,则至少有两个属于同一类.

设a, b的末位数是同一类,那么

a3b-ab3≡ab-ab≡0 (mod 10);或a3b-ab3≡(-a)b-a(-b)≡0 (mod 10).

∴ 10| (a3b-ab3)

三、练习

1. 三个数33,45,69除以正整数N有相同余数,但余数不是0,那么N=_______.

2. 求7的个位数字.

3. 求37459277除以19的余数; 41989除以9的余数.

4. 求19891990÷1990的余数.

5. 四个数2836,4582,5164,6522都被同一个正整数除,所得的余数都相同且不是

- 3 -

0,求除数和余数.

6. 求证:7|(33334444+44443333).

7. 已知:正整数n>2 . 求证:111?1?3 (mod 4). ???

n个

8. 任给8个整数,其中必有两个,它们的差能被7整除,试证之.

9. 求使2n+1能被3整除的一切自然数n.

10. 已知 69,90,125除以N (N>1) 有同余数,那么对于同样的N,81同余于( )

(A)3. (B)4. (C)5. (D)7. (E)8.

参考答案

1. N=12,6,2.(舍去3,∵余数是0).解法仿例1.

2. 个位数字是3.∵7≡-1(mod 4), ∴ 777≡(-1)77(mod 4)??仿例3

3. 余数是18和1. ∵37≡-1 (mod 19) ∴原式≡-1 ≡18 (mod 19); 41989=(43)663 64≡1(mod 9) 64663≡1663 ≡1.

4. 余数是1. ∵1989≡-1 (mod 1990) ∴19891990≡(-1)1990≡1 (mod 1990).

5. 根据题意 2836≡4582≡5164≡6522≡r (mod m)

而且4582-2836=1746, 6522-5164=1358.

∴ m| 1746, 且m|1358, (1746,1358)=2×97

∴m=194, 97, 2 (2不合题意.舍去)

答:除数为194, 余数是120或除数为97, 余数是23

6. ∵ 33334444+44443333≡14444+(-1)3333≡0 (mod 7).

7. 11????11?11????1100+11≡11≡3 (mod 4).

n个n?2个

8. 8个正整数分别除以7,必有两个或两个以上是同余数

9. ∵2≡-1 (mod 3) ∴2n≡(-1)n (mod 3)

2n+1≡(-1)n+1 (mod 3)

当且仅当n奇数时, (-1)n+1≡0

∴能被3整除的一切正整数n是奇数

10. (B).

- 4 -

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com