浅谈同余理论的应用

《浅谈同余理论的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈同余理论的应用在日常生活屮，我们所要注意的不仅仅是某些整数，而是某些数用某一固定的数去除所得的余数。例如：我们经常会问现在是儿点钟了，这实际上就是用24去除某一个总的时数所得的余数，又如问现在是星期几,就是用7去除某一个总的天数所得的余数。这样，在数学中就产生了同余的概念。同余是可除性的符号语言，在西方是由高斯最先引进的。他的名著《算术探究》奠定了近代数论的基础。我们国家对同余式的研究冇着光辉而悠久的历史。如《孙子算经》中的“物不知其数”问题就是同余式研究的开始。下面将着重介绍同余式在FI常生活中的应用。其中将用到同余的一些基本概念、基本性质，以及孙子定理等等知识

2、來解决“物不知其数”问题，列举检查因数的方法以及在密码学上的简单应用。定义1：给定一个正整数m,把它叫做模。如果用m去除任意两个整数a与b所得的余数相同，我们就说a,b对模m同余。记作a三b(modm)o如果余数不同，我们就说0,b对模m不同余。定理1：整数a,b对模m同余的充分与必要条件是m(a~b),即:a=b+mt,t是整数。证明：设a=mql+rl,b=mq2+r2,0^rl

3、=r2,由此得证。定理1说明同余这一概念又可定义如下：若m(a-b),则a,b叫做对模m同余。一、“物不知其数”问题定理2(孙子定理人设ml,m2,…賊是k个两两互质的正整数。m=mlm2---mk,m=miMi,i=l,2,・・・k,则同余式组x=bl(modml),x=b2(modm2),…，x=bk(modmk)的解是：x三lMlbl+M72M2b2+MzkMkbk(modm)其中1M1=1(modmi),i二1,2,・・・k这个方法与孙子的算法完全一致，它在国外文献中被称为中国剩余定理。孙子定理是数论中一个很重要的定理。由上表可以看出求乘率是最困难的。也就是求

4、解同余式：xMi=l(modmi)o我国宋代大数学家秦九韶在他的杰作《算书九章》(1247)屮提出了解这个同余式的一般解法，秦氏将它称作“求一术”。二、检查因数的方法作同余知识的应用，这里将列举出一些简便的检查因数的方法。定理3：—个整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除。证明：设a是任意一个正整数，把a写成十进位数的形式：a=an1On+an-11On-1++a0,OWai<10,i=0,1,…，n因为10=1(mod3),所以a三an+anT+・・・+aO(mod3)由此可知：3a当且仅当3(an+anT+…+a0)同法可证9的情况定理

5、4：设a=anlOOOn+an-l1000n-l+---+a0,0^ai<1000则a能被7(11,13)整除的充要条件是：7(11,13)整除(a0+a2+…)=(al+a3+…)=(-1)ial证明:通过直接计算可知：1000三T(mod7),从而10002=1(mod7),10003三一1(mod7),…，1000n=(-1)n(mod)7所以a三an(-1)n+anT(T)n-l+・・・-al+a0(mod7)乂因为(al+a2+…)-(al+a3+…)=(-1)iai所以7a当且仅当7(-1)iai因为1000=-l(mod11)和1000=-l(mod13

6、),所以同样的推理对模11和模13也成立。定理证毕。三、在密码学上的应用同余理论在密码学上有重要的应用。密码作为军事斗争与政治斗争的一种手段在历史上早就产生了，信息化社会的到来，使得密码学更加有用。先介绍几个名词，甲方通过公共通道向乙方传输信息，为了防止被窃取，甚至被篡改，需要将信息改变为秘密形式。原信息称为明文。明文的秘密形式称为密文。把明文变成密文的过程叫加密。知道了密码把密文译为明文的过程叫解密。密码中的关键信息叫做密钥。密钥在保密通讯中占有极重要的地位。这里我们将介绍一种简单的，在历史上曾经用过的密码，就是置换密码。我们假定这种密码是用英文发送的，办法很简单，

7、就是把每个字母用另一个字母替换，而形成密文。替换的规则可以是随机的，也可以是系统的。公元前在高卢战争期间罗马大将恺撒使用的一种密码就是系统置换的密码。置换的规律是：每个字母由它后面的第三个字母来替换。例如：A-D,B-E,C-F,D-G,…，W-Z,X-A,Y-B,Z-C。例：PekingUniversity在这一密码下是：ShnlgjXjlyhuvlwbo利用同余式的理论，恺撒的密码很容易得到解释，首先把26个字母都编上号，按顺序，A是01号，B是02号，…，Y是25号，Z是26号。若用P表示明文中的字母编号，而用S表示密文中的字母编号，则恺撒密码