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

ad0415的博客

欢迎来作客!ad0415@yeah.net

 
 
 

日志

 
 

同余运算及其基本性质  

2009-07-28 13:04:13|  分类: 数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  100除以7的余数是2,意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义:假如被除数是a,除数是b(假设它们均为正整数),那么我们总能够找到一个小于b的自然数r和一个整数m,使得a=bm+r。这个r就是a除以b的余数,m被称作商。我们经常用mod来表示取余,a除以b余r就写成a mod b = r。

    如果两个数a和b之差能被m整除,那么我们就说a和b对模数m同余(关于m同余)。比如,100-60除以8正好除尽,我们就说100和60对于模数8同余。它的另一层含义就是说,100和60除以8的余数相同。a和b对m同余,我们记作a≡b(mod m)。比如,刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用,比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。

    之所以把同余当作一种运算,是因为同余满足运算的诸多性质。比如,同余满足等价关系。具体地说,它满足自反性(一个数永远和自己同余)、对称性(a和b同余,b和a也就同余)和传递性(a和b同余,b和c同余可以推出a和c同余)。这三个性质都是显然的。

    同余运算里还有稍微复杂一些的性质。比如,同余运算和整数加减法一样满足“等量加等量,其和不变”。小学我们就知道,等式两边可以同时加上一个相等的数。例如,a=b可以推出a+100=b+100。这样的性质在同余运算中也有:对于同一个模数m,如果a和b同余,x和y同余,那么a+x和b+y也同余。在我看来,这个结论几乎是显然的。当然,我们也可以严格证明这个定理。这个定理对减法同样有效。

    性质:如果a≡b(mod m),x≡y(mod m),则a+x≡b+y(mod m)。

    证明:条件告诉我们,可以找到p和q使得a-mp = b-mq,也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms,即a+x-m(p+r) = b+y-m(q+s),这就告诉我们a+x和b+y除以m的余数相同。

    容易想到,两个同余式对应相乘,同余式两边仍然相等:

    如果a≡b(mod m),x≡y(mod m),则ax≡by(mod m)。

    证明:条件告诉我们,a-mp = b-mq,x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms),等式两边分别展开后必然是ax-m(...) = by-m(...)的形式,这就说明ax≡by(mod m)。

    现在你知道为什么有的题要叫你“输出答案mod xxxxx的结果”了吧,那是为了避免高精度运算,因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数,令b=a mod m,那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的,这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然,因为同余运算只关心余数(不关心“整的部分”),完全可以每一次运算后都只保留余数。因此,整个运算过程中参与运算的数都不超过m,避免了高精度的出现。

    在证明Fermat小定理时,我们用到了这样一个定理:

    如果ac≡bc(mod m),且c和m互质,则a≡b(mod m) (就是说同余式两边可以同时除以一个和模数互质的数)。

    证明:条件告诉我们,ac-mp = bc-mq,移项可得ac-bc = mp-mq,也就是说(a-b)c = m(p-q)。这表明,(a-b)c里需要含有因子m,但c和m互质,因此只有可能是a-b被m整除,也即a≡b(mod m)。

  评论这张
 
阅读(522)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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