同余及其應(yīng)用

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

同余及其應(yīng)用

CONGRUENCEANDITS

APPLICATIONS

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

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

摘要

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

1前言

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

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

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

1

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

2

2同余

2.1同余引言

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

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

定義給定一個正整數(shù)m把它叫做模，假使用m去除整數(shù)a和b，所得余數(shù)一致，我們就說a與b對模m同余，記作a?b(modm)。假使余數(shù)不一致，那么我們就說a與b對模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)。這說明存在整數(shù)k，使得

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

?b反過來，若存在整數(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）對稱性.假使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時，a?b(modd)。

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

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

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

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

(modmax?b)（2-1）

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

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

x1?x0(modm)，

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

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

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

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

5

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

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

[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，則無解。而當(dāng)d整除b時，有無窮多解：

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

ax-my?b，

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

解，有無窮多這樣的解。

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

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

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

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

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

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

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

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

6

方程變元數(shù)多于一，且方程數(shù)多于一，但是方程的模一致。

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

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

x?a1(modm1)

x?a2(modm2)..有模

M?m1m2...mrx?ar(momdr

)的唯一解。

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

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

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

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

y1,我們需要解同余方程

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

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可以驗證，滿足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ù)的計算機(jī)算術(shù)運算的方法。存儲很大的整數(shù)并做它們之間的算術(shù)運算需要特別的技巧。中國剩余定理告訴我們給定兩個互素的模m1,m2,...,mr，一個小于M?m1m2...mr的正整數(shù)n由它的模mj最小正剩余唯一確定，其中

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

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

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

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

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

y?yi(modmi)則

。然后利用中國剩余定理將所得的四個最小正剩余的和的

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

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

就可以利用中國剩余定理求出模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ù);簡單驗證x是奇數(shù)的情形不是解）。模5的解釋整數(shù)x?1(mod5)，我們利用中國剩余定理求

8

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

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

我們知道，一旦知道了多項式模p同余方程的所有解，就有相對簡單的方法

kp來解多項式的模同余方程。

我們會知道，模P的解可以用來求模p的解，模p的解可以用來求模p的解，

2p等等。我們先舉例說明從模P的解可以用來求模的解的基本思路。

223例通過對x?0,1,2,3和4直接驗證，可見

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

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

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

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

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

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

例線性同余方程組

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

9

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

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

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

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

7y?17(mod13

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

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

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

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

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

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

我們給出一個關(guān)于含有兩個二元方程的同余方程組的一般結(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的一個逆。

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

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

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

矩陣同余A?B(modm)提供了表達(dá)nk個同余式aij?bij(modm)的一種簡單方法。定理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個方程的同余方程組等價于矩陣同余方程

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的一個?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互為素數(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)這等價于矩陣同余方程

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

6??626??105?1????3??是??242??模7的一個逆。因此，我們有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此圖說明白數(shù)列x的周期特性。其中的值為2，與模97同余，i

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

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

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

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

x,x,...,xs大，而與n相比較小，數(shù)字12是隨機(jī)地選取時，這是可能發(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ù)多項式，緊接著我們用遞歸定義

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

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

14

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

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

,3?67x74,?x1?5,x2?26x值得注意的是，由xk的遞歸定義，假使其中d是一個正整數(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的一個因子，我們要求

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

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

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

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

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

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

經(jīng)過試驗得出，假使想要分解具有相當(dāng)大的素因子的整數(shù)，波拉德?方法是實用的。在實際應(yīng)用中，我們假使想要分解大的整數(shù)時，首先用小素數(shù)試除，例如小于104的素數(shù)；其次，我們用波拉德?方法來找出中等大小的（例如不超過1015）的素因子。一般的，我們在采用此方法失敗之后，我們才采用真正強(qiáng)力的方法，譬如二次篩法或者橢圓曲線方法，在此不予介紹。

15

3同余的應(yīng)用

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

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

被2的冪整除性檢驗我們已經(jīng)知道可以被2整除那么它的最終一位一定是整數(shù)，那么要推導(dǎo)出被2的冪整除的整數(shù)要怎么做呢？例如：令n=32688048，n能否被22整除？能否被23整除？能否被24整除？能夠被n整除的2的最高次冪是多少呢？我們將要推導(dǎo)出一種檢驗的方法來回復(fù)這些問題，而不是用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ìn)j由于，由此可得到對所有的正整數(shù)有：

而

16

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

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

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)根據(jù)上面的同余式，我們得出結(jié)論：我們只需要檢驗各位數(shù)字之和能否被3或者9整除，便可以飯別判斷n是否能被3或者9整除。

例3.3令n=4127835

17

我們可以得出n的各位數(shù)字之和是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的各位數(shù)字交替相

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

例3.4令n=723160823

易知n可以被11整除，由于交替相加減之后，我們得到22，可以被11整除。被7,11,13整除的檢驗我們將要推導(dǎo)一個可以判斷同時被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)

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

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

