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