最大公约数_欧几里得算法_辗转相除法

//
更相减损术

gcd( a,b )=gcd( |a-b|,min( a,b ) )

eg.
98-63=35
63-35=28
35-28=7
28-7 =21
21-7 =14
14-7 =7 ( 98 63 的最大公约数 )

更相减损术的快速版本 就是辗转相除法

gcd( a,b )=gcd( b,a%b )

// gcd( a,b )=gcd( b,a%b ); // r=a%b r!=0 则 gcd( a,b ) = gcd( b,r )

// 最大公约数（Greatest Common Divisor）缩写 GCD
01 a>b
02 r=a%b
03 r!=0
证:gcd(a,b)=gcd( b,a%b ).

法 01
a=kb+r ,均 >0 . (1)
设 c 为 a,b 众多公约数的一员,即 a%c==0 && b%c==0. (2

最大公约数_欧几里得算法_辗转相除法最先出现在Python成神之路。