注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周靖国的博客

春蚕到死丝方尽 愿将余生蚕化春蚕

 
 
 

日志

 
 

有趣的同余式  

2013-06-29 06:00:42|  分类: 趣味数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

(选自《数论妙趣——数学女王的盛情款待》第五章 大师的发明)

先来做一个数学游戏:

让对方想一个小于1000的正整数,相继用7,11,13去除它,把3个余数告诉你,你很快就能说出他想的数是什么。

做到这一点其实并不难。你只需把3个余数分别乘以“魔数”715,364,924,再把所得的积相加,从中尽量减去1001的整数倍,得到的差就是他所想的数。

例如,对方告诉你的余数是5,6,3。

751×5+364×6+924×3=8531,8531-8×1001=523,就是他所想的数。

在作出解释之前,有必要学点“同余”知识,它是数学大师号称“数学王子”的高斯发明的。

在数论里,我们时常要测试一个数n能否被另一个数m整除。此时,商数并不重要,感兴趣的仅仅是余数以及使之为0(即整除)的条件。高斯为此发明了一种非常紧凑而高度有效的记号,不考虑无关因素,使我们得到了有关整数与可除性的全新且熠熠发光的概念——同余。

例如,用13除31,通常写作31÷13=2……5,而用同余的概念,可以记作31≡5 mod 13。读作“31与5同余,模13”。

同余式与方程有许多相似的性质。

以31≡5 mod 13为例:

两边同时加上3,得34≡8 mod 13。(即,34除以13,余8。)

两边同时减去5,得26≡0 mod 13。(即,26能被13整除。)

两边同时乘以4,得124≡20 mod 13,由于20≡7 mod 13,所以可以记作124≡7 mod 13。(即,124除以13,余7。)

两边同时各自平方,得312≡52 mod 13。因为52≡12 mod 13,所以可以记作312≡52≡12 mod 13。由于12在除以13时少1,所以又可以记作312≡52≡-1 mod 13。两边同时加上1,得312+1≡0 mod 13。(即,312+1能被13整除。事实上,312+1=962,962÷13=74,962能被13整除。)

与方程不同,仅当一个数与模互质时,才能用它去除同余式的两边。所以,即便有40≡10 mod 15,两边也不能同时除以10,得4≡1 mod 15,因为除数10不与模15互质。而两边同时除以2,得20≡5 mod 15,则是可以的,因为2与模15互质。如果一定要用10去除同余式的两边,那就同时要用10与模15的公因子5去除模15,得4≡1 mod 3。

同余式在处理乘幂时非常有用。例如:

证明97104-1恰能被105整除。

97≡1 mod 3,得97104≡1104≡1 mod 3,即

          97104≡1 mod 3。  (1)

由97≡2 mod 5,得972≡22≡4≡-1 mod 5,进而得974≡(-1)2≡1 mod 5,于是,(974)2697104≡126≡1 mod 5,即

          97104≡1 mod 5。    (2)

97≡-1 mod 7,得97104≡(-1)104≡1 mod 7,即

          97104≡1 mod 7。    (3)

把上面三式结合起来,由于3,5,7没有公因子,得

          97104≡1 mod 3·5·7=105,

          97104-1≡0 mod 105,

即97104-1恰能被105整除。

现在来看前面戏法中的魔数715,364,924。

设x是选定的未知数,a,b,c是x除以7,11,13的余数。于是有:

    x≡a mod 7, 715x≡715a mod 7。

    x≡b mod 11, 364x≡364b mod 11。

    x≡c mod 13, 924x≡924a mod 13。

移项,得

        715(x-a)≡0 mod 7。    (1)

        364(x-b)≡0 mod 11。       (2)

        924(x-c)≡0 mod 13。       (3)

因为

(1)式中的715能被11,13整除,从而(1)式能被7,11,13整除,即能被7×11×13=1001整除;

(2)式中的364能被7,13整除,从而(2)式能被7,11,13整除,即能被7×11×13=1001整除;

(3)式中的924能被7,11整除,从而(3)式能被7,11,13整除,即能被7×11×13=1001整除。

对新模1001而言,上面3式相加,得

    2003x-(715a+364b+924c)≡0 mod 1001

移项,得

    2003x≡(715a+364b+924c)≡0 mod 1001

从2003x中减去1001的倍数2002x,得

      x≡(715a+364b+924c)≡0 mod 1001

这样就得到用三个魔数和三个余数表达的x的值,只需尽量减去1001的倍数就可以了。

那么,三个魔数又是怎样得到的呢?715实际就是11与13的公倍数中被7除余1的数;364实际就是7与13的公倍数中被11除余1的数;924实际就是7与11的公倍数中被13除余1的数。

大家一定知道,在我国古代算书《孙子算经》和《算法统宗》中,就有类似的问题,可以互相参考借鉴。

同余式还有一个重要性质:如果一个同余式对好几个模都成立,则它对这些模的最小公倍数也成立。

利用这一性质,类似下面的问题很容易解决:

有一支部队的人数,不能被2,3,4,5,6,7,8,9,10,11,12整除,在每种情况下,都有一人剩下来。但是,却可以等分为13队。试问,这支部队至少有多少人?

设这支部队有x人。这时有同余式

    x≡1 mod 2,3,4,5,6,7,8,9,10,11,12

以及

         x≡0 mod 13。

由于2,3,4,5,6,7,8,9,10,11,12的最小公倍数是27720,从而

         x≡1 mod 27720

因此,x满足的首要条件是,x等于1或者1加上27720的整数倍,即

         x=27720m+1

从27720≡4 mod 13,两边同时乘以m再加1,得27720m+1≡4m+1 mod 13。要使右边的4m+1能被13整除,取m=3,可得4m+1≡0 mod 13。因而满足条件的最小数为x=27720m+1=27720×3+1=83161。即,这支队伍至少有83161人。

  评论这张
 
阅读(152)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017