高中數(shù)學(xué)講義：初等數(shù)論 同余

高中數(shù)學(xué)講義：初等數(shù)論同余

目錄

1.本講概述....................................................................1

1.1.同余的定義：............................................................1

1.2.剩余類與完全剩余系(簡(jiǎn)稱完系).........................................1

2.例題精講....................................................................2

3.大顯身手....................................................................3

1.本講概述

同余是大數(shù)學(xué)家高斯的一個(gè)天才發(fā)明，這個(gè)符號(hào)使得原來難以表述的很多數(shù)

論問題表述起來簡(jiǎn)單清晰.利用同余符號(hào)，可以方便地處理各種復(fù)雜的數(shù)字相對(duì)

于另一數(shù)的余數(shù)這一類問題.本講將著重講述同余的基本性質(zhì)，并利用這些性質(zhì)

來解決各類同余的典型問題.此外，基于同余，還給出了剩余系與完系的概念.

盡管聯(lián)賽大綱沒有明確對(duì)這兩個(gè)概念作要求，但是有了對(duì)剩余系的基本認(rèn)識(shí)后

對(duì)很多問題處理起來會(huì)更為方便.

1.1.同余的定義：

設(shè)m是一個(gè)給定的正整數(shù)，如果兩個(gè)整數(shù)a與b用m除所得的余數(shù)相同，

則稱a與b對(duì)模同余，記作。三。(modm),否則，就說a與b對(duì)模m不同余.

(用三符號(hào)上面加一個(gè)斜線來表示，類似不等符號(hào)).

顯然，a=￡>(modin)a=km+b,CkZ)m\(a-b)；

1.2.剩余類與完全剩余系(簡(jiǎn)稱完系)

我們可以將所有的整數(shù)按模m分類.例如：按模2分類，可將所有整數(shù)分

成兩類，模2余1的分成一類，即奇數(shù)；模2余0的一類，即偶數(shù).按模3分

類，可分成3k,3k+l,3k-l三種類型;等等.

剩余類的定義:設(shè)m為一給定的正整數(shù),則全體整數(shù)可以分為m個(gè)集合Ko,

K1,…，Km-1,這里K產(chǎn){x|xKZ,x-r(modm)},r=0,1,…，m-1.我們稱Ko,Ki,…,

Km-1為模m的剩余類.

在模m的m個(gè)剩余類中分別取一個(gè)數(shù)，共取出m個(gè)，我們把這m個(gè)數(shù)成

第1頁共4頁

為模m的一組完全剩余系，簡(jiǎn)稱完系.例如：0,1,2,就是一組完系，顯然，

它們兩兩對(duì)模m不同余.

性質(zhì)1.每個(gè)整數(shù)在且僅在模m的一個(gè)剩余類中.

性質(zhì)2.若ao,ai,…，am-i是模m的一個(gè)完系,而(a,m)=l,bez,則aao+b,

aai+b,…,aam-i+b也是模m的一個(gè)完系.(此性質(zhì)可自行證明，聯(lián)賽范圍內(nèi)一

般不需要掌握)

同余的性質(zhì)非常之多，以下僅列舉最常用的一些，

(1)自反性：a三a(modm)(a為任意自然數(shù))

(2)對(duì)稱性：若a三b(modm),則b三a(modm)

(3)傳遞性：若a三b(modm),b三c(modm),則a三c(modm)

(4)可加減性：若a三b(modm),c三d(modm),貝Ua土c三b土d(modm)

(5)可乘性：若a三b(modm),c三d(modm),貝Uac=bd(modm)

(6)可乘方性:若a三b(modm),n￡N+,則an=bn(modm)

注意：一般地同余沒有“可除性”，但是

(7)如果：ac三bc(modm)且(c,m)=l,則a三b(modm)

如果ac=bc(modm),(c,m)=d,貝ija=b(mod—)

d

(8)如果a三b(modm),a三b(modn)且[m,n]=k,貝Ia三b(modk)([m,n]表

示m,n的最小公倍數(shù))

(9)設(shè)pdN+,p22,則任何一個(gè)p進(jìn)制自然數(shù)與其數(shù)碼和(p進(jìn)制下各數(shù)

碼之和)對(duì)模p-1同余；特別地，p=10時(shí)，是我們熟知的“棄九法”的理論依據(jù)：

任一正整數(shù)與其十進(jìn)制表示中各位數(shù)字之和對(duì)模9同余.

利用“棄九法”可以方便地解決很多與數(shù)字和相關(guān)的問題.

另外，利用同余與各種乘法公式以及二項(xiàng)式定理展開式相結(jié)合往往威力更大,

但我們這里暫時(shí)不涉及.

2.例題精講

【例1】證明上述理論部分中的部分性質(zhì)：

i.同余的可除性:如果:ac=bc(modm)K(c,m)=l,則a三b(modm)

第2頁共4頁

ii.證明若ao,ai,…，am-i是模m的一個(gè)完系，而(a,m)=l,b6Z,則aao+b,

aai+b,…,aam-i+b也是模m的一個(gè)完系.(提示：只需證明任意兩

個(gè)模m不同余即可)

iii.棄九法原理：任一正整數(shù)與其十進(jìn)制表示中各位數(shù)字之和對(duì)模9同

余

【例2】(1)用同余的寫法證明：平方數(shù)除以4余數(shù)為0或1；

(2)用同余的寫法證明：奇數(shù)的平方除以8余1；

(3)試證明1155網(wǎng)+34網(wǎng)不是平方數(shù).

【例3】求證：對(duì)任意正整數(shù)n,8?"+217"

【例4】(1)設(shè)m為正整數(shù)，證明：必有一個(gè)正整數(shù)是m的倍數(shù)，且它的各位

數(shù)字均為0或1.

(2)從任意m個(gè)整數(shù)中，必可找到若干個(gè)數(shù)，它們的和(只

有一個(gè)加數(shù)也行)被m整除.

【例5】199r的各位數(shù)字之和為a,a的各位數(shù)字之和為b,b的各位數(shù)字之和

為c,求c.

【例6】求證：三個(gè)連續(xù)整數(shù)的平方和不是立方數(shù).

【例7】求出所有小于10的正整數(shù)m,使得511989"'+加989.

【例8】已知數(shù)列｛p,J定義如下：z=l"+2"+3"+4",求出所有的正整數(shù)n,使

得5Ip”.

【例9】已知數(shù)列｛4｝遞歸定義如下：4=0,4=1,an+2=8an+l-an(n>0),求證：

數(shù)列｛%｝中沒有形如3a5〃(％夕為正整數(shù))的項(xiàng).

【例10】設(shè)正整數(shù)X,y,Z滿足f+y2=Z?,證明：60|孫z.

3.大顯身手

1.證明：數(shù)列11,ill,1111,…中沒有平方數(shù)

2.若質(zhì)數(shù)且2p+l也是質(zhì)數(shù)，證明：4p+l是合數(shù)

3.3000的各位數(shù)字之和為a,a的各位數(shù)字之和為b,b的各位數(shù)字之和為

第3頁共4頁

C,求c.

1990

4.對(duì)，=1,2,3,…,1990,不可以取值1或者?1,證明Z乜工。?

2=1

5.設(shè)x,y,z為整數(shù)，且滿足(x-y)(y-z)(z-x)=A：+y+z,證明：

271x+y+z

6.(1)十進(jìn)制數(shù)88...8妁9...9可被7整除，那么數(shù)字x等于多少?(其中

有50個(gè)