基于b進(jìn)制表示的整除性檢驗(b是一個正整數(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)制符號表示的被2的方冪和5的方冪整除的整除性檢驗推廣到了其他進(jìn)制整數(shù)的整除性檢驗。

18

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

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

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

可以被d整除。

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

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

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

此定理將十進(jìn)制符號表示的對整數(shù)是否被11整除的整除性檢驗推廣到了其他進(jì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萬年歷

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

19

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

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

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

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

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

N?100C?Y,

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

d1600求得

dN，第一步我們應(yīng)當(dāng)計算出第N年與1600年之間有幾個閏年（在這里不包括1600年而包括N年）。我們?nèi)￠c年數(shù)為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/?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ù)上述得出的式子，我們計算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)

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

dN我們還需要計算出

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

入求值的方法，根據(jù)事實，對于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號是星期三。接著將1600代入到計算N的式

子中，得到

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

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

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

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

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

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](我們可以利用這個公式來計算任何一年的任何一天的星期數(shù)。

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

其中，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號

其中，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é)中，我們將探討如何利用同余來安排N個隊的循環(huán)賽的賽程，使得每個隊與其他任何一個隊都比賽一次，這個方法是由弗輪德發(fā)明的。

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

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

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

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

22

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

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

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

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

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

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

23

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

輪123456717bye234562671bye345356712bye4隊4bye567123534bye671262345bye717123456bye

3.4散列函數(shù)

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

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

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

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

我們有時也會遇到以下幾個問題，下面介紹一下問題及其解決方法。

24

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

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

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

又由于

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

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

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

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

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

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

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

為檢測序列，其中

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

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

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

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

25

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

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

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

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

，

通過計算，得到

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

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

公式

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)。這樣我們得出第四個地址1742。同理，我們可以得出第五，六，七，八個文件分派的地址，分別為：

3960,4075,2376,578。

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

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

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

26

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

社會安全號碼h(k)2691526285415263960407523765785781526h1(k)174225801742h2(k)1958344401659325510778212228844329938157047900151372500191034367980546332190509496993132489973

3.5校驗位

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

我們在傳播或者處理比特串時可以產(chǎn)生誤差。簡單的檢測方法是在比特串

x1x2...xnxn?1后面加上一個奇偶校驗位。它的定義是：

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

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

。

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

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

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

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

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

存在誤差，那么就改變了一個或多個位置，我們檢驗是否有

27

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

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

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

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

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

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

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

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

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

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

例3.8假設(shè)有一個護(hù)照的號碼是211894，我們?yōu)榱苏页鲂ｒ炍?/p>

x7，計算

28

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

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

yj?xj?a(mod10)。其中

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

x7yj不正確且替換了正確的

a(mod10),當(dāng)

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

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

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

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

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

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

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

選擇校驗位滿足同余式

?ixi?110i?0(mod11)

x10很簡單知道，校驗位可以由同余式

x10??ixi(mod11)i?19計算得到。即校驗

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

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

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

29

所以國際標(biāo)準(zhǔn)書號是0-201-06561-4。若一本書的國家標(biāo)準(zhǔn)書號是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對應(yīng)于十一進(jìn)制X,我們可以知道校驗位是X。所以國際標(biāo)準(zhǔn)書號是3-540-19102-X。

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

30

4特別的同余式

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

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

定理4.1（威爾遜定理）若p是素數(shù)，則

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

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

證明當(dāng)p?2時，我們有(p?1)!?1??1(mod2)，因此，當(dāng)p?2時定理是成立的?，F(xiàn)在我們設(shè)p是大于2的素數(shù)，根據(jù)定理2.13對于任何滿足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ù)對。并且，每一組的乘積模p余1。所以我們有

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

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

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

ap?1?1(modp)。

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

31

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

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

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