辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至3000年前。
例如：
展开编辑本段简介 辗转相除法的演示动画
在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 ? 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (?2） × 252。这个重要的等式叫做贝祖等式。
辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。自此，现代抽象代数概念如欧几里得整环开始出现。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。
辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，寻找满足中国剩余定理的数，或者求有限域的倒数。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。加百利·拉梅(Gabriel Lamé)于1844年证明了这点，开创了计算复杂性理论。编辑本段证明简单的想法
设两数为a、b(a>b），求a和b最大公约数(a，b）的步骤如下：用b除a，得a=bq......r1(0≤r1）。若r1=0，则（a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2）.若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零除数即为（a，b）。
原理及其详细证明
设两数为a、b(b
数，r=a mod b 为a除以b以后的余数，k为a除以b的商，即a/b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r）。 第一步：令c=gcd(a,b），则设a=mc，b=nc 第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c 第三步：根据第二步结果可知c也是r的因数 第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】 从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。 证毕。编辑本段计算机算法自然语言描述
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： 1. 若 r 是 a ÷ b 的余数，则 gcd(a,b) = gcd(b,r) 2. a 和其倍数之最大公因子为 a。 另一种写法是： 1. a ÷ b，令r为所得余数（0≤r
伪代码
这个算法可以用递归写成如下： function gcd(a,b) { if b<>0 return gcd(b,a mod b); else return a； }
C语言实现
/*题目：输入两个正整数，求其最大公约数。*/
#include
{ unsigned m,n;
printf("请输入两个正整数：");
scanf("%u%u",&m,&n);
printf("%u与%u的最大公约数为：%u\n",m,n,gcd ( m,n ) ); return 0; } /* 功能：返回正整数m和n的最大公约数*/
unsigned gcd ( unsigned m,unsigned n )
{ unsigned temp;
if (m
}
Basic实现
INPUT m,n DO r=mMODn m=n n=r LOOP UNTILr=0 PRINT m END
Pascal实现
function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; Common Lisp实现 (defun my-gcd (number-a number-b) (do ((r (mod number-a number-b) (mod ea eb))(eb number-b r) (ea number-a eb)) ((= 0 r) eb)))
数据举例
其中“a mod b”是指取 a ÷ b 的余数。 例如，123456 和 7890 的最大公因子是 6，这可由下列步骤看出： a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0
时间复杂度
辗转相除法的运算速度为 O(n2），其中 n 为输入数值的位数。编辑本段辗转相除法求不定方程的特解 辗转相除法可以求出不定方程的一组
整数解。 设不定方程为a x+b y=c，其中a,b,c为整数且lcm(a,b)|c b=q（1） a+r（2） a=q（2） r（2）+r（3） a,b辗转相除的算式为 r（2）=q（3） r（3）+r（4） ... r(n-2）=q(n-1）r(n-1）+r(n) r(n-1）=q(n)r(n) 其中r(n）为lcm(a,b），不妨令b=r(0），a=r（1），r(n+1）=0 第i个算式为 r(i-1）=q(i)r(i)+r(i+1） 所以r(i+1）=r(i-1）-q(i)(ri) (*) 用公式（*）可以得到r(n)=lcm(a,b）关于a,b的线性组合sa+tb=lcm(a,b) 所以不定方程a x+b y=c的一组特解为 x=sc/lcm(a,b) y=tc/lcm(a,b)编辑本段例如： 不定方程为326x+78y=4 求（326,78）的算式为： 326=4*78+14 14=326-4*78 78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 所以 2 =8-6=8-（14-8） =2*8-14=2*（78-5*14）-14 =2*78-11*14=2*78-11*（326-4*78） =46*78-11*326 即2=(-11）*326+46*78 所以4=(-22）*326+92*78 所以x=-22,y=92是不定方程326x+78y=4的一组特解 注：q(i），r(i），括号中的是下标，lcm是求最小公倍数
辗转相除法最大的用途就是用来求两个数的最大公约数。
用（a,b）来表示a和b的最大公约数。 有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。 （证明过程请参考其它资料）
例：求 15750 与27216的最大公约数。
解： ∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466） ∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284) ∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898） ∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386） ∵2898=1386×2+126 ∴（2898，1386）=（1386，126） ∵1386=126×11 ∴（1386，126）=126 所以（15750，27216）=216 辗转相除法比较适合用来求两个比较大的数的最大公约数 。