有趣的余数巧算法

摘要：本文主要找出了积式、幂式、和式的余数规律，并加以论证和举例应用，从而体现出简便性和实用性。

关键词：余数；积式；幂式；和式；简便

两个整数相除，如果不能整除，如何求余数呢？对于数字较小的两个整数，可直接求出余数；但当数字较大时，尤其是含有整数的乘积、乘方的两个数相除，一般不容易直接得出余数。如199108除以13的余数，很难直接求出。经过多次探索、研究、推理和验算，再结合初等数论中的带余除法，得出了求余数的一些简單、快捷的计算方法。

下面来看一下如何快速求出两数相除所得的余数。

文中出现的字母，不作特别说明，都表示正整数。为了方便，约定a除以b的余数记作rab。为了解决问题，我们需要带余除法：设a，b为正整数，则存在唯一的q，x为整数，使得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。

类似地，我们可以得出第三种类型求余数的方法：

第三种类型：若ra1b=x1，ra2b=x2，则ra1+a2b=rx1+x2b。

下面举例说明上述规律的应用和使用方法，以及如何利用余数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。

本文中的三个规律是可以反复使用的，如在ranb中，如果n很大，我们就可以反复运用这三个规律，使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求证：对于任何自然数k，数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。

命题得证。

这一证明题若用一般方法去做，较繁且思路不易想出，而运用上述方法，简便且易操作。我们再来看一下下面的例题。

例7设n为自然数，求证：若n为奇数，则（2n+1）是3的倍数，若n为偶数，则2n+1被3除余2。

证：当n为奇数时，设n=2k+1，则

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

余数为零，从而证明了2n+1是3的倍数。

当n为偶数时，设n=2k，则

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

命题得证。

从上面的例题演算可知，利用我们总结的基本方法，能解整数乘积以及整数幂次被另一个整数除所得的余数，能使一些较复杂繁琐的题目简单化，而且对没有专门学过初等数论知识的中学生亦能接受这些规律。

参考文献：

[1]王进明.初等数论[M].北京.人民教育出版社，2002.

作者简介：杜海清，江苏省淮安市，江苏淮阴师范学院数学科学学院。