同余及其應(yīng)用

本文格式為Word版，下載可任意編輯——同余及其應(yīng)用

同余及其應(yīng)用

CONGRUENCEANDITS

APPLICATIONS

專業(yè)：信息與計(jì)算科學(xué)

姓名：XXX指導(dǎo)教師：XXX申請(qǐng)學(xué)位級(jí)別：XX論文提交日期：XXXXXXXX學(xué)位授予單位：XXXX大學(xué)

摘要

本論文歸納總結(jié)了同余的相關(guān)性質(zhì)定理，如Wilson定理，F(xiàn)ermat小定理以及Euler定理，以及集合論中的等價(jià)關(guān)系、商集等相關(guān)知識(shí)、數(shù)論中關(guān)于同余的一些性質(zhì)，并熟悉剩余環(huán)相關(guān)的知識(shí)。還研究了含有未知數(shù)的同余方程，例如線性同余方程，多項(xiàng)式同余方程，線性同余方程組等。學(xué)習(xí)同余在實(shí)際和理論中的應(yīng)用，結(jié)合實(shí)際探究了同余性質(zhì)在整除性校驗(yàn)，萬(wàn)年歷，散列函數(shù)上的應(yīng)用以及構(gòu)造校驗(yàn)位等方面的應(yīng)用。這些應(yīng)用表達(dá)了用同余性質(zhì)解決問(wèn)題的簡(jiǎn)單性。在文章的最終，研究了當(dāng)今在數(shù)論中最流行的工具M(jìn)aple語(yǔ)言，學(xué)習(xí)其如何執(zhí)行數(shù)論中關(guān)于同余的計(jì)算，并且編程計(jì)算相關(guān)的問(wèn)題。

1前言

整個(gè)數(shù)學(xué)的發(fā)展史是和人類物質(zhì)文明和精神文明的發(fā)展史交融在一起的。數(shù)學(xué)不僅是一種確切的語(yǔ)言和工具、一門博大精深并應(yīng)用廣泛的科學(xué)，而且更是一種先進(jìn)的文化。它在人類文明的進(jìn)程中一直起著積極的推動(dòng)作用，是人類文明的一個(gè)重要支柱。自古（這里指1975年以前）數(shù)論擁有數(shù)學(xué)最純粹部分的美稱。同余理論是數(shù)論里的重要內(nèi)容之一，同余這一特別語(yǔ)言在數(shù)論中極為有用，其性質(zhì)及應(yīng)用的研究已引起大量學(xué)者的關(guān)注，人們之所以研究同余，是由于它歷史悠久且碩果累累，也由于它有大量易于理解而令人著迷的問(wèn)題，更由于它富足聰慧的魅力。前者的研究只是對(duì)同余的某特性質(zhì)進(jìn)行探討，不夠全面、完全。本論文歸納總結(jié)了同余的若干性質(zhì)，結(jié)合實(shí)例探究了同余性質(zhì)在整除校驗(yàn)、構(gòu)造校驗(yàn)位、解方程、求余數(shù)、素性判定等方面的應(yīng)用?，F(xiàn)代數(shù)論的發(fā)展始于德國(guó)數(shù)學(xué)家高斯（Gauss）,他是歷史上最宏偉的數(shù)學(xué)家之一，在19世紀(jì)初期發(fā)明白同余的語(yǔ)言。我們稱兩個(gè)整數(shù)a和b是模m同余的（其中m為正整數(shù)）是指m整除a-b。這種語(yǔ)言是我們我們?cè)谘芯空躁P(guān)系的時(shí)候，變得像研究方程那樣簡(jiǎn)單。

人們?cè)谌粘Ｉ钪?，不知不覺(jué)地在運(yùn)用著大量的同余數(shù)知識(shí)。本論文用豐富的例子、通俗的語(yǔ)言、易懂的證明，介紹同余式的概念、計(jì)算方法及其應(yīng)用，證明白費(fèi)馬小定理和中國(guó)剩余定理、整除、二次剩余的探討和計(jì)算。提現(xiàn)了用同余性質(zhì)解決問(wèn)題的簡(jiǎn)單性。在引入同余之前，人們研究整除關(guān)系所用的記號(hào)笨拙而且難用。而引入便利的記號(hào)對(duì)加速數(shù)論的發(fā)展起了重要作用。同時(shí)，本文還研究了一些特別的同余式，如威爾遜定理和費(fèi)馬小定理、偽素?cái)?shù)、歐拉定理。

本論文主要分為三個(gè)方面，第一階段研究同余。將給出它的一些基本性質(zhì)（等價(jià)性，傳遞性等）描述如何進(jìn)行同余式的算術(shù)運(yùn)算，還將研究含有未知數(shù)的同余方程，例如線性同余方程，多項(xiàng)式同余方程，線性同余方程組等。引出線性同余方程組，它們來(lái)源于古代中國(guó)難題：求一個(gè)數(shù)，它被3,5和7除所得余數(shù)為2,3和2。我們將如何運(yùn)用著名的中國(guó)剩余定理來(lái)解像上一難題那樣的線性同余方程組。我們還將學(xué)習(xí)怎樣解多項(xiàng)式同余方程。最終，我們用同余語(yǔ)言來(lái)介紹一種（整數(shù)）分解方法，即波拉德ρ方法。其次階段研究同余的應(yīng)用。同余有廣泛的應(yīng)用，如利用同余展示怎樣在計(jì)算機(jī)上做大整數(shù)的乘法。本論文廣泛涉及了同余的各種類型的好玩兒的應(yīng)用，首先，我們將指出如何利用同余進(jìn)行整除性檢驗(yàn)，譬如已經(jīng)熟知的如火如何判斷一個(gè)整數(shù)能否被3或9整除的簡(jiǎn)單檢驗(yàn)。然后會(huì)推導(dǎo)出一個(gè)可以確定歷史上任何一天的星期數(shù)的同余式。還有利用同余編排循環(huán)賽程。我們也將探討同余性質(zhì)在計(jì)算科學(xué)中的一些應(yīng)用，例如，應(yīng)用在散列函數(shù)上，散列函數(shù)本身就有好多種應(yīng)用，譬如確定數(shù)據(jù)儲(chǔ)存的計(jì)算機(jī)存儲(chǔ)地址。最終，我們將給

1

出如何利用同余構(gòu)造校驗(yàn)位，用來(lái)確定一個(gè)認(rèn)證數(shù)是否被錯(cuò)誤復(fù)制。如何利用同余從不同的途徑對(duì)信息驚醒加密，或者利用同余產(chǎn)生隨機(jī)數(shù)。最終一個(gè)階段研究當(dāng)今最流行的工具M(jìn)aple或Mathematic如何用于執(zhí)行數(shù)論中的計(jì)算。本論文將簡(jiǎn)單的描述一些對(duì)于同余的計(jì)算有用的命令，主要通過(guò)描述這兩種系統(tǒng)中已經(jīng)存在的命令，編程計(jì)算同余相關(guān)的問(wèn)題。

2

2同余

2.1同余引言

同余在日常生活中隨處可見。例如，鐘表對(duì)于小時(shí)是模12或24的，對(duì)于分鐘和秒是模60的；日歷對(duì)于星期是模7的，對(duì)于月份是模12的水電表是模1000的，里程表尋常是模100000的。我們有時(shí)需要將同余式轉(zhuǎn)換為等式。

人們從孩提時(shí)代開始就知道每個(gè)星期有七天：從星期一到星期六，再加上一個(gè)星期日，接下來(lái)又是星期一。假使某一天是星期一，那么在它以后的第8天、第15天、第22天、……都是星期一。這些都是星期一的―天數(shù)‖有一個(gè)共性：它們除以7所得的余數(shù)都是1。也就是說(shuō)，它們除以7是―同余的‖。2.1.1相關(guān)定義

定義給定一個(gè)正整數(shù)m把它叫做模，假使用m去除整數(shù)a和b，所得余數(shù)一致，我們就說(shuō)a與b對(duì)模m同余，記作a?b(modm)。假使余數(shù)不一致，那么我們就說(shuō)a與b對(duì)模m不同余，記作a?b(modm)。或設(shè)m是正整數(shù)，若a和b是整數(shù)，且

m(a?b)，則稱a和b模m同余。假使a和b模m同余,則記

a?b(modm)。假使a和b模m不同余，則記m|(a,b)，并稱a模m不同余b。整

數(shù)m稱為同余的模。2.1.2相關(guān)性質(zhì)定理

定理2.1a和b是整數(shù)，則a?b(modm)當(dāng)且僅當(dāng)存在整數(shù)k，使得

a?b?km。

證明若a?b(modm)，則

m(a?b)。這說(shuō)明存在整數(shù)k，使得

km?a?b，所以a?b?km。

?b反過(guò)來(lái)，若存在整數(shù)k使得a?b?km，則km?a。于是，m(a?b)a?b(modm),。

定理2.2設(shè)m是大于0的整數(shù)，則模m的同余有以下性質(zhì)：（1）自反性.假使a是整數(shù)，則a?a(modm)。

