初二奧數(shù)教材同余式

同余式

定義1給定一個正整數(shù)m,如果用m去除a,b所得的余數(shù)相同，則

稱a與b對模m同余，記作

a三b(modm),

并讀作a同余b,模m.

若a與b對模m同余，由定義1,有

a=mqi+r,b=mq2+r.

所以a-b-m(qi-q2),

即m|a-b.

反之，若mIa-b,設(shè)

a=mqi+ri,b=mq2+r2,OWn,r2^m-l,

則有m|ri-r2.因Iri-r2IWm-1,故0二0,即ri=rz.

于是，我們得到同余的另一個等價定義：

定義2若a與b是兩個整數(shù),并且它們的差a-b能被一正整數(shù)m整除,

那么，就稱a與b對模m同余.

同余式的寫法，使我們聯(lián)想起等式.其實同余式和代數(shù)等式有一些相

同的性質(zhì)，最簡單的就是下面的定理1.

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

(2)若a三b(modm),則b三a(modm).

(3)若a=b(modm),b三c(modm),則a=c(modm).

在代數(shù)中，等式可以相加、相減和相乘，同樣的規(guī)則對同余式也成立.

定理2若a=b(modm),c=d(modm),則

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

證由假設(shè)得mIa-b,mIc-d,所以

mI(a+c)-(b+d),mIc(a-b)+b(c-d),

即

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

由此我們還可以得到：若a三b(modm),k是整數(shù)，n是自然數(shù)，則

a±k=b±k(modm),

ak=bk(modm),an=bn(modm).

對于同余式ac三bc(modni),我們是否能約去公約數(shù)c,得到一個正確

的同余式a三b(modm)?

在這個問題上，同余式與等式是不同的.例如

25=5(mod10),

約去5得

5=1(mod10).

這顯然是不正確的.但下面這種情形，相約是可以的.

定理3若ac三be(modm),且(c,m)=l,則

a三b(modm).

證由題設(shè)知

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

由于(m,c)=L故mIa-b,即a三b(modni).

定理4若n，2,

a三b(modmi),

a三b(modm2),

a三b(modmn),

