《浅谈同余理论的应用》由会员分享，可在线阅读，更多相关《浅谈同余理论的应用（5页珍藏版）》请在金锄头文库上搜索。
1、浅谈同余理论的应用 在日常生活中，我们所要注意的不仅仅是某些整数，而是某些数用某一固定的数去除所得的余数。例如：我们经常会问现在是几点钟了，这实际上就是用24去除某一个总的时数所得的余数，又如问现在是星期几，就是用7去除某一个总的天数所得的余数。这样，在数学中就产生了同余的概念。同余是可除性的符号语言，在西方是由高斯最先引进的。 他的名著算术探究奠定了近代数论的基础。我们国家对同余式的研究有着光辉而悠久的历史。如孙子算经中的“物不知其数”问题就是同余式研究的开始。下面将着重介绍同余式在日常生活中的应用。其中将用到同余的一些基本概念、基本性质，以及孙子定理等等知识来解决“物不知其数”问题，列举检
2、查因数的方法以及在密码学上的简单应用。 定义 1：给定一个正整数m，把它叫做模。如果用m去除任意两个整数a与b所得的余数相同，我们就说a，b对模m同余。记作ab（mod m）。如果余数不同，我们就说a，b对模m不同余。 定理 1：整数a，b对模m同余的充分与必要条件是m（a-b），即：a=b+mt，t是整数。 证明：设a=mq1+r1，b=mq2+r2，0r1 若ab（mod m），则r1=r2，因此a-b=m（q1-q2） 反之若m（a-b），则mm（q1-q2）+（r1-r2） 因此m（r1-r2），但r1-r2 定理1说明同余这一概念又可定义如下：若m（a-b），则a，b叫做对模m同余。
3、 一、“物不知其数”问题 定理2（孙子定理）：设 m1，m2，mk是k个两两互质的正整数。 m=m1m2mk，m=miMi，i=1，2，k， 则同余式组xb1（mod m1），xb2（mod m2），xbk（mod mk）的解是： xM1M1b1+M2M2b2+MkMkbk（mod m） 其中M1M11（mod mi），i=1，2，k 这个方法与孙子的算法完全一致，它在国外文献中被称为中国剩余定理。孙子定理是数论中一个很重要的定理。由上表可以看出求乘率是最困难的。也就是求解同余式： xMi=1（mod mi）。 我国宋代大数学家秦九韶在他的杰作算书九章（1247）中提出了解这个同余式的一般解法
4、，秦氏将它称作“求一术”。 二、检查因数的方法 作同余知识的应用，这里将列举出一些简便的检查因数的方法。 定理3：一个整数能被3（9）整除的充要条件是它的十进位数码的和能被3（9）整除。 证明：设a是任意一个正整数，把a写成十进位数的形式： a=an10n+an-110n-1+a0，0 ai 因为101（mod3），所以aan+an-1+a0（mod3） 由此可知：3a当且仅当3（an+an-1+a0） 同法可证9的情况 定理4：设a=an1000n+an-11000n-1+a0，0ai 则a能被7（11，13）整除的充要条件是： 7（11，13）整除（a0+a2+）=（a1+a3+）=（-1
5、）ia1 证明：通过直接计算可知：1000-1（mod 7），从而 100021（mod 7），10003-1（mod 7），1000n（-1）n（mod）7 所以aan（-1）n+an-1（-1）n-1+-a1+a0（mod 7） 又因为（a1+a2+）-（a1+a3+）=（-1）iai 所以7a当且仅当7（-1）iai 因为1000-1（mod 11）和1000-1（mod 13），所以同样的推理对模11和模13也成立。定理证毕。 三、在密码学上的应用 同余理论在密码学上有重要的应用。密码作为军事斗争与政治斗争的一种手段在历史上早就产生了，信息化社会的到来，使得密码学更加有用。 先介绍几个
6、名词，甲方通过公共通道向乙方传输信息，为了防止被窃取，甚至被篡改，需要将信息改变为秘密形式。原信息称为明文。明文的秘密形式称为密文。把明文变成密文的过程叫加密。知道了密码把密文译为明文的过程叫解密。密码中的关键信息叫做密钥。密钥在保密通讯中占有极重要的地位。 这里我们将介绍一种简单的，在历史上曾经用过的密码，就是置换密码。我们假定这种密码是用英文发送的，办法很简单，就是把每个字母用另一个字母替换，而形成密文。替换的规则可以是随机的，也可以是系统的。 公元前在高卢战争期间罗马大将恺撒使用的一种密码就是系统置换的密码。置换的规律是：每个字母由它后面的第三个字母来替换。例如：AD，BE， CF，DG
7、， WZ，XA，YB，ZC。例：Peking University在这一密码下是：Shnlgj Xjlyhuvlwb。利用同余式的理论，恺撒的密码很容易得到解释，首先把26个字母都编上号，按顺序，A是01号，B是02号，Y是25号，Z是26号。若用P表示明文中的字母编号，而用S表示密文中的字母编号，则恺撒密码就可以用同余式写出来：SP+3（mod 26），式中的3就是密钥，解密的关键就是找到密钥，找到了密钥之后立刻就可以得到明文。这只需要解同余式PS-3S+23（mod 26）。更一般些，密码可由公式SP+k（mod 26）给出，为了迷惑企图破译的人，密文通常写成5个字母的形式，于是上面一例可
8、以改写成：Shnlg jXjly huvlw b的形式。 对置换密码的解密来说，关键在于确定k的值。解密的方法有两种：一种是穷举法，对k一个一个地试，直到出现有明确意义的明文。另一种是根据英文字母出现的频率来进行解密。在英文中各字母出现的频率是不同的，如e的频率最高，约占13.04%，找出字母中出现次数最多的字母，使之对应于e，然后进行尝试性求解。 数学史上著名的数学家高斯曾说过：“数学是科学之王，数论是数学之王，它常常屈尊去为天文学和其他的自然科学效劳，但在所有的关系中，它都堪称第一。”作为初等数论中的重要组成部分，同余理论不仅有理论价值又有着广泛的实际应用。同余概念的产生以及同余理论的不断发展完善极大地丰富了数学的内容。 （作者单位：河北省邢台市第六中学）第 1 页 共 1 页