（2）對(duì)稱性.假使a和b是整數(shù)，且a?b(modm)，則b?a(modm)。

3

（3）傳遞性.假使a，b和c是整數(shù)，且a?b(modm)和b?a(modm)，則

a?c(modm)。

定理2.3假使a,b,c和m均是整數(shù)，并且m大于0，同余式可以相加減，即若有a?b(modm)，c?d(modm)則（1）a?c?b?d(modm)（2）a?c?b?d(modm)（3）ac?bd(modm)

m?0，d?(c,m)并且有ac?bc(modm)，定理2.4假使a,b,c和m是整數(shù)，

那么a?b(modm/d)。

m?0，c與m互素，并且有ac?bc(modm)推論2.4.1假使a,b,c和m是整數(shù)，

則有a?b(modm)。

定理2.5假使a,b,n和m是整數(shù)，并且n和m均大于0，a?b(modm)

nna?b(modm)。則有

定理2.6假使a,b,m1,m2,...,mk是整數(shù)，m1,m2,...,mk均大于0，且有

a?b(modm1),a?b(modm2),...,a?b(modmk)則a?b(mod?m1,m2,mk?)。推論2.6.1假使a?b(modm1),a?b(modm2),...,a?b(modmk)，其中，a,b是整數(shù)，

定理2.7若自然數(shù)n?2,ai?bi(modm),i?1,2n,

ai??bi(modm)則?i?1i?1nnm1,m2,...,mk是兩兩互素的整數(shù)，則a?b(modm1m2...mk)。

。

ni定理2.8設(shè)

f(x)??aixi?1，

g(x)??bixii?1n，x?z。假使

ai?bi(modm)，

i?0,1,2,n則f(x)?g(x)(modm)。

4

定理2.9若a?b(modm)

（1）當(dāng)dm，d?0時(shí)，a?b(modd)。

ab?m?mod?（2）d是a,b及模m的任一正公因數(shù)，則d?d??d???。

定理2.10設(shè)a,b?Z，且b?0，則存在唯一一對(duì)整數(shù)q,r，使得a=bq+r，其中0?r?b。

定義一個(gè)模m完全剩余系是一個(gè)整數(shù)的集合，使得每個(gè)整數(shù)恰和此集合中的一個(gè)元素模m同余。

定理2.11假使r1,r2,...,rm是一個(gè)模m完全剩余系，并且正整數(shù)a使得a與m互素，那么對(duì)于任何的整數(shù)b，ar1?b,ar2?b,...,arm?b都是模m的完全剩余系。2.2線性同余方程設(shè)x是未知整數(shù)，形如

(modmax?b)（2-1）

的同余式稱為一元線性同余方程。假使我們有那么

x?x0是同余方程ax?b(modm)的一個(gè)解，并且

x1?x0(modm)，

ax1?ax0?b(modm)，所以x1也是一個(gè)解。因此，由文獻(xiàn)[1]可知：假使一個(gè)

模m同余類的某個(gè)元素是解，則此同余類的所有元素都是解。那么，方程有多少個(gè)模m不同余的解等價(jià)于模m的m個(gè)同余類中有多少個(gè)給出方程的解。引用下面的定理，我們會(huì)得知一元線性同余方程在那種狀況下有解，更進(jìn)一步的在有解時(shí)方程有多少模m不同余的解。

定理2.12設(shè)a,b和m是整數(shù)，m>0,(a,m)=d.若d不整除b，則ax?b(modm)無(wú)解。若d整除b,則ax?b(modm)恰有d個(gè)模m不同余的解。在證明之前，我們先引入一個(gè)定理

定理2.13設(shè)a,b是整數(shù)且d=(a,b)。假使d不整除c,那么方程ax?by?c沒(méi)有整數(shù)解。假使d整除c，那么存在無(wú)窮多個(gè)整數(shù)解。另外，假使x?x0，y?y0

5

是方程的一個(gè)特解，那么所有的解可以表示為其中n是整數(shù)。

證明由定理2.1可知，線性同余方程ax?b(modm)等價(jià)于二元線性丟番圖

[1]

x?x0?(m)ty?y0?(a)nd，d

方程ax?my?b。整數(shù)x是同余方程（2-1）的解，當(dāng)且僅當(dāng)存在y使得

ax?my?b。

根據(jù)定理2.13可知，假使d不整除b，則無(wú)解。而當(dāng)d整除b時(shí)，有無(wú)窮多解：

x?x0?(m)ty?y0?(a)td，d

ax-my?b，

x0?(m)tx?x0,y?y0d且是線性同余方程的其中，是方程的特解。上述x的值是

解，有無(wú)窮多這樣的解。

為了確定有多少不同余的解，我們先找出兩個(gè)解，設(shè)這兩個(gè)解分別為

x1?x0?(m)t1x2?x0?(m)t2d和d，再找出這兩個(gè)解模m同余的條件。

x0?(m)t1?x0?(m)t2(modm)x0dd首先，若這兩個(gè)解同余，那么，兩邊減去，有(m)t1?(m)t2(modm)dd

m(m,m)?mdd。再由定理2.4我們可以知道t1?t2(modd)由于d整除m，所以

x?x0?(m)td得到，其中t取遍這說(shuō)明，不同余的解的一個(gè)完全集合可以通過(guò)取

x?x0?(m)td給出，其中模d的完全剩余系。一個(gè)這樣的集合可以由t?0,1,2,...d?,。

同時(shí)，我們還可以得到，乘數(shù)a和模m互素的線性同余方程有唯一解。這是由于當(dāng)a和m互素時(shí)，那么（a,m）整除b,由上述結(jié)論即定理2.12可知，線性同余方程ax?b(modm)恰有(a,m)?1個(gè)模m不同余的解。2.3中國(guó)剩余定理

在本節(jié)中，我們探討聯(lián)立的同余方程組。本節(jié)將會(huì)研究?jī)煞N類型的方程組：第一種類型有兩個(gè)或更多具有不同模的一元線性同余方程組；其次種類型的同余

6

方程變?cè)獢?shù)多于一，且方程數(shù)多于一，但是方程的模一致。

首先，我們考慮僅有一個(gè)未知數(shù)但有不同模的同余方程組，我們先給出關(guān)于一元線性同余方程組的解的主要定理：中國(guó)剩余定理。

定理2.14（中國(guó)剩余定理）設(shè)有r個(gè)兩兩互素的正整數(shù)m1,m2,...,mr。那么同余方程組

x?a1(modm1)

x?a2(modm2)..有模

M?m1m2...mrx?ar(momdr

)的唯一解。

那么，中國(guó)剩余定理是如何解決關(guān)于一元線性同余方程組的解的問(wèn)題，我們首先通過(guò)闡述古代的中國(guó)難題來(lái)說(shuō)明中國(guó)剩余定理的主要用途。

在公元3世紀(jì)晚期的《孫子算經(jīng)》中，有這樣一個(gè)問(wèn)題：求一個(gè)數(shù)，它能被3除余1，被5除余2，被7除余3。我們可以列出下面的同余方程組

x?1(mod3)x?2(mod5)x?3(mod7)根據(jù)中國(guó)剩余定理，我們有

M?3?5?7?105，M1?105/3?35，M2?105/5?21，M3?105/7?15,，為確定

y1,我們需要解同余方程

35y1?1(mod3)或者與其等價(jià)的，馬上得到

2y1?1(mod3)。得到

y1?2(mod3)。解同余方程

21y2?1(mod5)y2?1(mod5)。最終，解

15y3?1(mod7)y3?1(mod7)得。因此，

