CoffeeCat's IT Blog

奇妙的数学

今天我在编写RSA加密算法的程序,其中,有一个原理性的式子有点看不明白:a=b(mod c)。于是,我和黄臻开始讨论,然后,黄臻发现,这个叫同余式,表示a除以c的余数是b。

于是,我提出了一个问题,如果a和c的余数是1,那么能不能证明a和c是互质的?。然后,我和黄臻开始了有趣的思考。我尝试着证明几次,都很搞笑的回到了命题本身,最后,黄臻通过反证法,把这个问题解出来了,然后和我说了3遍,才把我说服,呵呵,当时,我和他的思维处于两条平行线上,所以我们的一些对话特别搞笑,当时我们自己都笑翻了~~比如我试图推翻他的结论,于是我开始举反例,举了半天没举出来,后来发现,我如果能举出反例,我也就能推翻我的命题,不需要证明了~~

根据黄臻的反证法,我们总算得出了结论:如果a和c的余数是1,那么a和c就互质了~

然后我继续写程序~写程序的时候,我想起来我程序中用到了欧几里德算法来求最大公约数,就是用除数除以被除数,如果求得的余数不为0,则将被除数作为新的除数,余数作为新的被除数,重复刚才的步骤。如果求得的余数等于0了,那么最后一次的被除数就是两个数的最大公因数。比如,求15和6的公约数,先得到15除以6的余数3,然后得到6和3的余数0,由此得到15和6的最大公因数是3。那我只要求一下a和c的最大公约数不就行了~

于是,我用欧几里德算法来求a和c的最大公约数,由题目可知,a除以c的余数是1,c除以1的余数肯定是0,所以,a和c的最大公因数也就是1,也就是a和c是互质的~

一个反证,一个正证,两种不同的思路,两种不同的方法,却能得到相同的结论~一个简单的命题,可以很简单的证明了,也可能绕了很大圈子也没证明出来~数学真是奇妙啊~

posted on 2007-12-27 01:40 CoffeeCat 阅读(323) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
<2007年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

公告

常用链接

留言簿(183)

随笔档案

收藏夹

搜索

最新评论

阅读排行榜

评论排行榜