浅谈同余理论的应用.docx

浅谈同余理论的应用在日常生活中我们所要注意的不仅仅是某些整数而是某些数用某一固定的数去除所得的余数。例如：我们经常会问现在是几点钟了这实际上就是用24去除某一个总的时数所得的余数又如问现在是星期几就是用7去除某一个总的天数所得的余数。这样在数学中就产生了同余的概念。同余是可除性的符号语言在西方是由高斯最先引进的。他的名著《算术探究》奠定了近代数论的基础。我们国家对同余式的研究有着光辉而悠久的历史。如《孙子算经》中的“物不知其数”问题就是同余式研究的开始。下面将着重介绍同余式在日常生活中的应用。其中将用到同余的一些基本概念、基本性质以及孙子定理等等知识来解决“物不知其数”问题列举检查因数的方法以及在密码学上的简单应用。定义1：给定一个正整数m把它叫做模。如果用m去除任意两个整数a与b所得的余数相同我们就说ab对模m同余。记作ab（modm）。如果余数不同我们就说ab对模m不同余。定理1：整数ab对模m同余的充分与必要条件是m（a-b）即：a=b+mtt是整数。证明：设a=mq1+r1b=mq2+r20≤r1若ab（modm）则r1=r2因此a-b=m（q1-q2）反之若m（a-b）则m[m（q1-q2）+（r1-r2）因此m（r1-r2）但r1-r2定理1说明同余这一概念又可定义如下：若m（a-b）则ab叫做对模m同余。一、“物不知其数”问题定理2（孙子定理）：设m1m2…mk是k个两两互质的正整数。m=m1m2…mkm=miMii=12…k则同余式组xb1（modm1）xb2（modm2）…xbk（modmk）的解是：xM′1M1b1+M′2M2b2+M′kMkbk（modm）其中M′1M11（modmi）i=12…k这个方法与孙子的算法完全一致它在国外文献中被称为中国剩余定理。孙子定理是数论中一个很重要的定理。由上表可以看出求乘率是最困难的。也就是求解同余式：xMi=1（modmi）。我国宋代大数学家秦九韶在他的杰作《算书九章》（1247）中提出了解这个同余式的一般解法秦氏将它称作“求一术”。二、检查因数的方法作同余知识的应用这里将列举出一些简便的检查因数的方法。定理3：一个整数能被3（9）整除的充要条件是它的十进位数码的和能被3（9）整除。证明：设a是任意一个正整数把a写成十进位数的形式：a=an10n+an-110n-1+…+a00≤ai因为101（mod3）所以aan+an-1+…+a0（mod3）由此可知：3a当且仅当3（an+an-1+…+a0）同法可证9的情况定理4：设a=an1000n+an-11000n-1+…+a00≤ai则a能被7（1113）整除的充要条件是：7（1113）整除（a0+a2+…）=（a1+a3+…）=（-1）ia1证明：通过直接计算可知：1000-1（mod7）从而100021（mod7）10003-1（mod7）…1000n（-1）n（mod）7所以aan（-1）n+an-1（-1）n-1+…-a1+a0（mod7）又因为（a1+a2+…）-（a1+a3+…）=（-1）iai所以7a当且仅当7（-1）iai因为1000-1（mod11）和1000-1（mod13）所以同样的推理对模11和模13也成立。定理证毕。三、在密码学上的应用同余理论在密码学上有重要的应用。密码作为军事斗争与政治斗争的一种手段在历史上早就产生了信息化社会的到来使得密码学更加有用。先介绍几个名词甲方通过公共通道向乙方传输信息为了防止被窃取甚至被篡改需要将信息改变为秘密形式。原信息称为明文。明文的秘密形式称为密文。把明文变成密文的过程叫加密。知道了密码把密文译为明文的过程叫解密。密码中的关键信息叫做密钥。密钥在保密通讯中占有极重要的地位。这里我们将介绍一种简单的在历史上曾经用过的密码就是置换密码。我们假定这种密码是用英文发送的办法很简单就是把每个字母用另一个字母替换而形成密文。替换的规则可以是随机的也可以是系统的。公元前在高卢战争期间罗马大将恺撒使用的一种密码就是系统置换的密码。置换的规律是：每个字母由它后面的第三个字母来替换。例如：ADBECFDG…WZXAYBZC。例：PekingUniversity在这一密码下是：ShnlgjXjlyhuvlwb。利用同余式的理论恺撒的密码很