?1?3?15?1?15?7x?1?35?2?2?2152(m可以驗(yàn)證，滿足x?52(mod105)的x是同余方程組的解，這只需注意到

52?1(mod3)，52?2(mod5)，52?3(mod7)。

7

abr2?12?12?1。其模的最小正剩余是引理2.1假使a和b是正整數(shù)，則

中，r是a模b的最小正剩余。

同時(shí)，中國(guó)剩余定理提供了實(shí)施大整數(shù)的計(jì)算機(jī)算術(shù)運(yùn)算的方法。存儲(chǔ)很大的整數(shù)并做它們之間的算術(shù)運(yùn)算需要特別的技巧。中國(guó)剩余定理告訴我們給定兩個(gè)互素的模m1,m2,...,mr，一個(gè)小于M?m1m2...mr的正整數(shù)n由它的模mj最小正剩余唯一確定，其中

j?1,2,...r假設(shè)一個(gè)計(jì)算機(jī)的字長(zhǎng)僅為100，但是我們想做

大小為106的整數(shù)的算術(shù)運(yùn)算。首先，找到小于100的兩兩互素的正整數(shù)，是它

m1?99，m2?98，m3?97m?956

們的積超過(guò)10；例如，可以取和4。我們將小于106的整數(shù)轉(zhuǎn)換為4元組，每個(gè)分量分別是它模m1，m2，m3，m4的最小正剩余。然后，例如做整數(shù)的加法，我們僅僅需要把他們模m1，m2，m3，m4的最小正剩余相加，這利用到之前得出的結(jié)論：

x?y?xi?yi(modmi)x?xi(modmi)，

y?yi(modmi)則

。然后利用中國(guó)剩余定理將所得的四個(gè)最小正剩余的和的

集合轉(zhuǎn)換為一個(gè)整數(shù)。2.4求解多項(xiàng)式同余方程

a1a2akm?pp...p12k，若m有素因子分解則求解形如f(x)?0(modm)等價(jià)于求解aiaif(x)?0(modp)pi?1,2,...,ki同余方程組，。一旦解出k個(gè)模的同余方程，

就可以利用中國(guó)剩余定理求出模m的解。

4例由于80?2?5，所以求解同余方程

32x?7x?4?0(mod80)

化為求解

32x?7x?4?0(mod16)

和

32x?7x?4?0(mod5)。

模16的解釋整數(shù)x?12(mod16)。（由于若x為解，則必為偶數(shù);簡(jiǎn)單驗(yàn)證x是奇數(shù)的情形不是解）。模5的解釋整數(shù)x?1(mod5)，我們利用中國(guó)剩余定理求

8

x?12(mod16)和x?1(mod5)的聯(lián)立解，通過(guò)運(yùn)算我們得到x?76(mod80)。這就

32x?7x?4?0(mod80)的解。是

我們知道，一旦知道了多項(xiàng)式模p同余方程的所有解，就有相對(duì)簡(jiǎn)單的方法

kp來(lái)解多項(xiàng)式的模同余方程。

我們會(huì)知道，模P的解可以用來(lái)求模p的解，模p的解可以用來(lái)求模p的解，

2p等等。我們先舉例說(shuō)明從模P的解可以用來(lái)求模的解的基本思路。

223例通過(guò)對(duì)x?0,1,2,3和4直接驗(yàn)證，可見

32x?7x?4?0(mod5)

的解是x?1(mod5)。如何求模25的解？我們可以從0到24這25個(gè)值依次驗(yàn)證。我們有更加系統(tǒng)給的方法。由于

32x?7x?4?0(mod25)

的每一個(gè)解都是模5的解，而且每個(gè)模5的解都滿足x?1(mod5)，那么x?1?5t，t是整數(shù)。用1?5t代替x可以求出t的值，繼而我們得到

?t53?)2(17?(1t?5?)40(mod25)將其化簡(jiǎn)得到t的線性同余方程65t?5?15t?5?0(mod25)消去因子5，得到3t?1?0(mod5解為t?3(mod5)這說(shuō)明模25的解是x?1?5t?1?5?3?16(mod25)，我們可以驗(yàn)證出這的確是解。2.5線性同余方程組

線性同余方程組即未知數(shù)個(gè)數(shù)與方程個(gè)數(shù)是同一大于1的整數(shù)，并且所有方程的模都一致。

例線性同余方程組

4x?3y?9(mod135x?2y?7(mod的所有整數(shù)x和y。嘗試求x和y，將第13)一個(gè)方程乘以2，其次個(gè)方程乘以3,我們得到

9

8x?6y?18(mod1315x?6y?21(mod13)再用其次個(gè)方程減去第一個(gè)方程，得到7x?3(mod13

由于2是7的模13逆，所以我們將上面的同余方程兩邊同時(shí)乘以2，得到2?7x?2?3(mod1即

x?6(mod13同樣的，我們將（原來(lái)的）第一個(gè)方程乘以5，將其次個(gè)方程乘以4，我們又會(huì)得到如下方程組

20x?1y5?45(mod120x?8y?28(mod13)用第一個(gè)方程減去其次個(gè)方程，得到

7y?17(mod13

為求y，上面的同余方程兩邊同時(shí)乘以2，這里7模13的一個(gè)逆，得2?7y?2?17(mod1所以

y?8(mod13這就證明白，任何解（x,y）都滿足

x?6(mod13)，y?8(mod13)

將以上求得的關(guān)于x和y這兩個(gè)同余方程代入到原來(lái)的同余方程組，可以得知他們確實(shí)是解：

4x?3y?4??6?3?8?485x?2y?5??6?2?8?469(mod7(mod13)因此，我們得到同余方程組的解釋使得

x?6(mod13y?8(mod13)的所有整數(shù)對(duì)（x,y），。

我們給出一個(gè)關(guān)于含有兩個(gè)二元方程的同余方程組的一般結(jié)論。

10

定理2.15設(shè)a，b，c，d，e，f和m是整數(shù)，m?0，且(?,m)?1，其中

??ad?bc。那么同余方程組

ax?b?y(emodm)cx?d?y(fmodm)有模m的唯一解如下：

'x??(de?b)f(modm)'y??(af?c)e(mod其中，m)

?'是?模m的一個(gè)逆。

利用類似的方法，我們就可以求解含有n個(gè)未知數(shù)和n個(gè)方程的同余方程組。當(dāng)n很大時(shí)，我們就很有必要引入矩陣的語(yǔ)言來(lái)求解。我們首先介紹矩陣同余的概念。

定義設(shè)A和B是n?k整數(shù)矩陣，第(i,j)個(gè)分量分別是aij和bij，若

aij?bij(modm)對(duì)所有(i,j)成立，1?i?n，1?j?k，則稱A和B模m同余。若A和B模m同余，則記為A?B(modm)。

矩陣同余A?B(modm)提供了表達(dá)nk個(gè)同余式aij?bij(modm)的一種簡(jiǎn)單方法。定理2.16設(shè)A和B是

n?k階矩陣

，滿足

A?B(modm)，C是k?p階矩

陣，D是p?n階矩陣，它們都是整數(shù)元素的矩陣。則AC?BC(modm)，

DA?DB(modm)。

現(xiàn)在考慮同余方程組

a11x1?ax(mod12?...2?anxn1?b1mM))a21x1?ax22?...2?anxn2?b(mod2man1x1?anx?annxn?bn(mmod)2?2...利用矩陣記法，此含有n個(gè)方程的同余方程組等價(jià)于矩陣同余方程

AX?B(modm)，其中

11

?x1??b1??a11a12...an?1?x??b??a?a...a2122n22???2???A?X?B??M??M???O??????aa...axn1n2nn???n??bn?

例如方程組

4x?3y?9(mod13?43??x??9??52??y???7?(mod13)5x?2y?7(mod可以將其寫為13)??????

更進(jìn)一步地，我們學(xué)習(xí)一種形如

AX?B(modm)的同余方程組的求解方法。這種方法的原理是，基于求出矩陣A使得AA?I,即A是矩陣A的逆。其中，I是單位矩陣。定義設(shè)A和A是n?n階矩陣，且AA?AA?I(modm)，其中

?10...?01...?I??MO??00L?0?0?A?是n階矩陣，則稱是A模m的一個(gè)?1?逆。例如求解

?22??12?模7的逆，由于我們有???2?1?并且

2??16??814?????3???21?????7?8??10?(mod7)?0?1，

?1?3?6??22??814?????1?2?7?8?1???????10?(mod7)?0?1

?16??22??31??12??是??模7的逆。所以我們得到??ab?A??cd???是整數(shù)矩陣，定理2.17設(shè)

12

且??detA?ad?bc與正整數(shù)m互為素?cái)?shù)。則矩陣是A模m的逆，其中?是?模m的逆。

?35?A???47??,由于14是detA?1模13的逆，所以有例設(shè)

'?7?5??7??5A?14???(mod13)????43???43?

例考慮同余方程組

6x1?2x2?6x3?3(mod7)2x1?x3?4(mod7)2x1?4x2?2x3?1(mod7)這等價(jià)于矩陣同余方程

?6?1??2??25?20??12我們可以證明出?3??4(mod7)0??41?

6??626??105?1????3??是??242??模7的一個(gè)逆。因此，我們有26??x1????x???5??2???2????x3???3?3?x1??256????2??4?x???201???4??7????0(mod7)2???????????x??123??1???????1?4????0?3??

根據(jù)本節(jié)內(nèi)容，有好多解線性方程組的方法修改后可以用于求解同余方程組。例

如，高斯消元法可以修改用于求解同余方程組，其中除法變?yōu)槌艘阅的逆。而且，有類似于克萊姆法則的求解方法。2.6利用波拉德方法分解整數(shù)

本節(jié)描述的分解方法是源于同余的基礎(chǔ)。它由波拉德在1974年提出的。波拉德稱之為蒙特卡洛方法，由于它依靠于生成貌似隨機(jī)挑揀的整數(shù)；現(xiàn)在成為波拉德方法。

為什么稱此方法為波拉德方法？我們現(xiàn)在借助下面的圖形解釋一下為什么這樣命名。

13

?x2?26x1?5?x0?2

x3?677?95(mod97)?

?x4?7474?5(mod97)

xi2?1xx0i?1此圖說(shuō)明白數(shù)列x的周期特性。其中的值為2，與模97同余，i

的值大于等于1。這個(gè)序列周期性出現(xiàn)之前的部分為字母?的尾部，周期性的部分為?的環(huán)部。

設(shè)n是一個(gè)大合數(shù)，p是它的最小素因子。我們的目標(biāo)是選取整數(shù)

x1,x2,...,xs，使得它們有不同的模n最小非負(fù)剩余，但它

p們模p的最小非負(fù)剩余不是全部不同的。使用一些概率公式，在s與相比較

x,x,...,xs大，而與n相比較小，數(shù)字12是隨機(jī)地選取時(shí)，這是可能發(fā)生的。一旦

找到整數(shù)xi和

xj0?i?j?sx?xj(modp)x?xjm(od)，，滿足i，且in，則

(xi?x,j)n是n的非平凡因子，這是由于p整除幾里得算法迅速求出

xi?xj，但n不整除

xi?xj。我們可以用歐

(xi?xj,n)。

xj我們用下面的方法尋覓這樣的整數(shù)xi和

：第一步，隨機(jī)選取初始值即種子

值x0，f(x)是次數(shù)大于1的整系數(shù)多項(xiàng)式，緊接著我們用遞歸定義

x?f(kx)(modn)0?xk?1?n，

求解xk，其中k?1,2,...。多項(xiàng)式f(x)的選取應(yīng)當(dāng)使得有很高的概率在出現(xiàn)重復(fù)

14

2之前生成適當(dāng)多的整數(shù)xi。而根據(jù)經(jīng)驗(yàn)，我們尋常選取多項(xiàng)式f(x)等于x?1。

2x0?2f(x)?x?1，那么我們有n?8051例設(shè)，，

,3?67x74,?x1?5,x2?26x值得注意的是，由xk的遞歸定義，假使其中d是一個(gè)正整數(shù)，則

74x74,5?2x68?39,871xi?xj(mod)

xi?1?f(xi)?f(xj)?xj?1(modd)

于是，假使，則序列xk變?yōu)槟周期的，其周期整除j?i；即在q與r同余在模

j?i的條件下，并且，q與r的值均大于等于i，xq與xr模d同余。因此，假使s是不小于i的j-i的最小倍數(shù)，那么xs與x2s模d同余。因此，為尋覓n的一個(gè)因子，我們要求

x2k?xk與n的最大公因子，k?1,2,3,。當(dāng)找到k使得

1?(x2k?xk,n)?n時(shí)，我們就得到了n的一個(gè)因子。根據(jù)之前的觀測(cè)，我們很可

p能找到一個(gè)接近于的整數(shù)k。

關(guān)于波拉德?方法在實(shí)際生活中的應(yīng)用，我們經(jīng)常選用多項(xiàng)式f(x)使其等于

x2?1來(lái)生成整數(shù)序列x0,x1,...,xk,...。并且，經(jīng)常選用初始值為2的x0。這樣的

選取方法在分解過(guò)程中，使得選取的多項(xiàng)式和初始值所生成的序列的行為很像隨機(jī)序列。

經(jīng)過(guò)試驗(yàn)得出，假使想要分解具有相當(dāng)大的素因子的整數(shù)，波拉德?方法是實(shí)用的。在實(shí)際應(yīng)用中，我們假使想要分解大的整數(shù)時(shí)，首先用小素?cái)?shù)試除，例如小于104的素?cái)?shù)；其次，我們用波拉德?方法來(lái)找出中等大小的（例如不超過(guò)1015）的素因子。一般的，我們?cè)诓捎么朔椒ㄊ≈螅覀儾挪捎谜嬲龔?qiáng)力的方法，譬如二次篩法或者橢圓曲線方法，在此不予介紹。

15

3同余的應(yīng)用

同余有廣泛的應(yīng)用，在前面我們已經(jīng)介紹了一個(gè)應(yīng)用方面的例子，如在2.4節(jié)中，我們介紹中國(guó)剩余定理的同時(shí)，就利用同余展示了如何在計(jì)算機(jī)上做大整數(shù)的乘法。本章涉及了同余的多種類型并且很好玩兒的應(yīng)用。首先，我們將會(huì)指出怎樣利用同余進(jìn)行整除性檢驗(yàn)。在本章中，我們不僅探討同余在實(shí)際生活中的一些應(yīng)用，如整除性校驗(yàn)、萬(wàn)年歷、利用同余編排循環(huán)賽賽程等等。我們還探討了同余性質(zhì)在計(jì)算科學(xué)中的廣泛應(yīng)用，譬如在散列函數(shù)上的應(yīng)用，怎樣確定數(shù)據(jù)儲(chǔ)存的計(jì)算機(jī)存儲(chǔ)地址、構(gòu)造校驗(yàn)位，確定一個(gè)認(rèn)證數(shù)是否被錯(cuò)誤的復(fù)制等等。3.1整除性檢驗(yàn)

在小學(xué)我們都學(xué)過(guò)驗(yàn)證一個(gè)整數(shù)能否被2或者3整除，只需檢驗(yàn)這個(gè)數(shù)的各位數(shù)字是否為偶數(shù)或者檢驗(yàn)該整數(shù)各位數(shù)字相加之后能否被3整除即可。其實(shí)，這就是一個(gè)整除性檢驗(yàn)的例子。前者應(yīng)用了一個(gè)整數(shù)的尾數(shù)來(lái)檢驗(yàn)這個(gè)數(shù)是否能被2整除，或者應(yīng)用了一個(gè)整數(shù)的所有數(shù)字去檢驗(yàn)這個(gè)數(shù)是否能被3整除?？傊?，他們都是運(yùn)用特定的數(shù)字去檢驗(yàn)這個(gè)數(shù)本身是否能被一個(gè)特定的數(shù)整除，而不是用這個(gè)不確定的除數(shù)直接去除那個(gè)整數(shù)。在本小節(jié)中，我們將基于這樣的檢驗(yàn)方法給出有關(guān)的理論。特別的，我們會(huì)給出基于b進(jìn)制展開的整數(shù)的整除性檢驗(yàn)，當(dāng)然，這里所提到的b是正整數(shù)。在這里，假使我們?nèi)得值等于10，我們就會(huì)得到著名的用來(lái)檢驗(yàn)整數(shù)能否被2,3,4,5,7,9,11,13等整除的檢驗(yàn)。不僅如此，我們還會(huì)給出這樣做的具體原因。

被2的冪整除性檢驗(yàn)我們已經(jīng)知道可以被2整除那么它的最終一位一定是整數(shù)，那么要推導(dǎo)出被2的冪整除的整數(shù)要怎么做呢？例如：令n=32688048，n能否被22整除？能否被23整除？能否被24整除？能夠被n整除的2的最高次冪是多少呢？我們將要推導(dǎo)出一種檢驗(yàn)的方法來(lái)回復(fù)這些問(wèn)題，而不是用4,8這些2的冪一個(gè)個(gè)去除n來(lái)判斷。

令

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ìn)j由于，由此可得到對(duì)所有的正整數(shù)有：

而

16

n?(a0)10(mod2),n?(a1a0)10(mo2d2),3n?(a2a1a0)1(0mod2),M..a2a1n?(ak?1ak?2.a0)10(mkod2)以上這些同余式告訴我們，要判斷一個(gè)整數(shù)n能否被2整除，只需要檢驗(yàn)這個(gè)整數(shù)的最終一位數(shù)字能否被2整除。同樣地，判斷n能否被4整除，只需檢驗(yàn)它的最終倆位數(shù)字能否被4整除。一般的，要檢驗(yàn)n能否被2整除，只需要檢驗(yàn)組成整數(shù)n的最終j位數(shù)字能否被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整除的檢驗(yàn)由于能被5的冪整除的整除性檢驗(yàn)類似于能被2的冪整除的整除性檢驗(yàn)，所以我們?cè)诖瞬辉賹懲茖?dǎo)過(guò)程，我們得出：

