辗转相除法的演示动画
在
数学中，
辗转相除法，又称
欧几里得算法，是求
最大公约数的算法。辗转相除法首次出现于
欧几里得的《
几何原本》（第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(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r
1(0≤r)。若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，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。
如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。
由此我们可以得出以下推论：
推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）
推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除
因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h－t)c
所以：(a±b)也能被c整除
推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b
因为：a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1
所以：a=b
辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。
证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)
证明：
∵a为m,n的最大公约数，
∴m能被a整除，且n也能被a整除，
∴由推论1得：qn也能被a整除，
∴ 由推论2得：m-qn也能被a整除，
又 ∵m-qn=r，
∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）
∵b为n和r的最大公约数，a为n和r的公约数
∴a≤b，
同理
∵b为n, r的最大公约数，
∴n能被b整除，且r也能被b整除，
∴由推论1得：qn也能被b整除，
∴由推论2得：qn+r也能被b整除，
又∵m=qn+r，
∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）
∵a为m,n的最大公约数，b为m和n的公约数，
∴b≤a，
由以上可知：
a≤b与b≤a同时成立，
故可得
a=b，
证毕。
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
自然语言描述
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤r＜b）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步。
流程图
流程图(当型)
伪代码
这个算法可以用递归写成如下:
function gcd(a, b) {
if b<>0
return gcd(b, a mod b);
else
return a;
}
c语言实现
/* 辗转相除法（递归）*/
#include <stdio.h>
int Gcd(int a,int b);
int main(void )
{
int m,n,t;
printf("Enter the two figures:");
scanf("%d %d",&m,&n);
printf("Gcd:%d\n",Gcd(m,n));
return 0;
}
int Gcd(int m,int n)//最大公约数
{
int t;
if(m<n)
{t = n,n = m,m = t;}
if(n == 0) return m;
else return Gcd(n,m%n);
}
pascal实现
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
数据举例
其中“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
a,b辗转相除的算式为
b=q(1) a+r(2)
a=q(2) r(2)+r(3)
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
求(163,39)的算式为
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+72*78
所以x=-22,y=72是不定方程326x+78y=4的一组特解
注：q(i)，r(i)，括号中的是下标，lcm是求最大公约数
