同余及其应用.doc

天津科技大学2013届本科生毕业论文 同余及其应用CONGRUENCE AND ITS APPLICATIONS专 业：信息与计算科学 姓 名： X X X 指 导 教 师： X X X 申请学位级别： X X 论文提交日期： XXXXXXXX 学位授予单位： XXXX大学摘 要 本论文归纳总结了同余的相关性质定理，如Wilson定理，Fermat小定理以及Euler定理，以及集合论中的等价关系、商集等相关知识、数论中关于同余的一些性质，并熟悉剩余环相关的知识。还研究了含有未知数的同余方程，例如线性同余方程，多项式同余方程，线性同余方程组等。学习同余在实际和理论中的应用，结合实际探究了同余性质在整除性校验，万年历，散列函数上的应用以及构造校验位等方面的应用。这些应用体现了用同余性质解决问题的简洁性。在文章的最后，研究了当今在数论中最流行的工具Maple语言，学习其如何执行数论中关于同余的计算，并且编程计算相关的问题。关键词：同余； 同余方程； 剩余环； 欧拉定理； 同余的应用； Maple语言 ABSTRACTThe article summarizes the related theorems of congruence, such as Wilson theorem, Fermat theorem and Euler theorem, some properties of the congruence equivalence relations, quotient set and other related knowledge, number theory as well as in set theory, and familiar with the relevant knowledge of the remaining ring. Also study the congruence equation containing the unknown number, such as linear congruence equation, polynomial congruence equation, linear congruence equations and so on. Learning the application of congruence in practical and theory, combined with the actual research in the congruence properties of divisibility checking, calendar, a hash function is applied on the application and construction check etc.Embodies simplicity to solve problems with congruence properties. At the end of the article, studying the most popular theory in todays tools of Maple language and learning how to perform the calculation about congruence in number theory, and programming computing the related problem of congruence. Key words: Congruences; congruence equation; the remaining ring; Euler theorem; congruence application; Maple language 目 录1. 前言12. 同余32.1 同余引言32.1.1 相关定义32.1.2 相关性质定理32.2 线性同余方程52.3 中国剩余定理72.4 求解多项式同余方程82.5 线性同余方程组92.6 利用波拉德方法分解整数143. 同余的应用173.1 整除性检验173.2 万年历203.4 散列函数253.5 校验位284. 特殊的同余式324.1 威尔逊定理和费马小定理324.2 欧拉定理345. Maple 语言或Mathematic语言355.1 求解多项式同余方程355.2 求解同余方程组355.3 求解中国剩余定理36结 论37参考文献38致 谢39 1 前言 整个数学的发展史是和人类物质文明和精神文明的发展史交融在一起的。数学不仅是一种精确的语言和工具、一门博大精深并应用广泛的科学，而且更是一种先进的文化。它在人类文明的进程中一直起着积极的推动作用，是人类文明的一个重要支柱。自古（这里指1975年以前）数论拥有数学最纯粹部分的美称。同余理论是数论里的重要内容之一，同余这一特殊语言在数论中极为有用，其性质及应用的研究已引起许多学者的关注，人们之所以研究同余，是因为它历史悠久且硕果累累，也因为它有大量易于理解而令人着迷的问题，更因为它富裕智慧的魅力。前者的研究只是对同余的某个性质进行探讨，不够全面、彻底。本论文归纳总结了同余的若干性质，结合实例探究了同余性质在整除校验、构造校验位、解方程、求余数、素性判定等方面的应用。现代数论的发展始于德国数学家高斯（Gauss）,他是历史上最伟大的数学家之一，在19世纪初期发明了同余的语言。我们称两个整数a和b是模m同余的（其中m为正整数）是指m整除a-b。这种语言是我们我们在研究整除性关系的时候，变得像研究方程那样容易。人们在日常生活中，不知不觉地在运用着大量的同余数知识。本论文用丰富的例子、通俗的语言、易懂的证明，介绍同余式的概念、计算方法及其应用，证明了费马小定理和中国剩余定理、整除、二次剩余的讨论和计算。提现了用同余性质解决问题的简洁性。在引入同余之前，人们研究整除关系所用的记号笨拙而且难用。而引入方便的记号对加速数论的发展起了重要作用。同时，本文还研究了一些特殊的同余式，如威尔逊定理和费马小定理、伪素数、欧拉定理。本论文主要分为三个方面，第一阶段研究同余。将给出它的一些基本性质（等价性，传递性等）描述如何进行同余式的算术运算，还将研究含有未知数的同余方程，例如线性同余方程，多项式同余方程，线性同余方程组等。引出线性同余方程组，它们来源于古代中国难题：求一个数，它被3,5和7除所得余数为2,3和2。我们将如何运用著名的中国剩余定理来解像上一难题那样的线性同余方程组。我们还将学习怎样解多项式同余方程。最后，我们用同余语言来介绍一种（整数）分解方法，即波拉德方法。第二阶段研究同余的应用。同余有广泛的应用，如利用同余展示怎样在计算机上做大整数的乘法。本论文广泛涉及了同余的各种类型的有趣的应用，首先，我们将指出如何利用同余进行整除性检验，比如已经熟知的如火如何判断一个整数能否被3或9整除的简单检验。然后会推导出一个可以确定历史上任何一天的星期数的同余式。还有利用同余编排循环赛程。我们也将讨论同余性质在计算科学中的一些应用，例如，应用在散列函数上，散列函数本身就有很多种应用，比如确定数据储存的计算机存储地址。最后，我们将给出如何利用同余构造校验位，用来确定一个认证数是否被错误复制。如何利用同余从不同的途径对信息惊醒加密，或者利用同余产生随机数。最后一个阶段研究当今最流行的工具Maple或Mathematic如何用于执行数论中的计算。本论文将简单的描述一些对于同余的计算有用的命令，主要通过描述这两种系统中已经存在的命令，编程计算同余相关的问题。2 同余2.1 同余引言同余在日常生活中随处可见。例如，钟表对于小时是模12或24的，对于分钟和秒是模60的；日历对于星期是模7的，对于月份是模12的水电表是模1000的，里程表通常是模100000的。我们有时需要将同余式转换为等式。人们从孩提时代开始就知道每个星期有七天：从星期一到星期六，再加上一个星期日，接下来又是星期一。如果某一天是星期一，那么在它以后的第8天、第15天、第22天、都是星期一。这些都是星期一的“天数”有一个共性：它们除以7所得的余数都是1。也就是说，它们除以7是“同余的”。2.1.1 相关定义定义 给定一个正整数m把它叫做模，如果用m去除整数a和b ，所得余数相同，我们就说a与b对模m同余，记作。如果余数不相同，那么我们就说a与b对模m不同余，记作。或设m是正整数，若a和b是整数，且，则称a和b模m同余。如果和b模m同余,则记。如果a和b模m不同余，则记，并称模不同余。整数m称为同余的模。2.1.2 相关性质定理 定理 2.1 a和b是整数，则当且仅当存在整数k，使得。 证明 若，则。这说明存在整数k，使得，所以。反过来，若存在整数k使得，则。于是，,。 定理2.2 设m是大于0的整数，则模m的同余有下列性质： （1）自反性. 如果a是整数，则。 （2）对称性. 如果a和b是整数，且，则。 （3）传递性. 如果a，b和c是整数，且和，则。 定理2.3 如果a,b,c和m均是整数，并且m大于0，同余式可以相加减，即若有， 则 （1） （2） （3） 定理2.4 如果a,b,c和m是整数，并且有，那么。 推论2.4.1 如果a,b,c和m是整数，c与m互素，并且有则有。 定理2.5 如果a,b,n和m是整数，并且n和m均大于0， 则有。 定理2.6 如果是整数，均大于0，且有则。 推论2.6.1 如果 ，其中，a,b是整数，是两两互素的整数，则。定理 2.7 若自然数,则。 定理2.8 设 ， ，。如果，则。 定理 2.9 若 （1）当 ，时，。 （2）是及模的任一正公因数，则。 定理 2.10 设，且，则存在唯一一对整数，使得，其中。定义 一个模完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模同余。定理2.11 如果是一个模m完全剩余系，并且正整数a使得a与m互素，那么对于任何的整数b，都是模m的完全剩余系。2.2 线性同余方程 设x是未知整数，形如 （2-1） 的同余式称为一元线性同余方程。 如果我们有是同余方程的一个解，并且，那么，所以也是一个解。因此，由文献1可知：如果一个模m同余类的某个元素是解，则此同余类的所有元素都是解。那么，方程有多少个模m不同余的解等价于模m的m个同余类中有多少个给出方程的解。引用下面的定理，我们会得知一元线性同余方程在那种情况下有解，更进一步的在有解时方程有多少模m不同余的解。 定理2.12 设a,b和m是整数，m0,(a,m)=d.若d不整除b，则无解。若d整除b,则恰有d个模m不同余的解。在证明之前，我们先引入一个定理 定理2.13 设a,b是整数且d=(a,b)。如果d不整除c,那么方程没有整数解。如果d整除c，那么存在无穷多个整数解。另外，如果，是方程的一个特解，那么所有的解可以表示为 ，其中n是整数。证明 由定理2.1 可知，线性同余方程等价于二元线性丢番图1方程。整数x是同余方程（2-1）的解，当且仅当存在y使得。根据定理2.13可知，如果d不整除b，则无解。而当d整除b时，有无穷多解： ， 其中，是方程的特解。上述x的值是且是线性同余方程的解，有无穷多这样的解。 为了确定有多少不同余的解，我们先找出两个解，设这两个解分别为和，再找出这两个解模m同余的条件。首先，若这两个解同余，那么，两边减去，有 因为整除m，所以。再由定理2.4我们可以知道这表明，不同余的解的一个完全集合可以通过取得到，其中t取遍模d的完全剩余系。一个这样的集合可以由给出，其中。同时，我们还可以得到，乘数a和模m互素的线性同余方程有唯一解。这是因为当a和m互素时，那么（a,m）整除b,由上述结论即定理2.12可知，线性同余方程恰有个模m不同余的解。2.3 中国剩余定理 在本节中，我们讨论联立的同余方程组。本节将会研究两种类型的方程组：第一种类型有两个或更多具有不同模的一元线性同余方程组；第二种类型的同余方程变元数多于一，且方程数多于一，但是方程的模相同。 首先，我们考虑仅有一个未知数但有不同模的同余方程组，我们先给出关于一元线性同余方程组的解的主要定理：中国剩余定理。定理2.14（中国剩余定理） 设有r个两两互素的正整数。那么同余方程组 . . 有模的唯一解。那么，中国剩余定理是如何解决关于一元线性同余方程组的解的问题，我们首先通过阐述古代的中国难题来说明中国剩余定理的主要用途。在公元3世纪晚期的孙子算经中，有这样一个问题：求一个数，它能被3除余1，被5除余2，被7除余3。我们可以列出下面的同余方程组 根据中国剩余定理，我们有， ，为确定,我们需要解同余方程或者与其等价的。得到。解同余方程，立即得到。最后，解得。因此， 可以验证，满足的x是同余方程组的解，这只需注意到，。 引理2.1 如果a和b是正整数，则模的最小正剩余是。其中，r是a模b的最小正剩余。同时，中国剩余定理提供了实施大整数的计算机算术运算的方法。存储很大的整数并做它们之间的算术运算需要特殊的技巧。中国剩余定理告诉我们给定两个互素的模，一个小于的正整数n由它的模最小正剩余唯一确定，其中假设一个计算机的字长仅为100，但是我们想做大小为106的整数的算术运算。首先，找到小于100的两两互素的正整数，是它们的积超过106；例如，可以取，和。我们将小于 106的整数转换为4元组，每个分量分别是它模 ， ，的最小正剩余。然后，例如做整数的加法，我们仅仅需要把他们模，的最小正剩余相加，这利用到之前得出的结论：，则。然后利用中国剩余定理将所得的四个最小正剩余的和的集合转换为一个整数。2.4 求解多项式同余方程 若m有素因子分解，则求解形如等价于求解同余方程组， 。一旦解出k个模的同余方程，就可以利用中国剩余定理求出模m的解。例 因为，所以求解同余方程 化为求解 和 。模16的解释整数。（因为若x为解，则必为偶数;容易验证x是奇数的情形不是解）。模5的解释整数，我们利用中国剩余定理求和的联立解，通过运算我们得到。这就是的解。 我们知道，一旦知道了多项式模p同余方程的所有解，就有相对简单的方法来解多项式的模同余方程。我们会知道，模P的解可以用来求模的解，模的解可以用来求模的解，等等。我们先举例说明从模P的解可以用来求模的解的基本思路。例 通过对和4直接验证，可见 的解是。如何求模25的解？我们可以从0到24这25个值依次验证。我们有更加系统给的方法。因为 的每一个解都是模5的解，而且每个模5的解都满足，那么，t是整数。用代替x可以求出t的值，继而我们得到 将其化简得到t的线性同余方程消去因子5，得到 解为这表明模25的解是，我们可以验证出这的确是解。2.5 线性同余方程组 线性同余方程组即未知数个数与方程个数是同一大于1的整数，并且所有方程的模都相同。例 线性同余方程组 的所有整数x和y。尝试求x和y，将第一个方程乘以2，第二个方程乘以3, 我们得到 再用第二个方程减去第一个方程，得到 因为2是7的模13逆，所以我们将上面的同余方程两边同时乘以2，得到 即 同样的，我们将（原来的）第一个方程乘以5，将第二个方程乘以4，我们又会得到如下方程组 用第一个方程减去第二个方程，得到 为求y，上面的同余方程两边同时乘以2，这里7模13的一个逆，得 所以 这就证明了，任何解（x,y）都满足，将以上求得的关于x和y这两个同余方程代入到原来的同余方程组，可以得知他们确实是解： 因此，我们得到同余方程组的解释使得 ，的所有整数对（x,y）。我们给出一个关于含有两个二元方程的同余方程组的一般结论。定理2.15 设a，b，c，d，e，f和m是整数，且，其中。那么同余方程组 有模m的唯一解如下： 其中，是模m的一个逆。利用类似的方法，我们就可以求解含有n个未知数和n个方程的同余方程组。当n很大时，我们就很有必要引入矩阵的语言来求解。我们首先介绍矩阵同余的概念。定义 设A和B是整数矩阵，第个分量分别是和，若 对所有成立，则称A和B模m同余。若A和B模m同余，则记为 。矩阵同余提供了表达nk 个同余式的一种简洁方法。 定理 2.16 设A和B是阶矩阵 ，满足，C是阶矩阵，D是阶矩阵，它们都是整数元素的矩阵。则，。现在考虑同余方程组 利用矩阵记法，此含有n个方程的同余方程组等价于矩阵同余方程，其中 例如方程组 可以将其写为更进一步地，我们学习一种形如的同余方程组的求解方法。这种方法的原理是，基于求出矩阵使得,即是矩阵的逆。其中，是单位矩阵。定义 设和是阶矩阵，且，其中 是n阶矩阵，则称是A模m的一个逆。例如求解模7的逆，因为我们有 ，并且 所以我们得到是模7的逆。 定理2.17 设是整数矩阵，且与正整数m互为素数。则矩阵是A模m的逆，其中是模m的逆。例 设,因为14是模13的逆，所以有 例 考虑同余方程组 这等价于矩阵同余方程 我们可以证明出是模7的一个逆。因此，我们有 根据本节内容，有很多解线性方程组的方法修改后可以用于求解同余方程组。例如，高斯消元法可以修改用于求解同余方程组，其中除法变为乘以模m的逆。而且，有类似于克莱姆法则的求解方法。2.6 利用波拉德方法分解整数 本节描述的分解方法是源于同余的基础。它由波拉德在1974年提出的。波拉德称之为蒙特卡洛方法，因为它依赖于生成貌似随机挑选的整数；现在成为波拉德 方法。为什么称此方法为波拉德方法？我们现在借助下面的图形解释一下为什么这样命名。 此图说明了数列x的周期特性。其中的值为2，与模97同余，i的值大于等于1。这个序列周期性出现之前的部分为字母的尾部，周期性的部分为的环部。设n是一个大合数，p是它的最小素因子。我们的目标是选取整数，使得它们有不同的模n最小非负剩余，但它们模p的最小非负剩余不是全部不同的。使用一些概率公式，在s与相比较大，而与相比较小，数字是随机地选取时，这是可能发生的。一旦找到整数和，满足，且，则是n的非平凡因子，这是因为p整除，但n不整除。我们可以用欧几里得算法迅速求出。我们用下面的方法寻找这样的整数和：第一步，随机选取初始值即种子值，是次数大于1的整系数多项式，紧接着我们用递归定义 ， 求解，其中。多项式的选取应该使得有很高的概率在出现重复之前生成适当多的整数。而根据经验，我们通常选取多项式等于。例 设，那么我们有 值得注意的是，由的递归定义，如果 其中d是一个正整数，则 于是，如果，则序列变为模d周期的，其周期整除；即在q与r同余在模的条件下，并且，q与r的值均大于等于i，与模d同余。因此，如果s是不小于i的j-i的最小倍数，那么与模d同余。因此，为寻找n的一个因子，我们要求与n的最大公因子，。当找到k使得时，我们就得到了n的一个因子。根据之前的观察，我们很可能找到一个接近于的整数k。关于波拉德方法在实际生活中的应用，我们经常选用多项式f(x)使其等于来生成整数序列。并且，经常选用初始值为2的。这样的选取方法在分解过程中，使得选取的多项式和初始值所生成的序列的行为很像随机序列。经过试验得出，如果想要分解具有相当大的素因子的整数，波拉德方法是实用的。在实际应用中，我们如果想要分解大的整数时，首先用小素数试除，例如小于104的素数；其次，我们用波拉德方法来找出中等大小的（例如不超过1015）的素因子。一般的，我们在采用此方法失败之后，我们才采用真正强力的方法，比如二次筛法或者椭圆曲线方法，在此不予介绍。3 同余的应用同余有广泛的应用，在前面我们已经介绍了一个应用方面的例子，如在2.4节中，我们介绍中国剩余定理的同时，就利用同余展示了如何在计算机上做大整数的乘法。本章涉及了同余的多种类型并且很有趣的应用。首先，我们将会指出怎样利用同余进行整除性检验。在本章中，我们不仅讨论同余在实际生活中的一些应用，如整除性校验、万年历、利用同余编排循环赛赛程等等。我们还讨论了同余性质在计算科学中的广泛应用，比如在散列函数上的应用，怎样确定数据储存的计算机存储地址、构造校验位，确定一个认证数是否被错误的复制等等。3.1 整除性检验在小学我们都学过验证一个整数能否被2或者3整除，只需检验这个数的各位数字是否为偶数或者检验该整数各位数字相加之后能否被3整除即可。其实，这就是一个整除性检验的例子。前者应用了一个整数的尾数来检验这个数是否能被2整除，或者应用了一个整数的所有数字去检验这个数是否能被3整除。总之，他们都是运用特定的数字去检验这个数本身是否能被一个特定的数整除，而不是用这个不确定的除数直接去除那个整数。在本小节中，我们将基于这样的检验方法给出有关的理论。特别的，我们会给出基于b进制展开的整数的整除性检验，当然，这里所提到的b是正整数。在这里，如果我们取b得值等于10，我们就会得到著名的用来检验整数能否被2,3,4,5,7,9,11,13等整除的检验。不仅如此，我们还会给出这样做的具体原因。被2的幂整除性检验 我们已经知道可以被2整除那么它的最后一位一定是整数，那么要推导出被2的幂整除的整数要怎么做呢？例如：令n=32688048，n能否被22整除？能否被23整除？能否被24整除？能够被n整除的2的最高次幂是多少呢？我们将要推导出一种检验的方法来回答这些问题，而不是用4,8这些2的幂一个个去除n来判断。令，那么，其中，。因为，由此可得到对所有的正整数有：，进而 以上这些同余式告诉我们，要判断一个整数n能否被2整除，只需要检验这个整数的最后一位数字能否被2整除。同样地，判断n能否被4整除，只需检验它的最后俩位数字能否被4整除。一般的，要检验n能否被整除，只需要检验组成整数n的最后j位数字能否被整除就可以了。例3.1令n=32688048 由2整除8可以得出2整除n；4整除48可以得出4整除n；8整除48可知8整除n；16整除8048可以得出16整除n；但是32不可以整除88048所以32不可以整除n。被5整除的检验 因为能被5的幂整除的整除性检验类似于能被2的幂整除的整除性检验，所以我们在此不再写推导过程，我们得出： 我们只需要检验组成整数n的最后j位数字能否被整除来判断是否能整除n。例3.2 令n=15535375由5能够整除5可以得出5能偶整除n；25能够整除75可以得出25能够整除n；125可以整除375可以得出125能够整除n；但是625不能够整除5375所以625不能够整除n。被3和9整除的校验 我们可以看出下面的两个同余式同时成立， ，因此，我们有下面的两个式子同时成立 ，由此，可以得到一个有用的同余式和根据上面的同余式，我们得出结论：我们只需要检验各位数字之和能否被3或者9整除，便可以饭别判断n是否能被3或者9整除。例3.3 令n=4127835 我们可以得出n的各位数字之和是30.因为3整除30，而9不能整除30，所以3能够整除n,9不可以。被11整除的校验 因为，所以我们有下面的同余式这表明能被11整除的充分必要条件是对n的各位数字交替相加减，得到的整数能被11整除。例3.4 令n=723160823易知n可以被11整除，因为交替相加减之后，我们得到22，可以被11整除。被7,11,13整除的检验 我们将要推导一个可以判断同时被7,11,13整除的整除性检验。 因为并且，所以上面这个同余式告诉我们：将原来的整数按照十进制展开，然后从最左端开始每连续的三位数字分成一组，再按照原顺序构成新的三位数，最后将它们连续地交替相加减而得到的整数同余于原来的整数。因为7,11,13都是1001的因子，所以我们想要判断一个整数能否被7,11,13整除，只需要检验这些三位数的交替相加减是否能被7,11或者13整除。例3.5 令n=59358208 按照上面所述的方法，没三位数字分组得到的整数的交替加减得到-91，因为-91可以被7和13整除，但是不可以被11整除，由此得知，7可以整除n，13可以整除n,但是11不可以整除n。基于b进制表示的整除性检验(b是一个正整数)定理3.1 如果d整除b，并且j，k都是正整数且满足，那么可以被整除当且仅当可以被整除。此定理将十进制符号表示的被2的方幂和5的方幂整除的整除性检验推广到了其他进制整数的整除性检验。定理3.2 如果d整除b-1，那么可以被d整除当且仅当n的各位数字之和可以被d整除。此定理将十进制符号表示的被3和9整除的整除性检验推广到其他进制整数的整除性检验。定理3.3 如果d整除b+1,那么 可以被d整除当且仅当n的各位数字的交错和可以被d整除。此定理将十进制符号表示的对整数是否被11整除的整除性检验推广到了其他进制的整除性检验。例3.6 令（十六进制）因为2可以整除16，根据定理3.1并且2可以整除n的尾数6，所以2可以整除十六进制的n。同样地，因为4可以整除16，但是4不整除n的尾数6，所以4不能整除十六进制的n。由定理3.2可知,3可以整除（16-1），5可以整除（16-1），15可以整除（16-1），并且我们可以求出n的所有位数之和为十六进制下的30，又因为3可以整除十六进制的30，所以3可以整除上述中n。但是5和15不可以整除十六进制的30，所以5和15不可以整除上述中的n。更进一步的，根据定理3.3,因为17可以整除（16+1），并且n的各位数字交错和为A，我们知道17不可以整除A，所以我们得到结论17不可以整除十六进制的n。3.2 万年历 埃及历法每年精确到365天，尤利乌斯凯撒推行了一种新的历法叫做凯撒历法。这个历法每四年会有一个闰年，每年的平均长度是365.25天。但是，随着世纪的更迭，每年会有0.0078天的误差被累加起来。为了纠正它，格里哥利教皇在1582年创建了一个新的历法，命名格里哥利历法。即原来误差产生的天数被加进原来的日期里，凯撒历法截止1582年会产生10天的误差。所以格里哥利历法将1582年10月5号变为1582年10月15号，闰年由原来除了年份可以整除100年，即标志世纪开始的年，年份能够整除4的都是闰年，变为那些年份能够整除100的只有在同时被400整除时才算是闰年，如：1900年,2100年都不是闰年而1600,2000是闰年。按照这个方法，误差每年缩小为0.0003天。 现在，我们学习一种公式来求在格里哥利历法下给定的一个日期所在的星期数。我们首先做出一些调整，从每年的三月份开始重新计数，将一月份和二月份算作前年的一部分，之所以这样做是因为我们把闰年多出来的一天加在了二月的最后一天。如：1995年的2月被认为是1994年的第十二个月，而1995年的6月则相应的被认为是第4个月。下面我们做一下设定：K=任何一个月份中的日期M=月份，并且一月份=11 二月份=12 三月份=1 四月份=2 五月份=3 六月份=4七月份=5 八月份=6 九月份=7 十月份=8 十一月份=9 十二月份=10N=年份（当前年份），该年份的一月份二月份归到前一年中，且,其中，C=世纪，Y=每一世纪中特定的年份。例如 对于1952年4月9号，我们有k=9,m=2,N=1952,C=19,Y=52。需要注意的是，1952年1月20号，有k=20,m=11,C=19,Y=51,原因在于我们在计算的时候将本年的一月份看做前一年的第十一个月了。我们将每一年的三月一号作为新的一年的起点，令代表第年的三月一号的星期数，在这里我们从1600年开始计算。我们可以计算得出，如果第年不是闰年，那么第与第年的3月1号相差365天，并且，所以，如果第年是闰年，因为闰月多了一天，所以 找出问题的关键所在，那么我们要想由求得，第一步我们应该计算出第年与1600年之间有几个闰年（在这里不包括1600年而包括年）。我们取闰年数为x，运用带余除法我们有，可以被4整除的年份有个，被100整除的年份有个，被400整除的年份有个。因此我们得到 我们将上述的C和Y代入到上式，可以得到 根据上述得出的式子，我们计算，因为所以每到下一年我们加上一天，得到,在加上中间出现的因为闰年而多出的天数x，我们得到下面的公式 整理我们得到 上面的这个公式就是我们联系任何一年3月1号的星期数与1600年3月1号的星期数的公式，但是想要求我们还需要计算出的值，在这里我们采取代入求值的方法，根据事实，对于1992年3月1日，有N=1992，C=19，Y=92,又因为，所以得到 因此，即1600年3月1号是星期三。接着将代入到计算的式子中，得到 （3-1）上述式子就是我们用来计算第年每一月的第一天的星期数的方法结论，那么我们只能计算每月第一天的星期数吗？有没有方法来计算特定月份的每一天的星期数呢？事实证明是可以的。我们利用它与前一个约得第一天的天数的差值来计算。因为有，也就是说如果这个月有30天，那么它下个月的第一天的星期数要比这个月第一天的星期数增加2；同理根据我们很快得到，如果是31天的话，星期数相应的增加3。所以在计算特定月份的某一天的星期数时，我们必须加上多余的天数。因为1,3,5,7,8,10,12月份分别有31天，所以在计算它们下一月的时候要加上3天，同样的，2,4,6,9,11月份用来计算某一月份的特定天数的星期数时我们加上2。如果我们利用上述这种方法是麻烦的，我们需要找出一个相同具有相同增量的表达式。注意到一共有11个增量共29天，所以每个增量是2.6天。不难发现，当m取2到12的数值时，函数得出与上面相同的增量。当时，函数的值为0。因此，模7的最小负剩余表示第年第m月第一天的星期数。记W为第年第m月第k天的星期数，我们只需要在该月第一天的想起书公式中加上，得到 我们可以利用这个公式来计算任何一年的任何一天的星期数。例3.7 求出你出生的那一天的星期数，并计算出你今年生日的星期数。1990年12月8号其中，因此有：从而，我出生那天是星期六。2013年12月8号其中，因此有:即今年我的生日是星期日。3.3 循环赛程 在本小节中，我们将讨论如何利用同余来安排个队的循环赛的赛程，使得每个队与其他任何一个队都比赛一次，这个方法是由弗轮德发明的。我们首先需要讨论的是的奇偶性，如果是奇数，则可以添加一个虚拟的队，使得参加比赛的队的总数是偶数，在某一轮与虚拟的队配对的队在本轮中轮空，不参加比赛。所以，我们总可以假设有偶数个小队参加比赛，在必要的时候添加一个虚拟的队。我们将个队进行编号:。按照下面的方法进行配对，如果，那么在第轮中，第队与第队比赛。除了第队和满足的第队外，这个赛程表让其他所有队在第轮中进行比赛。因为，根据定理2.31，同余方程在内有且仅有一个解。所以，这样的第队是存在的。我们让第队与第队在第轮中进行比赛。那么为什么这样做就使得每个队与其他任何一个队都比赛一次且只比赛一次呢？我们考虑前个队，在第轮中第队与第队制比赛一次，其中，并且，即第队不会两次与同一队进行比赛。如果第队与第队在第轮和第轮都进行了比赛，那么就会有和。因为，所以显然矛盾。所以我们得到，前个队中的每一个队都进行了次比赛。并且和同一个队比赛不超过两次。也就是说，和每一个队只进行一次比赛。同理，第队进行了次比赛，又因为任何其他队与第队只进行一次比赛，所以第队与其他任何一队只进行了一次比赛。例 为了安排七个队进行比赛，我们将这六个队进行编号：1,2,3,4,5，6,7。虚拟队用8编号。在第一轮中，第1队与第j队比赛，其中我们有。当j的值为7时同余式成立，故第一队与第7队比赛。又因为同余式的解的值为6，所以第二队与第六队进行比赛。如此进行下去，我们得到，第三队与第五队进行比赛。而是同余式的解，那么第四队与虚拟队第八队配对。也就是说，第四队在第一轮中轮空。继续这个步骤，我们就可以完成其他轮的赛程安排。如表3.1所示，第k轮第i队的对手在第k行第i列给出。表3.1 七队循环赛赛程安排轮队12345671765bye3212bye76543232176bye4343byye5654bye21767654321bye3.4 散列函数 假设我们想要在计算机中存储一份文件，每份文件的识别号码或者说关键词是位数较多的整数，所以为每个可能的识别号码或者关键字建立一个存储地址是不可行的。但是我们可以利用一种较为系统化的方法。此方法利用适当数量的存储单元，将这些文件排列在存储器中，这样我们就会很容易的访问每个文件。而这个排列所采用的这种较为系统的方法就是基于散列函数发展起来的。在这种方法中，每个散列函数为每份文件分配一个特定的存储单元。现在我们经常使用的函数类型模运算，就是散列函数的一种。我们接下来将要讨论这种类型的函数。 假设一个大学想要在计算机中为它的每一个学生储存一份文件，每份文件的识别号码或者说关键词是每个学生的社会安全号码，首先，令k是被存储文件的关键词，在这个例子中，是一个学生的社会安全号码，令m是一个正整数，我们定义散列函数: ,其中，因此是模m的最小正剩余.我们想要找到一个m，使得文件合理的分布在m个不同的存储单元中。 上述中的m不可以是用来表示一个关键词的基底b的方幂，例如：当我们选取社会安全号码作为关键词时，m不可以是10的方幂，如104 。否则这个时候的散列函数的值会变为关键词的最后几位数字。并且很有可能会使得关键词在存储单元中分布不均匀。这就是为什么早期 社会安全号码的最后三位数字为什么 通常在000到999之间，而不是在900到999之间。我们有时也会遇到以下几个问题，下面介绍一下问题及其解决方法。选取m为可以整除 （其中k和a对模m来说是较小的整数）的数。 这是不明智的做法。根据上述这个式子，的值通常会依赖于关键词的某几位数。而且相似的关键字经过顺序重排也可能会被发送到同一个存储单元。如取，因为111整除。所以我们得到。又因为 和 那么如何解决上述这个问题呢？我们只需要令m是接近于存储单元数目的一个素数即可。如：我们想要存储2000个学生的文件时，如果我们有5000个存储单元，那么m应该取素数4969。(1)发生冲突，即将两份不同的文件分配到相同的存储单元。为了解决这种冲突，使得每份文件分配到唯一的存储单元，我们有两种解决方法。第一种方法：发生冲突时，增加额外的存储单元并且将这个存储单元与原来的存储单元建立链接。我们想要存取发生了冲突的文件时，首先会对涉及的关键字的散列函数进行计算，其次搜索与该存储单元有链接的列表。第二种方法是：寻找下一个开放的存储地址。为了达到这个目的，我们采取被称作双重散列的方法。首先，我们选择，其中m是素数，是散列函数。我们接着选取第二个散列函数： ，其中，所以我们有与m互素。选取为检测序列，其中的值在零到m之间，并且可以为零。因为我们有与m互素。当j取遍所有整数时，将选出所有的存储单元。当m-2也为素数时，是最佳情况。这种最佳情况使得的值合理进布。综上，我们希望m与m-2是一对孪生素数。例 我们引入一个例子，利用社会安全号码，给具有下列社会安全号码的学生文件分配存储地址： 我们选取，。得到检测数据 ，根据上式我们得到 ，通过计算，得到 ，和。我们首先将这几个数分配为文件的地址。因为，但是前面我们已经将1526作为存储地址，那么我们公式得出，其中，。这样我们得出第四个地址1742。同理，我们可以得出第五，六，七，八个文件分配的地址，分别为：。我们可以发现，第九个地址578的值之前已经被占据，我们采用与第四个地址相同的方法，得到新的分配给第九个文件的地址2580。同样的，我们得到第十个文件分配的自由地址为1958。其中，我们得到这第十个地址经过两次运算，第一次运算得到的1742之前已经是第四个文件的地址，我们需要继续采用公式，其中，j的值为2。我们得到所求的第十个文件的地址。 表3.2 学生文件的散列函数社会安全号码269152628541526174239604075237657857825801526174219583.5 校验位检验字符（数据）串的误差我们同样可以应用同余理论进行解决。在这节中，我们将学习比特串的误差检测。那么什么是比特串？比特串是用来做什么的？我们将不再详细介绍，只需要知道比特串是用来代表计算机数据的。十进制的数据串即比特串常用来识别护照、支票、书籍或者其他的各种各样的目的。下面我们将要介绍一下同余理论时如何检测十进制的数据串的误差。我们在传播或者处理比特串时可以产生误差。简单的检测方法是在比特串后面加上一个奇偶校验位。它的定义是： 那么我们可以得出，如果字符串的前n个位有偶数个1，则，否则的话，。变化后的字符串满足下面的同余