jj55我們只需要檢驗(yàn)組成整數(shù)n的最終j位數(shù)字能否被整除來(lái)判斷是否能整

jj除n。

例3.2令n=15535375

由5能夠整除5可以得出5能偶整除n；25能夠整除75可以得出25能夠整除n；125可以整除375可以得出125能夠整除n；但是625不能夠整除5375所以625不能夠整除n。被3和9整除的校驗(yàn)

我們可以看出下面的兩個(gè)同余式同時(shí)成立，

310?1(mod9)10?1(mod，

因此，我們有下面的兩個(gè)式子同時(shí)成立

kk10?1(mod310?1(mod9)，

由此，可以得到一個(gè)有用的同余式

(ak?1ak?2...a2a1a0)10?ak10k?ak?110k?1...a110?a0?ak?ak?1...a1?a0(mod3)和(mod9)根據(jù)上面的同余式，我們得出結(jié)論：我們只需要檢驗(yàn)各位數(shù)字之和能否被3或者9整除，便可以飯別判斷n是否能被3或者9整除。

例3.3令n=4127835

17

我們可以得出n的各位數(shù)字之和是30.由于3整除30，而9不能整除30，所以3能夠整除n,9不可以。被11整除的校驗(yàn)

由于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)這說(shuō)明

(ak?1ak?2...a2a1a0)10能被11整除的充分必要條件是對(duì)n的各位數(shù)字交替相

ka?a?a?...?(?1)ak能被11整除。012加減，得到的整數(shù)

例3.4令n=723160823

易知n可以被11整除，由于交替相加減之后，我們得到22，可以被11整除。被7,11,13整除的檢驗(yàn)我們將要推導(dǎo)一個(gè)可以判斷同時(shí)被7,11,13整除的整除性檢驗(yàn)。

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)

