第一部分

第四章數(shù)論與有限域基礎(chǔ)張權(quán)2012年秋季本章提綱數(shù)論基礎(chǔ)群、環(huán)、域有限域基礎(chǔ)數(shù)論基礎(chǔ)素?cái)?shù)與互素對(duì)整數(shù)b!=0及a，如果存在整數(shù)m

使得a=mb，稱b

整除

a，也稱b

是a

的因子，記作b|a

例1,2,3,4,6,8,12,24整除24整除具有以下性質(zhì)：如果a|1，那么a=±1如果a|b

且b|a，則a=±b對(duì)任一b(b≠0)，b|0如果b|g，b|h，則對(duì)任意整數(shù)m、n

有b|(mg+nh)數(shù)論基礎(chǔ)素?cái)?shù)與互素稱整數(shù)

p(p>1)

是素?cái)?shù)，如果

p

的因子

只有±1，±p任一整數(shù)

a(a>1)

都能惟一地表示為以下形式：

其中

p1

>

p2

>

…>pt

是素?cái)?shù)，αi

>0(i=1,…,t)。

例如：91=7×13，11011=7×112×13數(shù)論基礎(chǔ)素?cái)?shù)與互素該性質(zhì)稱為整數(shù)分解的惟一性，也可如下陳述：設(shè)P是所有素?cái)?shù)集合，則任意整數(shù)a

(a>1)都能惟一地寫成以下形式：

其中ap≥0，等號(hào)右邊的乘積項(xiàng)取所有的素?cái)?shù)，然而大多指數(shù)項(xiàng)ap為0。相應(yīng)地，任一正整數(shù)可由非0指數(shù)列表表示。

例如：11011可表示為{a7=1,a11=2,a13=1}。數(shù)論基礎(chǔ)素?cái)?shù)與互素稱c

是兩個(gè)整數(shù)a、b

的最大公因子，當(dāng)且僅當(dāng)：

①c

是a

的因子也是b

的因子，

即c

是a、b

的公因子

②a

和b

的任一公因子，也是c

的因子表示為c=gcd(a,b)數(shù)論基礎(chǔ)素?cái)?shù)與互素由于最大公因子為正，所以

gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)一般地gcd(a,b)=gcd(|a|,|b|)由任一非0整數(shù)能整除0，可得gcd(a,0)=|a|如果將a，b都表示為素?cái)?shù)的乘積，則gcd(a,b)極易確定。例如：300=22×31×52；18=21×32，所以gcd(18,300)=21×31×50=6一般地，由c=gcd(a,b)可得：對(duì)每一素?cái)?shù)p，

cp

=min(ap,bp)數(shù)論基礎(chǔ)素?cái)?shù)與互素如果gcd(a,b)=1，則稱a和b互素整數(shù)a,b

互素是指除1之外它們沒有其它公因子，例如：8與15互素8的因子：1,2,4,815的因子：1,3,5,151是8與15唯一的公因子數(shù)論基礎(chǔ)模運(yùn)算設(shè)n

是一正整數(shù)，a是整數(shù)，如果用n

除a，得商為q，余數(shù)為r，則

其中為小于或等于x的最大整數(shù)。用amodn表示余數(shù)r，則如果(amodn)=(bmodn)，則稱a

和b

(模n)同余，

記為a≡bmodn。與a

模n

同余的數(shù)的全體稱為a

的同余類，記為[a]，稱a

為這個(gè)同余類的表示元素。注意：如果a≡0(modn)，則n|a。數(shù)論基礎(chǔ)模運(yùn)算同余有以下性質(zhì)：①若

n|(a-b)，則

a≡bmodn②a≡bmodn，則

b≡amodn③a≡bmodn

且b≡cmodn，則

a≡cmodn從以上性質(zhì)易知，同余類中的每一元素都可作為這個(gè)同余類的表示元素。數(shù)論基礎(chǔ)模運(yùn)算求余數(shù)的操作a

modn

將整數(shù)

a

映射到集合

{0,

1,…,

n-1}，在這個(gè)集合上的算術(shù)運(yùn)算稱為

模運(yùn)算，模運(yùn)算有以下性質(zhì)：①[(amodn)+(bmodn)]modn

=

(a+b)modn②[(amodn)-(bmodn)]modn

=

(a-b)modn③[(amodn)×(bmodn)]modn

=

(a×b)modn數(shù)論基礎(chǔ)模運(yùn)算性質(zhì)①的證明：設(shè)

(amodn)=

ra，(bmodn)

=

rb，則存在整數(shù)

j、k

使得

a

=

jn+ra，b

=

kn+rb，因此：(a+b)modn

=

[(j+k)n+ra+rb]modn

=

(ra+rb)modn

=[(amodn)+(bmodn)]modn（證畢）性質(zhì)②、③的證明類似。數(shù)論基礎(chǔ)模運(yùn)算例：設(shè)

Z8

=

{0,

1,

…,

7}，考慮

Z8

上的模加法和模乘法，結(jié)果如下表所示：+801234567001234567112345670223456701334567012445670123556701234667012345770123456×801234567000000000101234567202460246303614725404040404505274163606420642707654321數(shù)論基礎(chǔ)模運(yùn)算例：設(shè)

Z8

=

{0,

1,

…,7}，考慮

Z8

上的模加法和模乘法，結(jié)果如下表所示：從加法結(jié)果可見，對(duì)每一

x，都有一

y，使得x+y≡0mod8。稱y為x的負(fù)數(shù)，也稱為加法逆元。對(duì)

