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)。
可能以后还要用到更多的定理,到时候在这里更新。
Matrix67原创
转贴请注明出处
第4自然段某个好像打错了 “对于同一个模数m,如果a和b同余,x和y同余,那么a+b和x+y也同余。”
回复:谢谢提醒,已改正。请大家继续帮忙找错
若b<0则r是不存在的。
回复:谢谢提醒。我加了一句“都是正整数”
这个不准确,因为没有a+x-m(p+r)<m。
回复:对,这句话还是不写好
11
精确度较高,版块完整。赞一个。
总体看了下下blog,super!
加油哦!
“你会发现这种记号到处都在用,比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。”
哈哈,就是被除数和自己的余数同余啊
你跟我的思考风格很像呀,每次读你的文章都觉得特别明白 ^_^
不错
问下,四塔问题:
http://acm.fzu.edu.cn/problem.php?pid=1036
每次算要取最小怎么取模?
以前对Fermat迷茫,现在终于懂了。神牛的讲解好通俗。赞一个!!!
冯晶晶结婚了一刚~~高中班长们在婚姻方面也起带头作用嘛~~ Good Luck~~
能够慢慢培养的不是爱情,而是习惯。能够随着时间得到的,不是感情而是感动。所以爱是一瞬间的礼物,有就有,没有就没有。但反过来说,爱和婚姻实际并不是一回事情,并不是所有的爱情都要结婚的,也不是所有婚姻都有爱情的。
荣威350大话智享版对于即将步入婚姻生活的80后来说,如何选择家用车还是有点讲究的。既要考虑经济因素,又要兼顾驾乘品质。荣威350在外观造型上不失优雅,安全品质又杰出,还有独一无二的法宝——语音云驾驶iVoka让用户体验到了其带来的安全性、便捷性、娱乐性。新婚车时代怎么可以错过荣威350呢?
最早的预告八点城事今日播出关于思考婚姻的一期入门级节目。你理想的婚姻,是什么样子?贵州旅游广播欢迎收听。
生活中的理财当一对新人准备结婚时,如果其中一方已有房产并准备在房产证上为另一方加名时,需注意最好在法定婚姻关系成立之后进行,因现行法律规定凡是夫妻间的房产加名均免征契税,仅收取工本费和印花税等费用。但如果情侣间的房产证加名发生法定婚前则属于房屋赠予行为,仍需缴纳契税。
跟大家说一下【报名条件】哈A、 凡年满18周岁以上的女性;B、即将新婚的准新人;C、已经结婚,对婚姻充满憧憬的女性。(条件还是蛮宽松的哦)
林依晨(LYC)林于超(LYC),如果结婚,某妞名曰"林林依晨",如果生小孩,名字也想好了,取父母姓氏,全名"林林总总"纯属玩笑,希望妞这段感情可以走到最后,迈进婚姻殿堂! :大家都发现了
其实我这样的人今后谁娶我也是可怕的…我不敢想。害怕婚姻……我不要结婚……我怕,我真的怕…..
要以为蜜月归来就代表婚礼已经圆满结束,一定要做个完美的收尾。不知道该做什么?没关系,跟我们一起来看看吧!绝对没有准备婚礼那么繁琐。让你的甜蜜婚姻生活因此开个美好的头。
谈家八婚姻就象泡茶,第一道茶象恋爱,浓烈馥郁香; 第二道茶象新婚,清新可人;第三道茶则象刚过密月或密年的婚姻,平淡如水,需要我们用平常心去品味,才能领略到其中的真趣。
今早一个顾客朋友和我约好早早的到店里来光顾,除了利益之外,成为朋友也是一件很让人庆幸的事。把我当好朋友一样的分享心事与婚姻心得,不断提醒我,就算到③⓪岁再结婚也不要紧,劝诱我未婚前去做一切自己想要做的事。我知道,也真的听过太多人给我这样的建议,现在我是该庆幸自己还是高傲的单身吗?
我新婚的朋友问我婚姻里是不是真的要不断忍让和迁就,我说我们之间好像不需要有这个“忍让”词汇哦。他我忍你很久了!我
大牛也是个好孩子 虚心请教 不耻下问的。支持
网站改版之后,文中很多链接都404了。
比如费马小定律的链接。
http://www.matrix67.com/blog/article.asp?id=280
大讚!
这是是什么网站啊
Wow, incredible weblog layout! How lengthy have you been blogging for?
you made blogging look easy. The full glance of your web site is fantastic, as neatly as the content material!
You can see similar here sklep internetowy
Helpful information. Fortunate me I discovered your site by accident, and I am surprised why this twist of fate didn’t came
about earlier! I bookmarked it. I saw similar here:
E-commerce
Hello there! Do you know if they make any plugins to help with
SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Cheers! I saw similar art here:
Auto Approve List
Wow, awesome weblog format!
How long have you been blogging for? you made blogging glance easy.
The total glance of your site is magnificent, as smartly as the content
material! You can see similar here prev
next and that was wrote by Particia73.
See What Kayleigh Porn Star Tricks The Celebs Are Making Use Of
Porn Star
Don’t Be Enticed By These “Trends” Concerning Best Accident
Attorney Near Me New york accident Attorneys