上面這個(gè)同余式告訴我們：將原來(lái)的整數(shù)依照十進(jìn)制展開，然后從最左端開始每連續(xù)的三位數(shù)字分成一組，再依照原順序構(gòu)成新的三位數(shù)，最終將它們連續(xù)地交替相加減而得到的整數(shù)同余于原來(lái)的整數(shù)。由于7,11,13都是1001的因子，所以我們想要判斷一個(gè)整數(shù)能否被7,11,13整除，只需要檢驗(yàn)這些三位數(shù)的交替相加減是否能被7,11或者13整除。例3.5令n=59358208

依照上面所述的方法，沒(méi)三位數(shù)字分組得到的整數(shù)的交替加減得到-91，由于-91可以被7和13整除，但是不可以被11整除，由此得知，7可以整除n，13可以整除n,但是11不可以整除n。

基于b進(jìn)制表示的整除性檢驗(yàn)(b是一個(gè)正整數(shù))

定理3.1假使d整除b，并且j，k都是正整數(shù)且滿足j?k，那么

(akak?1...a1a0)b可以被d整除當(dāng)且僅當(dāng)

j(aj?1...a1a0)b可以被d整除。

j此定理將十進(jìn)制符號(hào)表示的被2的方冪和5的方冪整除的整除性檢驗(yàn)推廣到了其他進(jìn)制整數(shù)的整除性檢驗(yàn)。

18

定理3.2假使d整除b-1，那么各位數(shù)字之和除性檢驗(yàn)。

定理3.3假使d整除b+1,那么

ak?ak?1?...a1?a0n?(ak...a1a0)b可以被d整除當(dāng)且僅當(dāng)n的

可以被d整除。

此定理將十進(jìn)制符號(hào)表示的被3和9整除的整除性檢驗(yàn)推廣到其他進(jìn)制整數(shù)的整

n?(ak...a1a0)b可以被d整除當(dāng)且僅當(dāng)n的

k(?1)ak?...?a1?a0可以被d整除。各位數(shù)字的交織和

此定理將十進(jìn)制符號(hào)表示的對(duì)整數(shù)是否被11整除的整除性檢驗(yàn)推廣到了其他進(jìn)制的整除性檢驗(yàn)。

例3.6令

n?(7F28A6)16（十六進(jìn)制）

由于2可以整除16，根據(jù)定理3.1并且2可以整除n的尾數(shù)6，所以2可以整除十六進(jìn)制的n。同樣地，由于4可以整除16，但是4不整除n的尾數(shù)6，所以4不能整除十六進(jìn)制的n。由定理3.2可知,3可以整除（16-1），5可以整除（16-1），15可以整除（16-1），并且我們可以求出n的所有位數(shù)之和為十六進(jìn)制下的30，又由于3可以整除十六進(jìn)制的30，所以3可以整除上述中n。但是5和15不可以整除十六進(jìn)制的30，所以5和15不可以整除上述中的n。更進(jìn)一步的，根據(jù)定理3.3,由于17可以整除（16+1），并且n的各位數(shù)字交織和為A，我們知道17不可以整除A，所以我們得到結(jié)論17不可以整除十六進(jìn)制的n。3.2萬(wàn)年歷

埃及歷法每年確切到365天，尤利烏斯·凱撒推行了一種新的歷法叫做凱撒歷法。這個(gè)歷法每四年會(huì)有一個(gè)閏年，每年的平均長(zhǎng)度是365.25天。但是，隨著世紀(jì)的更迭，每年會(huì)有0.0078天的誤差被累加起來(lái)。為了改正它，格里哥利教皇在1582年創(chuàng)立了一個(gè)新的歷法，命名格里哥利歷法。即原來(lái)誤差產(chǎn)生的天數(shù)被加進(jìn)原來(lái)的日期里，凱撒歷法截止1582年會(huì)產(chǎn)生10天的誤差。所以格里哥利歷法將1582年10月5號(hào)變?yōu)?582年10月15號(hào)，閏年由原來(lái)除了年份可以整除100年，即標(biāo)志世紀(jì)開始的年，年份能夠整除4的都是閏年，變?yōu)槟切┠攴菽軌蛘?00的只有在同時(shí)被400整除時(shí)才算是閏年，如：1900年,2100年都不是閏年而1600,2000是閏年。依照這個(gè)方法，誤差每年縮小為0.0003天?，F(xiàn)在，我們學(xué)習(xí)一種公式來(lái)求在格里哥利歷法下給定的一個(gè)日期所在的星期數(shù)。我們首先做出一些調(diào)整，從每年的三月份開始重新計(jì)數(shù)，將一月份和二月份算作前年的一部分，之所以這樣做是由于我們把閏年多出來(lái)的一天加在了二月的最終一天。如：1995年的2月被認(rèn)為是1994年的第十二個(gè)月，而1995年的6月則相應(yīng)的被認(rèn)為是第4個(gè)月。下面我們做一下設(shè)定：

19

K=任何一個(gè)月份中的日期M=月份，并且

一月份=11二月份=12三月份=1四月份=2五月份=3六月份=4七月份=5八月份=6九月份=7十月份=8十一月份=9十二月份=10

N=年份（當(dāng)前年份），該年份的一月份二月份歸到前一年中，且其中，C=世紀(jì)，Y=每一世紀(jì)中特定的年份。

例如對(duì)于1952年4月9號(hào)，我們有k=9,m=2,N=1952,C=19,Y=52。需要注意的是，1952年1月20號(hào)，有k=20,m=11,C=19,Y=51,原因在于我們?cè)谟?jì)算的時(shí)候?qū)⒈灸甑囊辉路菘醋銮耙荒甑牡谑粋€(gè)月了。

我們將每一年的三月一號(hào)作為新的一年的起點(diǎn)，令dN代表第N年的三月一號(hào)的星期數(shù)，在這里我們從1600年開始計(jì)算。我們可以計(jì)算得出，假使第N年不是閏年，那么第N?1與第N年的3月1號(hào)相差365天，并且365?1(mod7)，所以

N?100C?Y,

dN?dN?1?1(mod7)，假使第N年是閏年，由于閏月多了一天，所以dN?dN?1?2(mod7)找出問(wèn)題的關(guān)鍵所在，那么我們要想由

d1600求得

dN，第一步我們應(yīng)當(dāng)計(jì)算出第N年與1600年之間有幾個(gè)閏年（在這里不包括1600年而包括N年）。我們?nèi)￠c年數(shù)為x，運(yùn)用帶余除法我們有，可以被4整除的年份有[(N?1600)/4]個(gè)，被100整除的年份有[(N?1600)/100]個(gè)，被400整除的年份有[(N?1600)/400]個(gè)。因此我們得到

