HelloWorld 善战者,求之于势,不责于人;故能择人而任势。

知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。物有本末，事有终始。知所先后，则近道矣。
  BlogJava :: 首页 ::  :: 联系 ::  :: 管理 ::
  167 随笔 :: 1 文章 :: 40 评论 :: 0 Trackbacks
最大公约数(Euclid算法)

gcd(a,b) = gcd(b, a mod b)

求a,b的最大公约数d
有 a = bk + r
      a = x*d
      b = y*d
      ->
      r = a - bk (即a mod b)
      r = xd - ydk
      r = (x-yk)d
      即d也可以被a mod b整除,d是a mod b的公约数
      因为d是b的公约数
所以 gcd(b,a mod b)成立



</script>

posted on 2007-12-28 12:48 helloworld2008 阅读(281) 评论(0)  编辑  收藏 所属分类: 数学定理

只有注册用户登录后才能发表评论。
网站导航: