关于欧几里得算法求最大公约数算法,
代码如下:
int gcd( int a , int b ) { if( b == 0 ) return a ; else gcd( b , a % b ) ; }
证明:
对于a,b,有a = kb + r (a , k , b , r 均为整数),其中r = a mod b .
令d为a和b的一个公约数,则d|a,d|b(即a、b都被d整除),
那么 r =a - kb ,两边同时除以d
得 r/d = a/d - kb/d = m (m为整数,因为r也被d整除)
所以可知
a,b 的公约数和 b , a mod b 公约数一样,所以他们最大公约数也一样。
即就是 gcd ( a , b ) = gcd ( b , r )
当r=0时,b显然是(b,r)的最大公约数,也即就是a,b的最大公约数,