N?[(x?[(N?1600)/?4]]40?0N[?[N/4?]N[?[N/4?1600?)/N10?0][?/4[(

/1?00]?N16/?400]/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(mo

20

根據(jù)上述得出的式子，我們計(jì)算dN，由于dN?dN?1?1(mod7)所以每到下一年我們加上一天，得到d1600?N?1600,在加上中間出現(xiàn)的由于閏年而多出的天數(shù)x，我們得到下面的公式dN?d1600?N?1600?x?d1600?100C?Y?1600?3C?[C/4]?[Y/4]?3(mod7)整理我們得到

dN?d1600?2C?Y?[C/4]?[Y/4](mod7)

上面的這個(gè)公式就是我們聯(lián)系任何一年3月1號(hào)的星期數(shù)與1600年3月1號(hào)的星期數(shù)的公式，但是想要求

dN我們還需要計(jì)算出

d1600的值，在這里我們采取代

入求值的方法，根據(jù)事實(shí)，對(duì)于1992年3月1日，有N=1992，C=19，Y=92,又由于d1992?0，所以得到

?9?20380?d160?[19?/4][?9d2/1?4]0603(mod7)dd因此，d1600?3，即1600年3月1號(hào)是星期三。接著將1600代入到計(jì)算N的式

子中，得到

[dN?3?2C?Y?[C/4]?Y/4](mo（3-1）

上述式子就是我們用來(lái)計(jì)算第年每一月的第一天的星期數(shù)的方法結(jié)論，那么我們只能計(jì)算每月第一天的星期數(shù)嗎？有沒(méi)有方法來(lái)計(jì)算特定月份的每一天的星期數(shù)呢？事實(shí)證明是可以的。我們利用它與前一個(gè)約得第一天的天數(shù)的差值來(lái)計(jì)算。由于有

30?2(mod7)，也就是說(shuō)假使這個(gè)月有30天，那么它下個(gè)月的第一

天的星期數(shù)要比這個(gè)月第一天的星期數(shù)增加2；同理根據(jù)31?3(mod7)我們很快得到，假使是31天的話，星期數(shù)相應(yīng)的增加3。所以在計(jì)算特定月份的某一天的星期數(shù)時(shí)，我們必需加上多余的天數(shù)。

由于1,3,5,7,8,10,12月份分別有31天，所以在計(jì)算它們下一月的時(shí)候要加上3天，同樣的，2,4,6,9,11月份用來(lái)計(jì)算某一月份的特定天數(shù)的星期數(shù)時(shí)我們加上2。假使我們利用上述這種方法是麻煩的，我們需要找出一個(gè)一致具有一致增量的表達(dá)式。注意到一共有11個(gè)增量共29天，所以每個(gè)增量是2.6天。不難發(fā)現(xiàn)，當(dāng)m取2到12的數(shù)值時(shí)，函數(shù)[2.6m?0.2]?2得出與上面一致的增量。當(dāng)m?1時(shí)，

21

函數(shù)的值為0。因此，dN?[2.6m?0.2]?2模7的最小負(fù)剩余表示第N年第m月第一天的星期數(shù)。記W為第N年第m月

第k天的星期數(shù)，我們只需要在該月第一天的想起書公式中加上k?1，得到

m?0.2?]C2?Y?Y[W?k?[2.6/?4C][/4](我們可以利用這個(gè)公式來(lái)計(jì)算任何一年的任何一天的星期數(shù)。

例3.7求出你出生的那一天的星期數(shù)，并計(jì)算出你今年生日的星期數(shù)。1990年12月8號(hào)

其中，C?19,Y?90,m?10,k?8因此有：

W?8?[26?0.2]?38?90?[90/4]?[19/4](mod7)?111(mod7)?6(mod7)

從而，我出生那天是星期六。2023年12月8號(hào)

其中，C?20,Y?13,m?10,k?8因此有:

W?8?[26?0.2]?40?13?[13/4]?[20/4](mod7)?14(mod7)?0(mod7)

即今年我的生日是星期日。3.3循環(huán)賽程

在本小節(jié)中，我們將探討如何利用同余來(lái)安排N個(gè)隊(duì)的循環(huán)賽的賽程，使得每個(gè)隊(duì)與其他任何一個(gè)隊(duì)都比賽一次，這個(gè)方法是由弗輪德發(fā)明的。

我們首先需要探討的是N的奇偶性，假使N是奇數(shù)，則可以添加一個(gè)虛擬的隊(duì)，使得參與比賽的隊(duì)的總數(shù)是偶數(shù)，在某一輪與虛擬的隊(duì)配對(duì)的隊(duì)在本輪中輪空，不參與比賽。所以，我們總可以假設(shè)有偶數(shù)個(gè)小隊(duì)參與比賽，在必要的時(shí)候添加一個(gè)虛擬的隊(duì)。

我們將N個(gè)隊(duì)進(jìn)行編號(hào):1,2,3...N?1,N。依照下面的方法進(jìn)行配對(duì)，假使

i?j?k(modN?1),i?N,j?N,且j?i，那么在第k輪中，第i隊(duì)與第k隊(duì)比賽。

除了第N隊(duì)和滿足2i?k(modN?1)的第i隊(duì)外，這個(gè)賽程表讓其他所有隊(duì)在第k輪中進(jìn)行比賽。由于(2,N?1)?1，根據(jù)定理2.31，同余方程2x?k(modN?1)

22

在1?x?N?1內(nèi)有且僅有一個(gè)解。所以，這樣的第i隊(duì)是存在的。我們讓第i隊(duì)與第N隊(duì)在第k輪中進(jìn)行比賽。

那么為什么這樣做就使得每個(gè)隊(duì)與其他任何一個(gè)隊(duì)都比賽一次且只比賽一次呢？我們考慮前N?1個(gè)隊(duì)，在第k輪中第i隊(duì)與第N隊(duì)制比賽一次，其中

1?x?N?1，并且2i?k(modN?1)，即第i隊(duì)不會(huì)兩次與同一隊(duì)進(jìn)行比賽。假使

'ikjk第隊(duì)與第隊(duì)在第輪和第輪都進(jìn)行了比賽，那么就會(huì)有i?j?k(modN?1)''i?j?k(modN?1)k?k(modN?1)，所以顯然矛盾。和。由于

所以我們得到，前N?1個(gè)隊(duì)中的每一個(gè)隊(duì)都進(jìn)行了N?1次比賽。并且和同一個(gè)隊(duì)比賽不超過(guò)兩次。也就是說(shuō)，和每一個(gè)隊(duì)只進(jìn)行一次比賽。同理，第N隊(duì)進(jìn)行了N?1次比賽，又由于任何其他隊(duì)與第N隊(duì)只進(jìn)行一次比賽，所以第N隊(duì)與其他任何一隊(duì)只進(jìn)行了一次比賽。

例為了安排七個(gè)隊(duì)進(jìn)行比賽，我們將這六個(gè)隊(duì)進(jìn)行編號(hào)：1,2,3,4,5，6,7。虛擬隊(duì)用8編號(hào)。在第一輪中，第1隊(duì)與第j隊(duì)比賽，其中我們有1?j?1(mod7)。當(dāng)j的值為7時(shí)同余式成立，故第一隊(duì)與第7隊(duì)比賽。又由于同余式2?j?1(mod7)的解的值為6，所以其次隊(duì)與第六隊(duì)進(jìn)行比賽。如此進(jìn)行下去，我們得到，第三隊(duì)與第五隊(duì)進(jìn)行比賽。而j?4是同余式2j?1(mod7)的解，那么第四隊(duì)與虛擬隊(duì)第八隊(duì)配對(duì)。也就是說(shuō)，第四隊(duì)在第一輪中輪空。繼續(xù)這個(gè)步驟，我們就可以完成其他輪的賽程安排。如表3.1所示，第k輪第i隊(duì)的對(duì)手在第k行第i列給出。

23

表3.1七隊(duì)循環(huán)賽賽程安排

輪123456717bye234562671bye345356712bye4隊(duì)4bye567123534bye671262345bye717123456bye

3.4散列函數(shù)

假設(shè)我們想要在計(jì)算機(jī)中存儲(chǔ)一份文件，每份文件的識(shí)別名碼或者說(shuō)關(guān)鍵詞是位數(shù)較多的整數(shù)，所以為每個(gè)可能的識(shí)別名碼或者關(guān)鍵字建立一個(gè)存儲(chǔ)地址是不可行的。但是我們可以利用一種較為系統(tǒng)化的方法。此方法利用適當(dāng)數(shù)量的存儲(chǔ)單元，將這些文件排列在存儲(chǔ)器中，這樣我們就會(huì)很簡(jiǎn)單的訪問(wèn)每個(gè)文件。而這個(gè)排列所采用的這種較為系統(tǒng)的方法就是基于散列函數(shù)發(fā)展起來(lái)的。在這種方法中，每個(gè)散列函數(shù)為每份文件分派一個(gè)特定的存儲(chǔ)單元?，F(xiàn)在我們經(jīng)常使用的函數(shù)類型模運(yùn)算，就是散列函數(shù)的一種。我們接下來(lái)將要探討這種類型的函數(shù)。假設(shè)一個(gè)大學(xué)想要在計(jì)算機(jī)中為它的每一個(gè)學(xué)生儲(chǔ)存一份文件，每份文件的識(shí)別名碼或者說(shuō)關(guān)鍵詞是每個(gè)學(xué)生的社會(huì)安全號(hào)碼，首先，令k是被存儲(chǔ)文件的關(guān)鍵詞，在這個(gè)例子中，k是一個(gè)學(xué)生的社會(huì)安全號(hào)碼，令m是一個(gè)正整數(shù)，我們定義散列函數(shù)h(k):

m)0?h(k)?mh(k)?k(mod,其中，

因此是k模m的最小正剩余.我們想要找到一個(gè)m，使得文件合理的分布在m個(gè)不同的存儲(chǔ)單元0,1,...m?1中。

上述中的m不可以是用來(lái)表示一個(gè)關(guān)鍵詞的基底b的方冪，例如：當(dāng)我們選取社會(huì)安全號(hào)碼作為關(guān)鍵詞時(shí)，m不可以是10的方冪，如104。否則這個(gè)時(shí)候的散列函數(shù)的值會(huì)變?yōu)殛P(guān)鍵詞的最終幾位數(shù)字。并且很有可能會(huì)使得關(guān)鍵詞在存儲(chǔ)單元中分布不均勻。這就是為什么早期社會(huì)安全號(hào)碼的最終三位數(shù)字為什么尋常在000到999之間，而不是在900到999之間。

我們有時(shí)也會(huì)遇到以下幾個(gè)問(wèn)題，下面介紹一下問(wèn)題及其解決方法。

24

k選取m為可以整除b?a（其中k和a對(duì)模m來(lái)說(shuō)是較小的整數(shù)）的數(shù)。

這是不明智的做法。根據(jù)上述這個(gè)式子，h(k)的值尋常會(huì)依靠于關(guān)鍵詞的某幾位數(shù)。而且相像的關(guān)鍵字經(jīng)過(guò)順序重排也可能會(huì)被發(fā)送到同一個(gè)存儲(chǔ)單元。如

3310?1(mod111)。10?1?999m?111取，由于111整除。所以我們得到

又由于

h(064212848)?064212848?064?212?848?14(mod111)和

?12)h(0648482064?8482?12?064?848212那么如何解決上述這個(gè)問(wèn)題呢？我們只需要令m是接近于存儲(chǔ)單元數(shù)目的一個(gè)素?cái)?shù)即可。如：我們想要存儲(chǔ)2000個(gè)學(xué)生的文件時(shí)，假使我們有5000個(gè)存儲(chǔ)單元，那么m應(yīng)當(dāng)取素?cái)?shù)4969。

(1)發(fā)生沖突，即將兩份不同的文件分派到一致的存儲(chǔ)單元。

為了解決這種沖突，使得每份文件分派到唯一的存儲(chǔ)單元，我們有兩種解決方法。第一種方法：發(fā)生沖突時(shí)，增加額外的存儲(chǔ)單元并且將這個(gè)存儲(chǔ)單元與原來(lái)的存儲(chǔ)單元建立鏈接。我們想要存取發(fā)生了沖突的文件時(shí)，首先會(huì)對(duì)涉及的關(guān)鍵字的散列函數(shù)進(jìn)行計(jì)算，其次探尋與該存儲(chǔ)單元有鏈接的列表。其次種方法是：尋覓下一個(gè)開放的存儲(chǔ)地址。為了達(dá)到這個(gè)目的，我們采取被稱作雙重散列的方法。首先，我們選擇h(k)?k(modm),0?h(j)?m，其中m是素?cái)?shù)，是散列函數(shù)。我們接著選取其次個(gè)散列函數(shù)：

