整數(shù)帶余數(shù)除法定理的再認(rèn)識(shí)

夏咪咪, 陳 若

(湖州師范學(xué)院 理學(xué)院, 浙江 湖州 313000)

0 引 言

帶余數(shù)除法定理不僅是初等數(shù)論的基礎(chǔ),而且在高等代數(shù)及近世代數(shù)中占有一席之地.帶余數(shù)除法定理從整數(shù)環(huán)、多項(xiàng)式環(huán)、高斯整數(shù)環(huán)推廣到一般的歐氏環(huán)，是這些環(huán)理論的基礎(chǔ).整數(shù)帶余數(shù)除法是數(shù)論中整數(shù)整除理論的一個(gè)重要組成部分.

帶余數(shù)除法定理的應(yīng)用十分廣泛,是小學(xué)到大學(xué)階段數(shù)學(xué)學(xué)習(xí)的重要內(nèi)容.帶余數(shù)除法在小學(xué)低年級(jí)數(shù)學(xué)中就有涉及,并常常被概括為這樣的形式:被除數(shù)÷除數(shù)=商……余數(shù),如10÷4=2……2.初中數(shù)學(xué)也涉及多項(xiàng)式除法的學(xué)習(xí),如根據(jù)等式2x3+9x2+9x+6=(x2+4x+1)(2x+1)+(3x+5),可知2x3+9x2+9x+6除以x2+4x+1的結(jié)果.高中及大學(xué)也會(huì)繼續(xù)學(xué)習(xí)該內(nèi)容并逐步加深.帶余數(shù)除法定理是研究整數(shù)和多項(xiàng)式整除理論的一個(gè)基本方法,所以深入研究該理論十分必要.

本文對(duì)整數(shù)帶余數(shù)除法定理進(jìn)行系統(tǒng)的研究,介紹帶余數(shù)除法定理及其歷史發(fā)展,并用多種方法給出相關(guān)證明,從不同角度對(duì)帶余數(shù)除法定理進(jìn)行深入理解.同時(shí)舉例說(shuō)明帶余數(shù)除法定理在數(shù)學(xué)教學(xué)及跨學(xué)科中的應(yīng)用.該研究用帶余除法定理的思想方法將小學(xué)到大學(xué)的相關(guān)知識(shí)串聯(lián)起來(lái),便于學(xué)生系統(tǒng)性地加深對(duì)知識(shí)的理解.

1 帶余數(shù)除法定理與歷史發(fā)展

定理1[2]若a,b是兩個(gè)整數(shù),其中b>0,則存在兩個(gè)整數(shù)q及r,使得

a=bq+r, 0≤r

(1)

成立,且q及r是唯一的.我們把q稱作a被b除所得的不完全商,r稱作a被b除所得的余數(shù).當(dāng)r=0即a=bq時(shí),我們就說(shuō)b整除a,記作b|a.

該定理稱作帶余數(shù)除法定理,整數(shù)的一些基本性質(zhì)可由此定理推導(dǎo)得出.在該定理中,假設(shè)a=173,b=21,則有a=8b+5,r=5<21,q=8,其中q、r是唯一的.

中國(guó)古代《九章算術(shù)》中介紹的“更相減損術(shù)”，實(shí)質(zhì)上就是應(yīng)用帶數(shù)除法定理,原是為約分設(shè)計(jì)的，而后應(yīng)用于任何求最大公約數(shù)的場(chǎng)合.書中記載到“可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也.以等數(shù)約之”[3].所利用的原理就是gcd(a，b)=gcd(a-b，b).以77和56為例.

77-56=21， 56-21=35， 35-21=14，

21-14=7， 14-7=7，

可知gcd(77,56)=7.更相減損術(shù)是利用減法原理來(lái)求兩數(shù)的最大公約數(shù).在西方歐幾里得創(chuàng)設(shè)了用除法原理求公約數(shù)的方法,即輾轉(zhuǎn)相除法.

定義1對(duì)任意兩個(gè)整數(shù)a,b>0，重復(fù)應(yīng)用帶余數(shù)除法,有:

a=bq1+r1, 0b=r1q2+r2, 0r1=r2q3+r3, 0……
rn-2=rn-1qn+rn, 0

rn-1=rnqn+1+rn+1,rn+1=0.

由于余數(shù)是小于除數(shù)的非負(fù)整數(shù),除數(shù)是正整數(shù),所以重復(fù)進(jìn)行帶余數(shù)除法能得到一個(gè)余數(shù)是零的等式,這樣的計(jì)算方法即為輾轉(zhuǎn)相除法.

