今天買(mǎi)了本《算法概論》影印注釋版，仔細(xì)看了第一章，果然名不虛傳，很是吸引人。
第一章的習(xí)題難度適中，這里抽出第35題來(lái)，這題是證明Wilson定理。
Wilson定理：
N是一個(gè)素?cái)?shù)當(dāng)且僅當(dāng): (N-1)! ≡ -1(mod N)
證明：
首先我們證明若N是素?cái)?shù)，那么等式成立，對(duì)于N=2,這是很明顯的。以下證明N>2 的情形。
1）若N是素?cái)?shù)，那么關(guān)于N同余的乘法群G={1,2,3....N-1}
群G每個(gè)元素都有逆元，映射 f:a -> a^-1 ，f(a)=a^-1 是一個(gè)一一映射?，F(xiàn)在，任取一個(gè)元素，它的逆元要么是其它一個(gè)元素，或者是它本身。 我們假設(shè)其中元素x的逆元是它本身，那么x*x ≡1(mod N) =>(x+1)*(x-1)=K*N,而N是素?cái)?shù)，所以要么x=N-1,要么x=1。也就是說(shuō)，除了這兩個(gè)元素，其它的元素的逆元都是映射到別的元素的。而N>2,是奇數(shù)，所以元素共有N-1個(gè)，也就是偶數(shù)個(gè)元素。這樣，除了1和N-1外剩余的N-3個(gè)元素剛好結(jié)成兩兩一對(duì)(x,y)(逆元是唯一的）使得f(x)=y=x^-1,也就是xy≡1(mod N).
現(xiàn)在把G的元素全部乘起來(lái)，讓互為逆元的元素組成一對(duì)那么(N-1)!=1*(N-1)*(x1*y1)*(x2*y2)...(xk*yk)≡1*(N-1)*1*1...1 (mod N)≡-1(mod N).
這樣，我們證明了一個(gè)方向了，下面我們證明另一個(gè)方向
2）若(N-1)! ≡ -1(mod N)成立，則N是素?cái)?shù)，若不然，令 N是和數(shù)。則(N-1)!肯定整除N,因?yàn)镹的每個(gè)因子p滿(mǎn)足p>1,p<N。
現(xiàn)在令(N-1)!=K1*N.又(N-1)! ≡ -1(mod N) => K1*N ≡ -1(mod N),由同余性質(zhì)知，存在K2使得K1*N+1=K2*N,兩邊同時(shí)除以N得K1+1/N=K2.顯然，這是不可能的，所以若(N-1)! ≡ -1(mod N)成立，則N是素?cái)?shù)
證明完畢！
這里用群的概念能夠簡(jiǎn)化一定的描述，其實(shí)可以完全不用群的概念的，只不過(guò)這樣一來(lái)，描述更長(zhǎng)點(diǎn)，繁瑣點(diǎn)！