第2章同余《信息安全數學基礎（第2版）》1同余主要內容本章將主要介紹數論中的同余理論，包括同余、同余關系、剩余類、完全剩余系和縮剩余系等基本概念和性質。另外，本章還將討論歐拉定理、費馬小定理、利用擴展歐幾里得算法進行快速模逆運算和威爾遜定理等。學習要求掌握同余的概念與性質，以及相關的計算方法；掌握剩余類和剩余系的概念與性質，以及相關的計算方法；掌握歐拉定理和費馬小定理及其相關的應用；掌握擴展歐幾里德算法和威爾遜定理及其相關的應用。2CONTENTS目錄同余同余的概念和性質1剩余類和剩余系2歐拉定理和費馬小定理3擴展歐幾里得算法和威爾遜定理

43同余的概念和性質第1節(jié)同余的概念和性質4同余的概念和性質5主要內容本節(jié)主要介紹同余的概念和性質。首先介紹了同余和同余式的定義，并介紹了同余的性質和一組同余式之間的關系。隨后介紹了同余與整除、倍數和最大公因子等相關的運算定理。涉及內容總結如下：同余和同余式的定義；同余的性質，包括自反性、對稱性和傳遞性；同余運算的相關定理。

同余的概念和性質6

同余的概念和性質7

同余的概念和性質8

同余的概念和性質9剩余類和剩余系第2節(jié)剩余類和剩余系10剩余類和剩余系11主要內容本節(jié)首先介紹剩余類和定義和相關定理。首先介紹了剩余類的定義和性質，隨后介紹了可由剩余類組成的完全剩余系，并總結了其性質和相關定理。涉及內容可總結如下：剩余類及其代表元；完全剩余系及其相關定理。

剩余類和剩余系12

剩余類和剩余系13

定理2.2.3

設k是滿足(k,m)=1的整數,b是任意整數,若a0,a1,…,am-1是模m的一個完全剩余系,則ka0+b,ka1

+b,…,kam-1+b也是模m的一個完全剩余系.即若x遍歷模m的一個完全剩余系,則kx+b也遍歷模m的一個完全剩余系.

定理2.2.4

若xi(i=0,1,…,m1-1)是模m1的完全剩余系,yj(j=0,1,…,m2-1)是模m2的完全剩余系,其中(m1,m2)=1,則m2xi+m1yj

(i=0,1,…,m1-1,j=0,1,…,m2-1)是模m1m2的完全剩余系.

剩余類和剩余系14歐拉定理和費馬小定理第3節(jié)歐拉定理和費馬小定理15歐拉定理和費馬小定理16主要內容本節(jié)首先介紹歐拉函數和縮系的定義，隨后介紹了相關定理，用于確認剩余類的縮系。接下來引出歐拉定理和費馬小定理，并介紹了與二者相關的運算定理。內容可總結如下：歐拉函數；縮系；歐拉定理；費馬小定理；與歐拉定理二者和費馬小定理相關的運算定理。

歐拉定理和費馬小定理17

歐拉定理和費馬小定理18

歐拉定理和費馬小定理19

歐拉定理和費馬小定理20擴展歐幾里得算法和威爾遜定理第4節(jié)擴展歐幾里得算法和威爾遜定理2122主要內容本節(jié)首先介紹整數在模空間下逆元的概念，隨后介紹求乘法逆元的擴展歐幾里得算法。最后則討論乘法逆元的一種特殊情況，并由此引出威爾遜定理。涉及內容總結如下：逆元；擴展歐幾里得算法；乘法逆元的相關定理；威爾遜定理。擴展歐幾里得算法和威爾遜定理

23擴展歐幾里得算法和威爾遜定理

定理2.4.2設r0,r1是兩個正整數,且r0>r1,設ri(i=2,…,n)是使用歐幾里德算法計算(r0,r1)時所得到的余數序列且rn+1=0,則可以使用如下算法求整數sn和tn,使得(r0,r1)=snr0+tnr1.這里sn和tn是如下遞歸定義的序列的第n項.且s0=1,t0=0;s1=0,t1=1;si=si?2

?qi?1si?1,ti=ti?2

?qi?1ti?1,其中qi=ri?1/ri,i=2,3,…,n.定理2.4.2中給出的求乘法逆元的算法稱為擴展歐幾里德算法.證明：（思路）歸納法證明ri=sir0+tir1,i=0,1,…,n.24擴展歐幾里得算法和威爾遜定理

25擴展歐幾里得算法和威爾遜定理小結本章小結