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

第25讲 同余式-初二奥数教材

发布时间:2014-01-28 09:46:51  

第二十五讲* 同余式

数论有它自己的代数,称为同余理论.最先引进同余的概念与记号的是数学王子高斯.

先看一个游戏:有n+1个空格排成一行,第一格中放入一枚棋子,甲乙两人交替移动棋子,每步可前移1,2或3格,以先到最后一格者为胜.问是先走者胜还是后走者胜?应该怎样走才能取胜?

取胜之道是:你只要设法使余下的空格数是4的倍数,以后你的对手若走i格(i=1,2,3),你走4-i格,即每一次交替,共走了4格.最后只剩4个空格时,你的对手就必输无疑了.因此,若n41,2或3时,那么先走者甲胜;若n除以4的余数是0胜.

而要关心这个数用m1999年有365天,365=7×52+1们关心的也是余数.这一讲中,的应用.

定义1 b所得的余数相同,则称a与b对模m,

并读作a

b1,有

1+r,b=mq2+r.

12,

-b.

m|a-b,设

a=mq1+r1,b=mq2+r2,0≤r1,r2≤m-1,

则有m|r1-r2.因|r1-r2|≤m-1,故r1-r2=0,即r1=r2.

于是,我们得到同余的另一个等价定义:

定义2 若a与b是两个整数,并且它们的差a-b能被一正整数m整除,那么,就称a与b对模m同余.

同余式的写法,使我们联想起等式.其实同余式和代数等式有一些相同的性质,最简单的就是下面的定理1.

定理1 (1)a≡a(modm).

(2) 若a≡b(modm),则b≡a(modm).

(3) 若a≡b(modm),b≡c(modm),则a≡c(modm).

在代数中,等式可以相加、相减和相乘,同样的规则对同余式也成立. 定理2 若a≡b(modm),c≡d(modm),则

a±c≡b±d(modm),ac≡bd(modm).

证 由假设得m|a-b,m|c-d,所以

m|(a±c)-(b±d), m|c(a-b)

a±c≡b±

由此我们还可以得到:若an是自然数,则

a±k≡b,bn.

acc,得到一个正确的同余式a≡

25≡5(mod 10),

5≡1(mod 10).

3 若ac≡bc(modm),且(c,m)=1,则

a≡b(modm).

证 由题设知

ac-bc=(a-b)c=mk.

由于(m,c)=1,故m|a-b,即a≡b(modm).

定理4 若n≥2,

a≡b(modm1),

a≡b(modm2),

????

a≡b(modmn),

且M=[m1,m2,?,mn]表示m1,m2,?,mn的最小公倍数,则

a≡b(modM).

前面介绍了同余式的一些基本内容,些具体问题.

m整除a,只需证a≡0(modm)即可.

例1 求证:

(1)8|(551999+17);

(2) 8(32n+7);

(3)17|(191000-1).

证 (1)因55≡-所以8),551999+17≡-1+17=16≡0(mod 8).

(2)32=93,所以32n+7≡1+7≡0(mod 8),即8|(32n+7) 4=16≡-1(mod 17),所以191000=(194)250≡

17|(191000-1).

2n-1为7的倍数的所有正整数n.

23≡8≡1(mod 7),所以对n按模3进行分类讨论.

n=3k,则

2n-1=(23)k-1=8k-1≡1k-1=0(mod 7);

(2) 若n=3k+1,则

2n-1=2·(23)k-1=2·8k-1

≡2·1k-1=1(mod 7);

(3) 若n=3k+2,则

2n-1=22·(23)k-1=4·8k-1 ≡4·1k-1=3(mod 7).

所以,当且仅当3|n时,2n-1为7的倍数. 例3 对任意的自然数n,证明

A=2903n-803n-464n+261n

能被1897整除.

证 1897=7×271,7与271互质.因为

2903≡5(mod 7), 803≡5(mod 7),464≡2(mod 7), 261≡

所以

A=2903n-nn ≡-5n-,

故7|A

, , 193(mod 271),

故271|A.因(7,271)=1,所以1897整除A.

例4 把1,2,3?,127,128这128个数任意排列为a1,a2,?,a128,计算出

|a1-a2|,|a3-a4| ,?,|a127-a128|,

再将这64个数任意排列为b1,b2,?,b64,计算

|b1-b2|,|b3-b4|,?,|b63-b64|.

如此继续下去,最后得到一个数x,问x是奇数还是偶数? 解 因为对于一个整数a,有

|a|≡a(mod 2), a≡-a(mod 2),

所以

b1+b2+?+b64

=|a1-a2|+|a3-a4|+?+|a127-a128|

≡a1-a2+a3-a4+?+a127-a128

≡a1+a2+a3+a4+?+a127+a128(mod 2),

得到的一个数

x≡a1+a2+?+a128=1+2 =64×129≡0(mod 2),

故x是偶数.

10的余数,求一个数100

例5 99除的余数.

10≡1(mod 9),

k≥1,有

10k≡1k=1(mod 9).

即A被9除的余数等于它的各位数字之和被9除的余数.

说明 (1)特别地,一个数能被9整除的充要条件是它的各位数字之和能被9整除.

(2)算术中的“弃九验算法”就是依据本题的结论.

例6 任意平方数除以4余数为0和1(这是平方数的重要特征). 证 因为

奇数2=(2k+1)2=4k2+4k+1≡1(mod 4),

偶数2=(2k)2=4k2≡0(mod 4),

所以

例7 任意平方数除以8余数为0,1,4(). 证 奇数可以表示为2k+1,从而

奇数2=4k2+. 因为两个连续整数k,k+4k(k+1)是8的倍数,从而

奇数2=8t+1

22=4k).

(1)若

22=0(mod 8).

奇数

21)2=16(t2+t)+4≡4(mod 8),

求余数是同余的基本问题.在这种问题中,先求出与±1同余的数是一种基本的解题技巧.

例8 (1)求33除21998的余数.

(2)求8除72n+1-1的余数.

解 (1)先找与±1(mod 33)同余的数.因为

25=32≡-1(mod 33),

所以 210≡1(mod 33),

21998=(210)199·25·23≡-8≡25(mod 33),

所求余数为25.

(2)因为7≡-1(mod 8),所以

72n+1≡(-1)2n+1=-1(mod 8),

72n+1-1≡-2≡6(mod 8),

即余数为6.

例9 形如

Fn=22n+1,n=0,1,2 的数称为费马数.证明:当n≥.

证 当n≥2时,2n是4n

Fn=22n+t≡1≡ 即Fn 说明 F0=F217,F3=257,F4=65537,

n,Fn都是素数.然而,

他证明了下一个费马数5F5

10

x4+y4+2=5z

没有整数解.

证 对于任一整数x,以5为模,有

x≡0,±1,±2(mod 5),

x2≡0,1,4(mod 5),

x4≡0,1,1(mod 5),

即对任一整数x,

x4≡0,1(mod 5).

同样,对于任一整数y

y4≡0,1(mod 5),

所以 x4+y4+2≡2,3,4(mod 5),

从而所给方程无整数解.

说明 键在于确定所取的模(本例我们取模5)定.

练习二十五

1.求证:17|(191000-1).

2.证明:对所有自然数n,33011).

4.求21000除以

5.求15+551005

651998天又是星期几?

7.求n=135的末三位数字.

2无整数解.

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