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?(akak?1...a1a0)10kk?1n?a10?a10...a110?a0，其中0?aj?9，kk?1，那么
j?0,1,2,...,k。
jj10?0(mod2)10?0(mod2)，进j因为，由此可得到对所有的正整数有：
而
16
n?(a0)10(mod2),n?(a1a0)10(mo2d2),3n?(a2a1a0)1(0mod2),M..a2a1 n?(ak?1ak?2.a0)10(mkod 2)以上这些同余式告诉我们，要判断一个整数n能否被2整除，只需要检验这个整数的最后一位数字能否被2整除。同样地，判断n能否被4整除，只需检验它的最后俩位数字能否被4整除。一般的，要检验n能否被2整除，只需要检验组成整数n的最后j位数字能否被2整除就可以了。
例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的幂整除的整除性检验，所以我们在此不再写推导过程，我们得出：
jj55 我们只需要检验组成整数n的最后j位数字能否被整除来判断是否能整
jj除n。
例3.2 令n=15535375
由5能够整除5可以得出5能偶整除n；25能够整除75可以得出25能够整除n；125可以整除375可以得出125能够整除n；但是625不能够整除5375所以625不能够整除n。 被3和9整除的校验
我们可以看出下面的两个同余式同时成立，
310?1(mod9) 10?1(mod，
因此，我们有下面的两个式子同时成立
kk10?1(mod310?1(mod9) ，
由此，可以得到一个有用的同余式
(ak?1ak?2...a2a1a0)10?ak10k?ak?110k?1...a110?a0?ak?ak?1...a1?a0(mod3)和(mod9) 根据上面的同余式，我们得出结论：我们只需要检验各位数字之和能否被3或者9整除，便可以饭别判断n是否能被3或者9整除。
例3.3 令n=4127835
17
我们可以得出n的各位数字之和是30.因为3整除30，而9不能整除30，所以3能够整除n,9不可以。 被11整除的校验
因为10??1(mod11)，所以我们有下面的同余式
(ak?1ak?2...a2a1a0)10?ak10k?ak?110k?1...a110?a0?ak(?1)k?ak?1(?1)k?1...?a1?a0(mod11)这表明
(ak?1ak?2...a2a1a0)10能被11整除的充分必要条件是对n的各位数字交替相
ka?a?a?...?(?1)ak能被11整除。 012加减，得到的整数
例3.4 令n=723160823
易知n可以被11整除，因为交替相加减之后，我们得到22，可以被11整除。 被7,11,13整除的检验 我们将要推导一个可以判断同时被7,11,13整除的整除性检验。
3 因为7?11?13?1001并且10?1000??1(mod1001)，所以
(ak?1ak?2...a2a1a0)10?ak10k?ak?110k?1...a110?a0?(a0?10a1?100a2)?1000(a3?10a4?100a5)?(1000)2(a6?10a7?100a8)?...?(a0?10a1?100a2)?(a3?10a4?100a5)?(a6?10a7?100a8)?...?(a2a1a0)10?(a5a4a3)10?(a8a7a6)10?...(mod1001)
上面这个同余式告诉我们：将原来的整数按照十进制展开，然后从最左端开始每连续的三位数字分成一组，再按照原顺序构成新的三位数，最后将它们连续地交替相加减而得到的整数同余于原来的整数。因为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都是正整数且满足j?k，那么
(akak?1...a1a0)b可以被d整除当且仅当
j(aj?1...a1a0)b可以被d整除。
j此定理将十进制符号表示的被2的方幂和5的方幂整除的整除性检验推广到了其他进制整数的整除性检验。
18
定理3.2 如果d整除b-1，那么各位数字之和除性检验。
定理3.3 如果d整除b+1,那么
ak?ak?1?...a1?a0n?(ak...a1a0)b可以被d整除当且仅当n的
可以被d整除。
此定理将十进制符号表示的被3和9整除的整除性检验推广到其他进制整数的整
n?(ak...a1a0)b可以被d整除当且仅当n的
k(?1)ak?...?a1?a0可以被d整除。 各位数字的交错和
此定理将十进制符号表示的对整数是否被11整除的整除性检验推广到了其他进制的整除性检验。
例3.6 令
n?(7F28A6)16（十六进制）
因为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个月。下面我们做一下设定：
19
K=任何一个月份中的日期 M=月份，并且
一月份=11 二月份=12 三月份=1 四月份=2 五月份=3 六月份=4 七月份=5 八月份=6 九月份=7 十月份=8 十一月份=9 十二月份=10
N=年份（当前年份），该年份的一月份二月份归到前一年中，且其中，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,原因在于我们在计算的时候将本年的一月份看做前一年的第十一个月了。
我们将每一年的三月一号作为新的一年的起点，令dN代表第N年的三月一号的星期数，在这里我们从1600年开始计算。我们可以计算得出，如果第N年不是闰年，那么第N?1与第N年的3月1号相差365天，并且365?1(mod7)，所以
N?100C?Y,
dN?dN?1?1(mod7)，如果第N年是闰年，因为闰月多了一天，所以 dN?dN?1?2(mod 7)找出问题的关键所在，那么我们要想由
d1600求得
dN，第一步我们应该计算出第N年与1600年之间有几个闰年（在这里不包括1600年而包括N年）。我们取闰年数为x，运用带余除法我们有，可以被4整除的年份有[(N?1600)/4]个，被100整除的年份有[(N?1600)/100]个，被400整除的年份有[(N?1600)/400]个。因此我们得到
N?[( x?[(N?1600)/?4]]40?0N[ ?[N/4?]N[ ?[N/4?1600?)/N10?0][? /4[(
/1?00]?N16/?40 0]/10?0N][我们将上述的C和Y代入到上式，可以得到
C?(Y/4?)]C?[Y( x?[25C?[Y/4?]C?C[ ?25]Y[ ?3C?[C/4?/?4]?/1?00C)][?(Y/4)(? //?4] 33(m o
20