利用輾轉(zhuǎn)相除法可求出兩個(gè)正整數(shù)的最大公約數(shù),如求1 537與1 749的最大公約數(shù).因?yàn)? 749=1×1 537+212，1 537=7×212+53，212=4×53，所以(1 537,1 749)=53.

由輾轉(zhuǎn)相除法可得到整數(shù)整除理論中幾個(gè)重要定理的關(guān)系,如圖1所示.這3個(gè)重要定理構(gòu)成了整數(shù)整除理論的主要內(nèi)容.因此，帶余數(shù)除法定理可以說(shuō)是整數(shù)整除理論的基石.

2 帶余數(shù)除法定理的存在性證明

定理1有多種證明方法,本文系統(tǒng)梳理了幾種證明方法，其中有的證法對(duì)中學(xué)數(shù)學(xué)的教和學(xué)都有一定幫助.

2.1 帶余數(shù)除法定理與數(shù)軸

帶余數(shù)除法定理的存在性可以通過(guò)實(shí)數(shù)與數(shù)軸關(guān)系進(jìn)行證明.該證法通俗易懂,對(duì)中小學(xué)數(shù)學(xué)的學(xué)習(xí)有一定幫助,特別是可以幫助學(xué)生理解數(shù)軸的作用.

證明如圖2,以b為長(zhǎng)度單位建立數(shù)軸.

根據(jù)實(shí)數(shù)與數(shù)軸上點(diǎn)的一一對(duì)應(yīng)關(guān)系，必然存在唯一整數(shù)q，使得a在區(qū)間[qb,(q+1)b)內(nèi),令a-qb=r,則a=bq+r,其中0≤r

證畢.

2.2 帶余數(shù)除法定理與數(shù)學(xué)歸納法

證明帶余數(shù)除法定理存在性的一般方法是數(shù)學(xué)歸納法.該證法的思想一直貫穿中小學(xué)數(shù)學(xué)學(xué)習(xí)的整個(gè)過(guò)程.

證明易得a<0時(shí)與a>0時(shí)的證明過(guò)程類似,為簡(jiǎn)明不妨假設(shè)a≥0，則

(Ⅰ)若a

(Ⅱ)若a≥b,對(duì)a用數(shù)學(xué)歸納法:假設(shè)對(duì)n

①若a'

②若a'≥b,則由歸納假設(shè)有a'=bq'+r,0≤r

證畢.

2.3 帶余數(shù)除法定理與自然數(shù)最小數(shù)原理

該方法主要利用自然數(shù)的最小數(shù)原理.最小數(shù)原理是自然數(shù)所具有的一種基本性質(zhì),即任何非空的自然數(shù)集中都有最小的自然數(shù).這一原理是數(shù)學(xué)歸納法的基礎(chǔ).

證明

(Ⅰ)若b|a,即a=bq,q∈Ζ,取r=0時(shí)等式(1)成立;

(Ⅱ)若b?a,則有r≠b.設(shè)集合A={a+kb,k∈Ζ}在k=k0時(shí),取得最小正整數(shù)r=a+k0b,則必有0b.

若r>b,即a+k0b>b,a+(k0-1)b>0,這與最小正整數(shù)r的取值矛盾,故0

證畢.

2.4 帶余數(shù)除法定理與高斯函數(shù)

高斯函數(shù)在中小學(xué)解題時(shí)常出現(xiàn),學(xué)生對(duì)其并不陌生.利用高斯函數(shù)對(duì)帶余數(shù)除法定理進(jìn)行證明，有助于加強(qiáng)學(xué)生對(duì)教材外所學(xué)知識(shí)的理解和應(yīng)用.

設(shè)x∈,記[x]為不超過(guò)x的最大整數(shù),{x}=x-[x].稱[x]為x的整數(shù)部分,{x}為x的小數(shù)部分,并把y=[x]稱為高斯函數(shù),如

證明假設(shè)在數(shù)1,2,…,a(a>0)中能被b整除的整數(shù)有k個(gè)，由于能被b整除的正整數(shù)是b，2b,3b,…,故

證畢.

2.5 帶余數(shù)除法定理與計(jì)算機(jī)程序

除了上述4種方法可以證明帶余數(shù)除法定理的存在性外,還可以通過(guò)C語(yǔ)言編寫實(shí)現(xiàn)整數(shù)帶余數(shù)除法的函數(shù),完成對(duì)該定理的機(jī)器驗(yàn)證[4].

class INT

{

public:

INT(int a)

{

x=a;

}

int x;

};

再定義運(yùn)算符的重載:

int operator/(INT x,int y)

{

return quo(x.x,y);

}

int operator/(int x,INT y)