d?，2g(k)?k?1(mom

其中0?g(k)?m?1，所以我們有g(shù)(k)與m互素。選取

hj(k)?h(k)?j?g(k)(modm)且可以為零。由于我們有

為檢測(cè)序列，其中

hj(k)的值在零到m之間，并

g(k)與m互素。當(dāng)j取遍所有整數(shù)0,1,...m?1時(shí)，將選

出所有的存儲(chǔ)單元。當(dāng)m-2也為素?cái)?shù)時(shí)，是最正確狀況。這種最正確狀況使得g(k)的值合理進(jìn)布。綜上，我們希望m與m-2是一對(duì)孿生素?cái)?shù)。

例我們引入一個(gè)例子，利用社會(huì)安全號(hào)碼，給具有以下社會(huì)安全號(hào)碼的學(xué)生文件分派存儲(chǔ)地址：

25

k1?344401659k3?212228844k5?047900151k7?034367980k2?325510778k4?329938157k6?372500191k8?546332190k9?509496993k10?132489973我們選取m?4969，m?2?4967。得到檢測(cè)數(shù)據(jù)

hj(k)?h(k)??jg(k)(mod49，

根據(jù)上式我們得到

0?hj(k)?4969h(k)?k(mod4969)，g(k)?k?1(mod4967),

，

通過(guò)計(jì)算，得到

k1?269，k2?1526和k3?2854。我們首先將這幾個(gè)數(shù)分派為文件的地址。由于

k4?1526(mod4969)，但是前面我們已經(jīng)將1526作為存儲(chǔ)地址，那么我們

公式

hj(k)?h(k)?j?g(k)(modm)得出

h1(k4)?h(k4)?g(k4)?1526?216?1742(mod4969)，其中，j?1，

g(k4)?1?k4?216(mod4967)。這樣我們得出第四個(gè)地址1742。同理，我們可以得出第五，六，七，八個(gè)文件分派的地址，分別為：

3960,4075,2376,578。

我們可以發(fā)現(xiàn)，第九個(gè)地址578的值之前已經(jīng)被占據(jù)，我們采用與第四個(gè)地址一致的方法，得到新的分派給第九個(gè)文件的地址2580。同樣的，我們得到第十個(gè)文件分派的自由地址為1958。其中，我們得到這第十個(gè)地址經(jīng)過(guò)兩次運(yùn)算，第一次運(yùn)算得到的1742之前已經(jīng)是第四個(gè)文件的地址，我們需要繼續(xù)采用公式

hj(k)?h(k)?j?g(k)(mod4969)的地址。

，其中，j的值為2。我們得到所求的第十個(gè)文件

26

表3.2學(xué)生文件的散列函數(shù)

社會(huì)安全號(hào)碼h(k)2691526285415263960407523765785781526h1(k)174225801742h2(k)1958344401659325510778212228844329938157047900151372500191034367980546332190509496993132489973

3.5校驗(yàn)位

檢驗(yàn)字符（數(shù)據(jù)）串的誤差我們同樣可以應(yīng)用同余理論進(jìn)行解決。在這節(jié)中，我們將學(xué)習(xí)比特串的誤差檢測(cè)。那么什么是比特串？比特串是用來(lái)做什么的？我們將不再詳細(xì)介紹，只需要知道比特串是用來(lái)代表計(jì)算機(jī)數(shù)據(jù)的。十進(jìn)制的數(shù)據(jù)串即比特串常用來(lái)識(shí)別護(hù)照、支票、書籍或者其他的各種各樣的目的。下面我們將要介紹一下同余理論時(shí)如何檢測(cè)十進(jìn)制的數(shù)據(jù)串的誤差。

我們?cè)趥鞑セ蛘咛幚肀忍卮畷r(shí)可以產(chǎn)生誤差。簡(jiǎn)單的檢測(cè)方法是在比特串

x1x2...xnxn?1后面加上一個(gè)奇偶校驗(yàn)位。它的定義是：

?...?xn(modxn?1?x1?x22)那么我們可以得出，假使字符串的前n個(gè)位有偶數(shù)個(gè)1，則

xn?1?1xn?1?0，否則的話，

。

x1x2...xnxn?1變化后的字符串滿足下面的同余式：

?xn?xn?1?0(mod2)x1?x2?...我們就是利用上面這個(gè)公式來(lái)檢測(cè)和尋覓誤差。假設(shè)我們發(fā)送了數(shù)據(jù)串

x1x2...xnxn?1y1y2...ynyn?1，接受到的數(shù)據(jù)串是數(shù)據(jù)串。假使

沒(méi)有誤差的話，那么這兩個(gè)數(shù)據(jù)串應(yīng)當(dāng)相等，即

xi?yi,i?1,2,...,n?1。但是如若

存在誤差，那么就改變了一個(gè)或多個(gè)位置，我們檢驗(yàn)是否有

27

y1?y2?..?.yn?yn?1?0(mod2)

假使上述同余式不成立，那么應(yīng)當(dāng)至少一位字符出現(xiàn)錯(cuò)誤。即使同余式成立，仍有可能出現(xiàn)誤差。當(dāng)誤差減少并且是隨機(jī)的，最尋常的誤差是出現(xiàn)單個(gè)誤差，我們可以很簡(jiǎn)單發(fā)現(xiàn)。在最一般的狀況下，我們可以檢測(cè)稀奇數(shù)個(gè)的誤差，卻不能檢查出偶數(shù)個(gè)誤差。

證明：奇偶校驗(yàn)分為奇校驗(yàn)和偶校驗(yàn)兩種，兩者類似，我們以奇校驗(yàn)為例說(shuō)明。奇校驗(yàn)是通過(guò)在末尾添加1或者0的方式使1的個(gè)數(shù)為奇數(shù)。校驗(yàn)時(shí)通過(guò)1的個(gè)數(shù)是否為奇數(shù)判斷是否出錯(cuò)了。

如11001100編碼后為110011001（最終一位添加為1，使1的個(gè)數(shù)是奇數(shù)5）11100110編碼后則為111001100（1的個(gè)數(shù)已經(jīng)是奇數(shù)，添0）

當(dāng)出錯(cuò)個(gè)數(shù)為奇數(shù)時(shí)，將導(dǎo)致1的個(gè)數(shù)的奇偶發(fā)生變化，可以檢測(cè)出錯(cuò)誤，而為偶數(shù)時(shí)，1的個(gè)數(shù)的奇偶不變，故檢測(cè)不出。

例如上例，110011001，當(dāng)有3個(gè)(奇數(shù)個(gè))位出錯(cuò)，假設(shè)是后三位那么就變成110010111這時(shí)1的個(gè)數(shù)就變成了6個(gè)，可以判斷，出錯(cuò)了。而2個(gè)(偶數(shù)個(gè))位出錯(cuò)，假設(shè)是后兩位那么就變成110011111這時(shí)1的個(gè)數(shù)為7個(gè)，依舊是奇數(shù)，就檢測(cè)不出錯(cuò)誤了。

這里所體驗(yàn)的基本原理是：一個(gè)奇數(shù)加上偶數(shù)依舊是奇數(shù)，加上奇數(shù)就變成偶數(shù)。

