辗转相除法
背景最大公约数欧几里得的辗转相除法计算的是两个自然数a和b的最大公约数g,意思是能够同时整除a和b的自然数中最大的一个。两个数的最大公约数通常写成GCD(a,b),或者简写成(a,b),但是第二种写法也被使用在其他数学概念,如二维向量的坐标。如果GCD(a,b)=1,则称a和b互素。a和b是否互素和它们是否素数无关。如,6和35都不是素数,因为它们都可以分解为多于一个素因数的乘积:6=2×3,35=5×7。但是,6和35互素,因为除了1以外没有自然数同时整除6和35。一个24×60的长方形正好被十个12×12的方格填满,其中12是24和60的最大公约数。一般地,当且仅当c是a和b的公约数时,a×b尺寸的长方形可被边长c的正方形正好填满。令g=GCD(a,b)。由于a和b都是g的整数倍,所以可以写成a=mg、b=ng,并且不存在更大的整数G>g使等式成立。为了使g尽可能大,就要使a和b中所有......