有趣的余數(shù)巧算法

摘要：本文主要找出了積式、冪式、和式的余數(shù)規(guī)律，并加以論證和舉例應(yīng)用，從而體現(xiàn)出簡便性和實(shí)用性。

關(guān)鍵詞：余數(shù)；積式；冪式；和式；簡便

兩個整數(shù)相除，如果不能整除，如何求余數(shù)呢？對于數(shù)字較小的兩個整數(shù)，可直接求出余數(shù)；但當(dāng)數(shù)字較大時，尤其是含有整數(shù)的乘積、乘方的兩個數(shù)相除，一般不容易直接得出余數(shù)。如199108除以13的余數(shù)，很難直接求出。經(jīng)過多次探索、研究、推理和驗算，再結(jié)合初等數(shù)論中的帶余除法，得出了求余數(shù)的一些簡單、快捷的計算方法。

下面來看一下如何快速求出兩數(shù)相除所得的余數(shù)。

文中出現(xiàn)的字母，不作特別說明，都表示正整數(shù)。為了方便，約定a除以b的余數(shù)記作rab。為了解決問題，我們需要帶余除法：設(shè)a，b為正整數(shù)，則存在唯一的q，x為整數(shù)，使得a=bq+x，其中0≤x

第一種類型：若rab=x，則rmab=rmxb。

因為ma=m（bq+x）=mbq+mx，所以rmab=rmxb。

特別地，若mx

第二種類型：若rab=x，則ranb=rxnb。

因為an=（bq+x）n

=C0n（bq）n+C1n（bq）n-1x+…+Cn-1n（bq）xn-1+Cnnxn，

所以ranb=rxnb。

類似地，我們可以得出第三種類型求余數(shù)的方法：

第三種類型：若ra1b=x1，ra2b=x2，則ra1+a2b=rx1+x2b。

下面舉例說明上述規(guī)律的應(yīng)用和使用方法，以及如何利用余數(shù)r=0時的特殊情況。

例1求r1283+1104+29929

解：因為r1289=r1109=r2999=2。

利用類型2、類型3，我們有

原式=r23+24+229=r8+16+49=r289=1。

例2求r10089×9237×14727

解：因為r1008927=18，

r923727=3，r14727=12，

所以利用類型1，我們有

原式=r18×3×1227=r54×1227

=r0×1227=r027=0。

例3求證：（m+n+1）p-1一定能被（m+n）整除。

證：要證此題，只要證明r（m+n+1）p-1m+n=0。

因為rm+n+1m+n=1，

所以r（m+n+1）p-1m+n=r1p-1m+n=r0m+n=0。

本文中的三個規(guī)律是可以反復(fù)使用的，如在ranb中，如果n很大，我們就可以反復(fù)運(yùn)用這三個規(guī)律，使n逐步降低。

例4求r19910813

解：因為r19913=4，所以，原式=r410813=r165413。

又r1613=3，所以，原式=r35413=r271813。

又r2713=1，所以，原式=r11813=r113=1。

例5求r523198119

解：因為，r52319=10。所以，原式=r10198119=r101980·1019=r100990·1019。

又因為，r10019=5，所以，原式=r5990×1019

=r25495×1019=r6495×1019

=r（63）165×1019=r216165×1019

=r7165×1019=r（73）55×1019=r34355×1019

=r155×1019=r1019=10。

例6求證：對于任何自然數(shù)k，數(shù)55k+1+45k+2+35k能被11整除。

證：只要證r55k+1+45k+2+35k11=0。

r55k+1+45k+2+35k11=r55k×5+45k×42+35k11

=r3125k×5+1024k×16+243k11。

又因為，r312511=1，r102411=1，r24311=1。

所以，原式=r1k×5+1k×16+1k11=r5+16+111=r2211=0。

命題得證。

這一證明題若用一般方法去做，較繁且思路不易想出，而運(yùn)用上述方法，簡便且易操作。我們再來看一下下面的例題。

例7設(shè)n為自然數(shù)，求證：若n為奇數(shù)，則（2n+1）是3的倍數(shù)，若n為偶數(shù)，則2n+1被3除余2。

證：當(dāng)n為奇數(shù)時，設(shè)n=2k+1，則

r2n+13=r22k+1+13=r4k×2+13=r1k×2+13=r2+13=0。

余數(shù)為零，從而證明了2n+1是3的倍數(shù)。

當(dāng)n為偶數(shù)時，設(shè)n=2k，則

r2n+13=r22k+13=r4k+13=r1k+13=r23=2。

命題得證。

從上面的例題演算可知，利用我們總結(jié)的基本方法，能解整數(shù)乘積以及整數(shù)冪次被另一個整數(shù)除所得的余數(shù)，能使一些較復(fù)雜繁瑣的題目簡單化，而且對沒有專門學(xué)過初等數(shù)論知識的中學(xué)生亦能接受這些規(guī)律。

參考文獻(xiàn)：

[1]王進(jìn)明.初等數(shù)論[M].北京.人民教育出版社，2002.

作者簡介：杜海清，江蘇省淮安市，江蘇淮陰師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院。