在數學中，辗转相除法，又称欧几里得算法（英語：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术 展开

计算过程
辗转相除法是一种递归算法，每一步计算的输出值就是下一步计算时的输入值。 设$${\displaystyle k}$$表示步骤数（从0开始计数），算法的计算过程 … 展开

辗转相除法是目前仍然在使用的历史最悠久的算法之一。 它首次出现于《几何原本》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以現代 … 展开

贝祖等式
贝祖等式说明，两个数$${\displaystyle a}$$和$${\displaystyle b}$$的最大公约数$${\displaystyle g}$$可 … 展开

如上文所述，辗转相除法最早用来寻找两自然数的最大公约数，但其实它也可以被推广至实数，甚至是多项式、二次整数和赫尔维茨四元数。在这些数系中，辗转相除法甚至被用来證明一个重要特 … 展开

最大公约数
欧几里得的辗转相除法计算的是两个自然数$${\displaystyle a}$$和$${\displaystyle b}$$的最大公约数$${\displaystyle g}$$，意思是能够同时整除$${\displaystyle a}$$和$${\displaystyle b}$$的自然数中最大的一个。两个数的最大 … 展开

辗转相除法的计算效率已经被彻底研究过了。 一个算法的效率可以用计算所需步数乘以每步计算的开销表示。加百利·拉梅于1884年指出 ，用辗转相除法计算两个数的最大公约数所需的步数不 … 展开