x，若有

y，使得

x×y≡1mod8，如

3×3≡1mod8，則稱

y

為

x

的倒數(shù)，也稱為

乘法逆元。在本例中并非每一

x

都有乘法逆元。數(shù)論基礎(chǔ)模運(yùn)算一般地，定義

Zn

為小于

n

的所有非負(fù)整數(shù)集合，即

Zn

=

{0,

1,…,

n-1}，稱

Zn

為模

n

的同余類。其上的模運(yùn)算有以下性質(zhì)：①交換律：(w+x)modn

=

(x+w)modn

(w×x)modn

=

(x×w)modn②結(jié)合律：[(w+x)+y]modn

=

[w+(x+y)]modn

[(w×x)×y]modn

=

[w×(x×y)]modn數(shù)論基礎(chǔ)模運(yùn)算一般地，定義

Zn

為小于

n

的所有非負(fù)整數(shù)集合，即

Zn

=

{0,

1,…,

n-1}，稱

Zn

為模

n

的同余類。其上的模運(yùn)算有以下性質(zhì)：③分配律：[w×(x+y)]modn

=

[w×x+w×y]modn④單位元：(0+w)modn

=

wmodn

(1×w)modn

=

wmodn⑤加法逆元：對(duì)

w∈Zn，存在

z∈Zn，使得

w+z≡0modn，記

z

=

-w。數(shù)論基礎(chǔ)模運(yùn)算一般地，定義

Zn

為小于

n

的所有非負(fù)整數(shù)集合，即

Zn

=

{0,

1,…,

n-1}，稱

Zn

為模

n

的同余類。此外還有以下性質(zhì)：加法可約律：如果

(a+b)≡(a+c)modn，

則

b≡cmodn該性質(zhì)可由

(a+b)≡(a+c)modn

的兩邊同加上

a

的加法逆元得到。類似性質(zhì)對(duì)乘法卻不一定成立。仔細(xì)觀察可見，與

8

互素的幾個(gè)數(shù)

1，3，5，7

都有乘法逆元。這幾個(gè)數(shù)有什么特點(diǎn)呢？這一結(jié)論可推廣到任一

Zn。數(shù)論基礎(chǔ)模運(yùn)算定理：設(shè)

a∈Zn，gcd(a,n)

=

1，則

a

在

Zn

中有乘法逆元。證明：首先，集合a

×

Zn={0,a,2a,…,(n-1)a}(modn)

與集合Zn

等價(jià)：

<n;

ia

modn

≠jamodn,iffi≠j,

i,j

∈Zn然后，存在x

∈Zn，滿足ax

≡1modn數(shù)論基礎(chǔ)模運(yùn)算(小結(jié))加法：

a+bmodn=(amodn)+(bmodn)modn

減法：

a-bmodn=a+(-b)modn乘法，重復(fù)加法：

a×bmodn=(amodn)×(bmodn)modn

除法：（乘法約簡(jiǎn)律）

a/bmodn

=a×b-1modn注意：b-1是

bmodn的乘法逆元，存在的條件是

gcd(b,n)

=1數(shù)論基礎(chǔ)歐幾里得(Euclid)算法數(shù)論中的一個(gè)基本技術(shù)：求兩個(gè)正整數(shù)的最大公因子的簡(jiǎn)化方法。擴(kuò)展Euclid算法不僅可以求出兩個(gè)正整數(shù)的最大公因子，而且當(dāng)兩個(gè)正整數(shù)互素時(shí)，還可求出其中一個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元。數(shù)論基礎(chǔ)歐幾里得(Euclid)算法求最大公因子Euclid算法基于以下基本結(jié)論：

對(duì)任意非負(fù)整數(shù)a

和正整數(shù)b，有

gcd(a,b)=gcd(b,amodb)課堂練習(xí)題：證明上述命題。數(shù)論基礎(chǔ)歐幾里得(Euclid)算法求最大公因子Euclid(f,d)：

設(shè)算法的輸入是兩個(gè)非負(fù)整數(shù)f,d，并且

f>dEuclid(f,d){

X←f;Y←d；#: ifY=0thenreturnX=gcd(f,d)；

R=XmodY；

X=Y；

Y=R；

goto#;}歐幾里得(Euclid)算法求最大公因子例子，gcd(1970,1066)1970=1x1066+904 gcd(1066,904)

1066=1x904+162 gcd(904,162)

904=5x162+94 gcd(162,94)

162=1x94+68 gcd(94,68)

94=1x68+26 gcd(68,26)

68=2x26+16 gcd(26,16)

26=1x16+10 gcd(16,10)

16=1x10+6 gcd(10,6)

10=1x6+4 gcd(6,4)

6=1x4+2 gcd(4,2)

4=2x2+0 gcd(2,0)數(shù)論基礎(chǔ)歐幾里得(Euclid)算法求乘法逆元如果gcd(a,b)=1，則b

在moda下有乘法逆元（不妨設(shè)b<a），即存在x(x<a)，使得bx≡1moda。擴(kuò)展Euclid算法可求出gcd(a,b)，當(dāng)gcd(a,b)=1，還得到b

的逆元。數(shù)論基礎(chǔ)ExEuclid(f,d){//設(shè)f>d

(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);#:ifY3=0thenreturnX3=gcd(f,d)；noinverse;ifY3=1thenreturnY3=gcd(f,d)；Y2=d-1modf;Q=X3/Y3

；

(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);goto#;}fX1