同余式

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

稱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,設

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

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

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

定義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).

證由假設得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是整數，n是自然數，則

a±k=b±k(modm),

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

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

的同余式a三b(modm)?

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

25=5(mod10),

約去5得

5=1(mod10).

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

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

a三b(modm).

證由題設知

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,??-,叫的最小公倍數，則

a=b(modM).

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

些具體問題.

應用同余式的性質可以簡捷地處理一些整除問題,若要證明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的倍數的所有正整數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).

所以，當且僅當31n時，2"-1為7的倍數.

例3對任意的自然數n,證明

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

能被1897整除.

證1897=7X271,7與271互質.因為

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個數任意排列為a”&,…，a儂,

計算出

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

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

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

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

解因為對于一個整數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),

因此，每經過一次“運算”，這些數的和的奇偶性是不改變的.最終

得到的一個數

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

=64X129=0(mod2),

故x是偶數.

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

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

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

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

除的余數.

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

10=1(mod9),

故對任何整數kN1,有

10k=r=l(mod9).

因此

a，-aaa

A=ann-r2l0

nn1

=anX10+anlX10-+-+aiX10+a0

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

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

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

能被9整除.

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

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

證因為

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

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

所以

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

0(mod4；,偶數.

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

證奇數可以表示為2k+l,從而

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

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

從而

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

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

⑴若k=偶數=2t,則

4k2=16t2=0(mod8).

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

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

所以

0(mod8),

平方數21(mod8),

4(mod8).

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

一種基本的解題技巧.

例8⑴求33除2,的余數.

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

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

2、=32三-1(mod33),

所以2y(mod33),

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

所求余數為25.

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

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

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

即余數為6.

例9形如

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

的數稱為費馬數.證明：當nN2時，F.的末位數字是7.

證當n》2時，2。是4的倍數，故令2"=4t.于是

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

=6'+1=7(mod10),

即3的末位數字是7.

說明費馬數的頭幾個是

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

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

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

R是合數.證明R是合數，留作練習.

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

例10證明方程