{

return quo(x,y.x);

}

int operator/(INT x,INT y)

{

return quo(x.x,y.x);

}

int operator % (INT x,int y)

{

return rem(x.x,y);

}

int operator % (int x,INT y)

{

return rem(x,y.x);

}

int operator % (INT x,INT y)

{

return rem(x.x,y.x);

}

給出進(jìn)行調(diào)用的主函數(shù):

void main( )

{

int x, y;

cout<<"x="; cin>>x;

cout<<"y="; cin>>y;

cout<<"x/y="<

cout<<"x%y="<

}

3 帶余數(shù)除法定理的應(yīng)用

帶余數(shù)除法定理是初等數(shù)學(xué)的重要組成部分,在現(xiàn)實(shí)生活中應(yīng)用廣泛.因此在中小學(xué)的數(shù)學(xué)學(xué)習(xí)中備受關(guān)注,此外,在不同學(xué)科中的應(yīng)用也很廣泛.早在公元5世紀(jì),我國(guó)的《孫子算經(jīng)》中就出現(xiàn)了一元線性同余方程組問(wèn)題,其解法被稱為孫子定理,又叫中國(guó)剩余定理.孫子定理的實(shí)際應(yīng)用十分廣泛,如計(jì)算機(jī)軟件技術(shù)、編寫與密碼、數(shù)字通訊等領(lǐng)域.孫子定理的重要性不言而喻,其理論依據(jù)就是帶余數(shù)除法定理.下面通過(guò)典型例子列舉帶余數(shù)除法在整除、不定方程、單位根及跨學(xué)科4個(gè)方面的應(yīng)用.

3.1 在整除中的應(yīng)用

分析注意到相鄰兩個(gè)整數(shù)中總有一個(gè)是偶數(shù),所以對(duì)任意整數(shù)n,n(n+1)能被2整除,于是只要證明對(duì)任意整數(shù)n,n(n+1)(2n+1)能被3整除即可.將全體整數(shù)除以3,按余數(shù)可分為3類:{0}、{1}和{2},只要證明整數(shù)n取{0}、{1}和{2}中的任何一個(gè)數(shù),n(n+1)(2n+1)都能被3整除即可.

證明對(duì)任意整數(shù)n,n(n+1)是偶數(shù),所以n(n+1)(2n+1)能被2整除.

對(duì)任意的整數(shù)k,當(dāng)n=3k時(shí),

n(n+1)(2n+1)=9k(k+1)(6k+1);

當(dāng)n=3k+1時(shí)，

n(n+1)(2n+1)=3(2k+1)(3k+1)(3k+2);

當(dāng)n=3k+2時(shí)，

n(n+1)(2n+1)=3(k+1)(3k+2)(6k+5).

證畢.

3.2 在不定方程中的應(yīng)用

例證明:若n=9k+t,t=3,4,5或6,k∈Ζ,則方程x3+y3=n沒(méi)有整數(shù)解.

分析不定方程不僅內(nèi)容十分豐富,而且許多不定方程的解法有其特殊性.下面簡(jiǎn)要介紹一種最具普遍性的方法——余數(shù)分析法.余數(shù)分析法是利用帶余數(shù)除法定理將不定方程的解按某個(gè)正整數(shù)的余數(shù)分類,考察方程中的項(xiàng)對(duì)某個(gè)正整數(shù)的余數(shù).

證明對(duì)任意的整數(shù)x,y,記

x=3q1+r1,y=3q2+r2, 0≤r1,r2≤2,q1,q2∈Ζ,

則

其中,

R1=0,1或8,R2=0,1或8,R=0,1,2,7或8.

由此得到所要證明的結(jié)論.

證畢.

帶余數(shù)除法定理在不定方程中應(yīng)用廣泛,而且不定方程在實(shí)際生活中具有重要意義.這其中也滲透了建模思想,即將實(shí)際問(wèn)題轉(zhuǎn)化成數(shù)學(xué)模型,再運(yùn)用數(shù)學(xué)模型更好地解決生活中的問(wèn)題.數(shù)學(xué)建模是數(shù)學(xué)世界與實(shí)際生活之間的橋梁,通過(guò)建模有利于培養(yǎng)學(xué)生的抽象思維能力，以及提出問(wèn)題、分析問(wèn)題和解決問(wèn)題的能力.

3.3 在單位根中的應(yīng)用

例正整數(shù)n的全體正因數(shù)di(i=1,2，…，n),則所有di(i=1,2，…，n)次原根就是全體n次單位根.

證明設(shè)ε是任意di次原根,則εdi=1.又因?yàn)閐i|n,設(shè)n=dimi,則εn=(εdi)mi=1,即ε是一個(gè)n次單位根.

