E81086713E446D36F62B2AA2A3502B5EB155

Java杂家

杂七杂八。。。一家之言

BlogJava 首页 新随笔 联系 聚合 管理
  141 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks
   今天买了本《算法概论》影印注释版,仔细看了第一章,果然名不虚传,很是吸引人。
第一章的习题难度适中,这里抽出第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是素数

证明完毕!

这里用群的概念能够简化一定的描述,其实可以完全不用群的概念的,只不过这样一来,描述更长点,繁琐点!





posted on 2009-04-10 22:38 DoubleH 阅读(1999) 评论(1)  编辑  收藏 所属分类: Memorandum

Feedback

# re: 《算法概论》第一章习题35证明(Wilson定理) 2009-08-29 13:29 wakeeper
很经典!  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: