欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。也叫辗转相除法。这是数论和代数学中的重要方法。从整数的除法可知:对任给二整数a,b0,必有二整数q及r存在,使得a=qb+r,0≤rb,并且q及r是唯一存在的,这是数论的一条基本定理,整数的一系列重要性质都可以由此得到,如果反复利用这一基本定理,就可以得到因为每进行一次除法,余数就至少减一,而b是有限的正整数,所以最多进行b次,总可以得到一个余数是零的等式,即rn+1=0。上面的方法叫做欧几里德算法。