反之,設(shè)εn=1且d是使εd=1的最小正整數(shù).令

n=dq+r, 0≤r

則εr=εn-dq=1.由d的最小性知,r=0.故d|n,即d是d1,d2，…，dt中的一個(gè).

設(shè)d=di(1≤i≤t),并由d的最小性(即ε是一個(gè)不低于di次單位根)知,ε是一個(gè)di次原根.

證畢.

單位根有很多性質(zhì),在解方程、循環(huán)行列式、循環(huán)矩陣中都有重要應(yīng)用.其中也蘊(yùn)含了豐富的思想方法,單位根的學(xué)習(xí)可以開拓學(xué)生的數(shù)學(xué)視野,拓寬學(xué)生的解題思路.

3.4 在信息傳遞中的跨學(xué)科應(yīng)用

在網(wǎng)絡(luò)信息傳遞的過(guò)程中,由于傳輸系統(tǒng)是人為設(shè)計(jì)的，難免會(huì)出現(xiàn)差錯(cuò),導(dǎo)致信息接收者收到錯(cuò)誤的數(shù)據(jù)信息.為提高準(zhǔn)確率,需要在數(shù)據(jù)中增加校驗(yàn)碼.校驗(yàn)碼通常位于一組數(shù)字的最后一位或多位,由前面的數(shù)字經(jīng)某種運(yùn)算后得出,用以檢驗(yàn)該組數(shù)字的正確性.介紹CRC(循環(huán)冗余)校驗(yàn)碼,其作用是檢驗(yàn)數(shù)據(jù)的正確性并對(duì)錯(cuò)誤數(shù)據(jù)進(jìn)行糾正.

CRC運(yùn)算的數(shù)學(xué)本質(zhì)是帶余數(shù)除法定理,其編碼的過(guò)程是先約定一個(gè)“生成多項(xiàng)式”,再用一個(gè)新定義的多項(xiàng)式對(duì)“生成多項(xiàng)式”作模二除法得到校驗(yàn)碼,將該校驗(yàn)碼放在源數(shù)據(jù)碼之后形成CRC碼進(jìn)行傳輸.若接收到的CRC碼能被“生成多項(xiàng)式”整除,則說(shuō)明傳遞無(wú)誤,否則需要通過(guò)校驗(yàn)位查出出錯(cuò)的位置并進(jìn)行還原.

例位數(shù)為n的校驗(yàn)碼共有2n種情況,如位數(shù)為3的校驗(yàn)碼有000、001、010、100、011、110、111、101這8種,除了正確的1種外還存在7種錯(cuò)誤可能.現(xiàn)在有生成多項(xiàng)式G(x)=x3+x+1和二進(jìn)制序列為1 100的源數(shù)據(jù)碼,若數(shù)據(jù)接收者得到的CRC碼為1100110,問(wèn)CRC碼是否存在出錯(cuò)位(假設(shè)僅存在單個(gè)錯(cuò))？

解檢驗(yàn)得到的CRC碼需要對(duì)生成多項(xiàng)式G(x)作模二除法,若余數(shù)為0則傳遞無(wú)誤,否則有誤，且不同位數(shù)出錯(cuò)余數(shù)不同,具體見(jiàn)表1.

表1 余數(shù)與出錯(cuò)位對(duì)應(yīng)關(guān)系表

由于CRC碼對(duì)生成多項(xiàng)式G(x)作模二除法后得到的余數(shù)是100,因此可知該CRC碼存在錯(cuò)誤,出錯(cuò)位為第5位.

解畢.

不同位數(shù)的CRC碼都有類似的計(jì)算方法,其核心都是帶余數(shù)除法定理.例4的求解是對(duì)二進(jìn)制進(jìn)行模二除法得到余數(shù),也可以將二進(jìn)制轉(zhuǎn)化為十進(jìn)制進(jìn)行除法,再將得到的余數(shù)轉(zhuǎn)化為二進(jìn)制,其運(yùn)算本質(zhì)相同.

此外，帶余數(shù)除法還在光通信系統(tǒng)[6]、單循環(huán)比賽安排[7]等方面有著重要的作用.

4 結(jié) 語(yǔ)

本文對(duì)帶余數(shù)除法的歷史、證法、應(yīng)用等方面進(jìn)行了再認(rèn)識(shí).根據(jù)帶余數(shù)除法的證明和列舉的應(yīng)用發(fā)現(xiàn),帶余數(shù)除法的研究是非常有意義的數(shù)學(xué)研究之一,具有較高的實(shí)用價(jià)值,值得繼續(xù)探究.