今天我在编写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是互质的～
一个反证，一个正证，两种不同的思路，两种不同的方法，却能得到相同的结论～一个简单的命题，可以很简单的证明了，也可能绕了很大圈子也没证明出来～数学真是奇妙啊～