最大公约数历史发展在求解最大公约数的几种方法中，辗转相除法最为出名

辗转相除法是仍然在使用的历史最悠久的算法之一

它首次出现于几何原本（卷7命题1–2、卷10命题2–3）（大约公元前300年）

在卷7中用于整数，在卷10中用于线段的长度（也就是所说的实数，但是当时未有实数的概念）

卷10中出现的算法是几何的，两段线段a和b的最大公约数是准确测量a和b的最大长度

这个算法可能并非欧几里得发明，而仅仅是将先人的结果编进他的几何原本

数学家、历史学家范德瓦尔登认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书

辗转相除法是被大约公元前375年的欧多克斯发现的，但也有可能更早之前就已经存在，因为欧几里得和亚里士多德的这两位历史名人著作中都出现了ἀνθυφαίρεσις一词（anthyphairesis, 意为“辗转相减”），几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及指定准确的历法

5世纪末，印度数学家、天文学家阿里亚哈塔可能是因为辗转相除法在解丢番图方程时的高效率而称它为“粉碎机”

因为在中国，孙子算经中出现了此算法的一个特例中国剩余定理，但是辗转相除法的完整表述直到1247年秦九韶的数学九章中才出现

在欧洲，辗转相除法首次出现于克劳德·巴希特（英语：Claude Gaspard Bachet de Méziriac）的著作Problèmes plaisants et délectables的第二版在欧洲，辗转相除法广泛使用于丢番图方程和连分数

后来，英国数学家桑德森（英语：Nicholas Saunderson）将扩展欧几里得算法作为罗杰科茨（英语：Roger Cotes）对计算连分数的方法的研究发表

19世纪，辗转相除法孕育出了一些新的数系，如高斯整数和艾森斯坦整数

1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，他的研究发表于1832年

高斯在他的《算数研究》（published 1801）中，作为处理连分数的方法提到了这个算法

约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家

狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法成立的数系中有效

狄利克雷的观点被理查德·戴德金修改和推广，他用辗转相除法研究代数整数

戴德金是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家

戴德金还率先定义了欧几里得整环的概念

19世纪末，辗转相除法的辉煌逐渐被戴德金的理想取代

辗转相除法的其他应用发展于19世纪

1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）

辗转相除法是历史上第一个整数关系算法（英语：integer relation algorithm），即寻找两数的整数关系的算法

近年来，出现了一些新颖的整数关系算法，如埃拉曼·弗格森（英语：Helaman Ferguson）和福尔卡德于1979年发表的弗格森-福尔卡德算法、以及与它相关的LLL算法（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法（英语：PSLQ algorithm）

1969年，科尔(Cole)和戴维(Davie)基于辗转相除法创造了一种二人游戏，叫做欧几里得游戏

这个游戏有最优策略

游戏开始于两列分别为a和b个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子

如果两列棋子a和b分别由x和y个棋子组成，其中x大于y，那么玩家可以序列a的棋子数量减少为自然数x − my

最后率先将一列棋子清空的玩家胜出

扩展欧几里得算法扩展欧几里德算法：扩展欧几里得算法（又称扩充欧几里得算法）是用来解某一类特定的不定方程的一种方法，常用用来求解模线性方程及方程组

扩展的欧几里得算法可以用来计算模逆元，而模逆元在公钥密码学中占有举足轻重的地位

 基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by

证明：设 a>b

1，显然当 b=0，gcd（a，b）=a

此时 x=1，y=0；2，ab≠0 时设 ax1+by1=gcd(a,b);bx2+(a mod b)y2=gcd(b,a mod b);根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);则：ax1+by1=bx2+(a mod b)y2;即：ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束

 Stein算法欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的

但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数

和欧几里德算法算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音

 Stein算法：设置A1=A、B1=B和C1=11、如果An=0，Bn*Cn是最大公约数，算法结束2、如果Bn=0，An*Cn是最大公约数，算法结束3、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)4、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn (很显然啦，2不是奇数的约数)5、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn (很显然啦，2不是奇数的约数)6、如果An和Bn都不是偶数，则An+1=|An-Bn|，Bn+1=min(An,Bn)，Cn+1=Cn7、n加1，转步骤1考虑欧几里德算法，最恶劣的情况是，每次迭代a=2b-1,这样，迭代后，r=b-1

如果a小于2N，这样大约需要4N次迭代

而考虑Stein算法，每次迭代后，显然A(n+1)B(n+1)≤AnBn/2，最大迭代次数也不超过4N次

也就是说，迭代次数几乎是相等的

但是，需要注意的是，对于大素数，试商法将使每次迭代都更复杂，因此对于大素数Stein将更有优势

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。