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