有趣的余数巧算法

2018-04-19 10:44杜海清
考试周刊 2018年40期
关键词:和式

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

关键词:余数;积式;幂式;和式;简便

两个整数相除,如果不能整除,如何求余数呢?对于数字较小的两个整数,可直接求出余数;但当数字较大时,尤其是含有整数的乘积、乘方的两个数相除,一般不容易直接得出余数。如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.

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

猜你喜欢
和式
谈谈配凑基本不等式中的和式与积式的技巧
关于组合和式的Dwork类型超同余式
一道全国大学生数学竞赛题的引申与推广
Zeilberger算法与二项分布
日本和式风格珠宝设计文化的研究
利用级数求无穷多项和的极限
函数Riemann和式的类Taylor级数展开式
等比法求和式极限
组合式的封闭形式解读
几类特殊和式极限求法的归纳