例假設(shè)收到了1101111和11001000，其中每個(gè)字符串后面的最終一位均是奇偶校驗(yàn)位。對(duì)于第一個(gè)數(shù)據(jù)串，我們有1?1?0?0?1?1?1?1?0(mod2)，所以，我們收到的字符串或者就是所傳送的，或者就是包含了偶數(shù)個(gè)誤差。同樣的，對(duì)于其次個(gè)字符串，我們有1?1?0?0?1?0?0?0?1(mod2)，就可以得出結(jié)論：收到的字符串不是所傳送的，我們可以要求重新發(fā)送。

十進(jìn)制字符串在大量不同的場(chǎng)合被用來(lái)作為認(rèn)證數(shù)。而我們本節(jié)所學(xué)習(xí)的校驗(yàn)位被用來(lái)找出這些字符串中的誤差，我們可以運(yùn)用各種不同的方案來(lái)計(jì)算校驗(yàn)位。如：校驗(yàn)位可以用來(lái)發(fā)現(xiàn)護(hù)照號(hào)碼中的錯(cuò)誤，在一些歐洲的國(guó)家，在他們應(yīng)用的方案中，假使x1x2x3x4x5x6是護(hù)照號(hào)碼，那么校驗(yàn)位x7可以被這樣選擇：

6modx7?7x1?3x2?x3?7x4?3x5?x(10)我們下面舉一個(gè)十進(jìn)制的例子。

例3.8假設(shè)有一個(gè)護(hù)照的號(hào)碼是211894，我們?yōu)榱苏页鲂ｒ?yàn)位

x7，計(jì)算

28

x7?7?2?3?1?1?1?7?8?3?9?1?4?5(mod10)那么得到校驗(yàn)位是5，并且我們會(huì)將七位數(shù)字211894印在護(hù)照上面。

依照上述方法，我們將計(jì)算出的一個(gè)校驗(yàn)位加在護(hù)照上，總是能夠發(fā)現(xiàn)誤差。為了進(jìn)一步證明這一點(diǎn)，我們假設(shè)在某一位上制造一個(gè)誤差a，即

yj?xj?a(mod10)。其中

xj是第j位正確的數(shù)字。但是

x7yj不正確且替換了正確的

a(mod10),當(dāng)

數(shù)字。從校驗(yàn)位的定義我們可以知道，可以變?yōu)?a或者3a或者

兩個(gè)數(shù)字的誤差不是5或者-5，即他們不是xi?xj?5式子中的xi和xj。利用這種方案我們可以檢測(cè)出大量混亂的三位數(shù)字的可能誤差。下面將注意力轉(zhuǎn)移到圖書出版過(guò)程中校驗(yàn)位的使用：

國(guó)際標(biāo)準(zhǔn)書號(hào)（ISBN）幾乎可以識(shí)別所有出版的書。國(guó)際標(biāo)準(zhǔn)書號(hào)是由出版商分派的市委數(shù)字的代碼。校驗(yàn)位在國(guó)際標(biāo)準(zhǔn)書號(hào)中可以用來(lái)發(fā)現(xiàn)當(dāng)國(guó)際標(biāo)準(zhǔn)書號(hào)被復(fù)制時(shí)經(jīng)常出現(xiàn)的誤差，也就是說(shuō)單個(gè)誤差和由于兩個(gè)數(shù)字顛倒位置而造成的誤差。例如：一本書第一版的國(guó)際標(biāo)準(zhǔn)書號(hào)是0-201-06561-4。第一組的數(shù)字是0，代表本書的語(yǔ)種—英語(yǔ)；其次組的數(shù)字是201代表出版公司—艾迪生·維斯理出版公司；第三組的數(shù)字是06561表示出版公司分派給本書的一組數(shù)；最終一組數(shù)4由于分組的型號(hào)是根據(jù)語(yǔ)種和出版商的不同而不同的，所分得的校驗(yàn)位。

校驗(yàn)位是如何被確定的？又是怎樣用來(lái)發(fā)現(xiàn)經(jīng)常出現(xiàn)的誤差的？假設(shè)一本書的國(guó)際標(biāo)準(zhǔn)書號(hào)是

x1x2...x10x10，其中是校驗(yàn)位。前九個(gè)數(shù)字是十

0,1,2,...9?x進(jìn)制數(shù)字，屬于集合?而校驗(yàn)位10是一個(gè)十一進(jìn)制的數(shù)字，屬于集合

?0,1,2,...9,X?，其中X是十一進(jìn)位的數(shù)字，在十進(jìn)制符號(hào)下代表整數(shù)10。我們

選擇校驗(yàn)位滿足同余式

?ixi?110i?0(mod11)

x10很簡(jiǎn)單知道，校驗(yàn)位可以由同余式

x10??ixi(mod11)i?19計(jì)算得到。即校驗(yàn)

位是前九位數(shù)字的加權(quán)和除11的剩余。

例某本書的國(guó)際標(biāo)準(zhǔn)書號(hào)是0-201-06561。找出這本書的第一版的國(guó)際標(biāo)準(zhǔn)書號(hào)的校驗(yàn)位。

x10?1?0?2?2?3?0?4?1?5?0?6?6?7?5?8?6?9?1?4(mod11)

29

所以國(guó)際標(biāo)準(zhǔn)書號(hào)是0-201-06561-4。若一本書的國(guó)家標(biāo)準(zhǔn)書號(hào)是3-540-19102開始的，則根據(jù)同余式

x10?1?3?2?5?3?4?4?0?5?1?6?9?7?1?8?0?9?2?10(mod11)

十進(jìn)制10對(duì)應(yīng)于十一進(jìn)制X,我們可以知道校驗(yàn)位是X。所以國(guó)際標(biāo)準(zhǔn)書號(hào)是3-540-19102-X。

國(guó)際標(biāo)準(zhǔn)書號(hào)還可以檢測(cè)出單個(gè)的錯(cuò)誤或者兩個(gè)數(shù)字是否倒置了。

30

4特別的同余式

本章我們將學(xué)習(xí)三個(gè)比較重要的同余式，無(wú)論是在理論上還是應(yīng)用上。4.1威爾遜定理和費(fèi)馬小定理

威爾遜定理證明白假使p是素?cái)?shù)，那么p除(p?1)!?1的余數(shù)是-1，而費(fèi)馬小定理給出了一個(gè)整數(shù)的p次冪模p的同余式。特別當(dāng)p時(shí)素?cái)?shù)，a是整數(shù)時(shí)，a和a被p除有一致的余數(shù)。

定理4.1（威爾遜定理）若p是素?cái)?shù)，則

(p?1)!??1(modp)。

p該定理是由威爾遜根據(jù)計(jì)算事實(shí)給出了這個(gè)猜想，但并沒(méi)有證明上述結(jié)論，最終由約瑟夫·拉格朗日在1771年證明出，并將定理描述為如上的同余式。在證明之前，我們先引入一個(gè)定理(設(shè)p是素?cái)?shù)，正整數(shù)a是其自身模p的逆，當(dāng)且僅當(dāng)a?1(modp)或者a??1(modp))

證明當(dāng)p?2時(shí)，我們有(p?1)!?1??1(mod2)，因此，當(dāng)p?2時(shí)定理是成立的。現(xiàn)在我們?cè)O(shè)p是大于2的素?cái)?shù)，根據(jù)定理2.13對(duì)于任何滿足1?a?p?1的整數(shù)a都存在逆a，使得1?a?p?1，aa?1(modp)。根據(jù)上述引入的定理，我們有在小于p的正整數(shù)中，逆等于其自身的只有1和p-1。所以，我們可以將2到p-2分成(p?3)/2組整數(shù)對(duì)。并且，每一組的乘積模p余1。所以我們有

(2?3???p?3)p?(?2)?1(mpo接著我們用1和p?1同時(shí)乘以上式得到

!1?2?3??p?(?3p)?(?p2?)(?1?p)?1(?(p?1)?1?)?p上述定理得證。我們還可以證明威爾遜定理的逆也是正確的，我們?cè)谶@里不再證明。

定理4.2（費(fèi)馬小定理）設(shè)p是一個(gè)素?cái)?shù)，a是一個(gè)正整數(shù)并且p|a，則

ap?1?1(modp)。

證明在這里我們考慮p-1個(gè)整數(shù)：a,2a,...,(p?1)a，它們的共同點(diǎn)是都不

31

能被p整除，并且在a,2a,...,(p?1)a中任何倆個(gè)整數(shù)模p不同余。由于整數(shù)

a,2a,...,(p?1)a是p-1個(gè)均不整除p的數(shù)，并且是兩兩都互不同余的整數(shù)組成的

集合中的元素，那么這些數(shù)模P的最小正剩余一定可以是1,2,...,(p?1)。再根據(jù)同余性，整數(shù)a,2a,...,(p?1)a的乘積模p要同余于前p-1個(gè)正整數(shù)的乘積，也就是

,?(a,2a,...pa?1)1,2p?,...,(p1所以

p?1a(p?1)?!p(?1)!(mpod)又由于(p?1)!與p互素，我們消去(p?1)!，得到

p?1a?1(mopd)

定理得證。

pa定理4.3設(shè)p是素?cái)?shù)