且M=[mi,m2,???,表示nh,m2,??-,叫的最小公倍數(shù)，則

a=b(modM).

前面介紹了同余式的一些基本內(nèi)容，下面運用同余這一工具去解決一

些具體問題.

應(yīng)用同余式的性質(zhì)可以簡捷地處理一些整除問題,若要證明m整除a,

只需證a三0(modm)即可.

例1求證：

(1)8I(55.+17)；

(2)8(32"+7)；

(3)17I(191000-1).

證(1)因55三-1(mod8),所以55蚪三-1(mod8),55,+17三-1+17=16

三0(mod8),于是8I(55螞+17).

2

(2)3三9三l(mod8),3"=l(mod8),所以3"+7三1+7三0(mod8),

即8|(32"+7).

44raM

(3)19=2(mod17),19=2=16=-1(mod17),所以19=(19，)250三

(-1)250=1(mod17),于是

17|(191000-1).

例2求使20-1為7的倍數(shù)的所有正整數(shù)n.

解因為2,三8三1(mod7),所以對n按模3進行分類討論.

(1)若n=3k,則

2--1=(23)k-l=8k-l=r-l=0(mod7)；

(2)若n=3k+l,則

2--1=2?(23)k-l=2?8k-l

三2T"-l=l(mod7)；

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

2--1=22?⑵)k-1=4?8k-l

=4-lk-l=3(mod7).

所以，當(dāng)且僅當(dāng)31n時，2"-1為7的倍數(shù).

例3對任意的自然數(shù)n,證明

A=2903--803--464"+26r

能被1897整除.

證1897=7X271,7與271互質(zhì).因為

2903=5(mod7),

803=5(mod7),

464=2(mod7),

261=2(mod7),

所以

A=2903n-803"-464"+26r

=5n-5n-2n+2n=0(mod7),

故71A.又因為

2903=193(mod271),

803=261(mod271),

464=193(mod271),

所以

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

=193n-261n-193n+261n

=0(mod271),

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

例4把1,2,3…，127,128這128個數(shù)任意排列為a”&,…，a儂,

計算出

Id.l~d,2I,I&3-34|,…，|3127-3128I,

再將這64個數(shù)任意排列為b,4，…，鼠，計算

Ibi-b2I,Ib『baI,…，Ib63-b64I.

如此繼續(xù)下去，最后得到一個數(shù)X,問X是奇數(shù)還是偶數(shù)？

解因為對于一個整數(shù)a,有

IaI=a(mod2),a=-a(mod2),

所以

bi+b2H----|-b64

=Iai-a2I+Ia3-a4I+…+Ia^-a^sI

=ai-a2+a3-a4+…+2川田128

,,,

=ai+a2+a3+a4++ai27+ai28(mod2),

因此，每經(jīng)過一次“運算”，這些數(shù)的和的奇偶性是不改變的.最終

得到的一個數(shù)

x三ai+a?+…+ai2s=1+2+…+128

=64X129=0(mod2),

故x是偶數(shù).

如果要求一個整數(shù)除以某個正整數(shù)的余數(shù)，同余是一個有力的工

具.另外，求一個數(shù)的末位數(shù)字就是求這個數(shù)除以10的余數(shù)，求一個數(shù)

的末兩位數(shù)字就是求這個數(shù)除以100的余數(shù).

例5求證：一個十進制數(shù)被9除的余數(shù)等于它的各位數(shù)字之和被9

除的余數(shù).

證設(shè)這個十進制數(shù)A=a?a^j--.aaa^o,因

10=1(mod9),

故對任何整數(shù)kN1,有

10k=r=l(mod9).

因此

a，-aaa

A=ann-r2l0

nn1

=anX10+anlX10-+-+aiX10+a0

=an+an-i+"■+ai+a0(mod9),

即A被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù).

說明(1)特別地，一個數(shù)能被9整除的充要條件是它的各位數(shù)字之和

能被9整除.

(2)算術(shù)中的“棄九驗算法”就是依據(jù)本題的結(jié)論.

例6任意平方數(shù)除以4余數(shù)為0和1(這是平方數(shù)的重要特征).

證因為

奇數(shù)2=(2k+l)2=4k2+4k+l=l(mod4),

偶數(shù)2=(2k)2=4k2=0(mod4),

所以

金神湖2f1(mod4),奇數(shù)；

0(mod4；,偶數(shù).

例7任意平方數(shù)除以8余數(shù)為0,1,4(這是平方數(shù)的又一重要特征).

證奇數(shù)可以表示為2k+l,從而

奇數(shù)2=4k2+4k+l=4k(k+l)+l.

因為兩個連續(xù)整數(shù)k,k+1中必有偶數(shù)，所以4k(k+1)是8的倍數(shù)，

從而

奇數(shù)2=8t+l三l(mod8),

偶數(shù)2=(2k)2=4k"k為整數(shù)).

⑴若k=偶數(shù)=2t,則

4k2=16t2=0(mod8).

(2)若卜=奇數(shù)=2t+l,則

4k2=4(2t+l)2=16(t2+t)+4三4(mod8),

所以

0(mod8),

平方數(shù)21(mod8),

4(mod8).

求余數(shù)是同余的基本問題.在這種問題中，先求出與±1同余的數(shù)是

一種基本的解題技巧.

例8⑴求33除2,的余數(shù).

(2)求8除7嘰1的余數(shù).

解(1)先找與±l(mod33)同余的數(shù).因為

2、=32三-1(mod33),

所以2y(mod33),

2'998=(210)199?25?2,三-8三25(mod33),

所求余數(shù)為25.

(2)因為7三-1(mod8),所以

72?+1=(-l)2n+1=-l(mod8),

72?+1-l=-2=6(mod8),

即余數(shù)為6.

例9形如

F?=22"+l,n=0,1,2,…

的數(shù)稱為費馬數(shù).證明：當(dāng)nN2時，F(xiàn).的末位數(shù)字是7.

證當(dāng)n》2時，2。是4的倍數(shù)，故令2"=4t.于是

F?=22n+l=24l+l=16l+l

=6'+1=7(mod10),

即3的末位數(shù)字是7.

說明費馬數(shù)的頭幾個是

F°=3,件=5,F2=17,F3=257,F4=65537,

它們都是素數(shù).費馬便猜測：對所有的自然數(shù)n,F.都是素數(shù).然而,

這一猜測是錯誤的.首先推翻這個猜測的是歐拉，他證明了下一個費馬數(shù)

R是合數(shù).證明R是合數(shù)，留作練習(xí).

利用同余還可以處理一些不定方程問題.

例10證明方程