从小学高年级开始，学校里就会教一些质因数分解和最大公约数的相关知识。通常来说，我们都是通过质因数分解来求两个数的最大公约数的，但这个方法对两个非常大的数而言就显得捉襟见肘，不是那么好用了。因为有时候我们根本不知道这两个大数能被哪些质数整除，光对两个大数进行质因数分解就是一项很大的工程，更何况是求最大公约数了。
这个时候，部分老师会教小朋友们一种叫做“辗转相除法”的方法，这就是今天我们要介绍的“欧几里得算法”(Euclidean algorithm)。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷，命题i和ii)中，而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的“最大公约数”(Greatest Common Divisor，简称GCD)是指能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如：252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 − 105 = 21 × (12 − 5) = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252。这个重要的结论叫做“裴蜀定理”。
辗转相除法最早出现在欧几里得的《几何原本》中(大约公元前300年)，所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度(相当于正实数)，但在19世纪，辗转相除法被推广至其他类型的数学对象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。
辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法(一种在电子商务中广泛使用的公钥加密算法)的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
简单介绍完了欧几里得算法之后，我们重要的是理解为什么欧几里得算法总是可行的?
举个例子：求GCD(175,65)。
通常的做法是：
1、先用65去除175，得到：175=2×65+45;
2、然后用余数45去除65，得到：65=1×45+20;
3、再用余数20去除45，得到：45=2×20+5;
4、最后用余数5去除20，得到：40=4×5+0。
在倒数第二步中得到的余数5就是175和65的最大公约数了。
这个过程用图形来演示的话，如下图所示：
上述过程还可以用另一种形式表达出来，即：GCD(175,65)=GCD(110,65)=GCD(45,65)=GCD(20,45)=GCD(20,25)=GCD(5,20)=GCD(5,15)=GCD(5,10)=GCD(5,5)=5。
欧几里得的辗转相除法的核心思想其实就是整除的“可加性”：若?|?，?|?，则?|(?±?)。用图形来表示就是：
说明：“?|?”意味着“表示较小数?的线段可以量尽表示较大数?的线段";“?|?”意味着“表示较小数?的线段可以量尽表示较大数?的线段";所以“表示较小数?的线段显然可以量尽表示较大数?与?的两根线段的和或者差”。
这个方法也可以延伸到求三个乃至任意多个数的最大公约数问题上去。
辗转相除法在处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数(十进制下)的五倍。读者朋友们可以自己尝试计算一下：
GCD(1 160 718 174, 316 258 250)
数学家拉梅于1844年证明了这点，同时这也标志着计算复杂性理论的开端。
高德纳称：“欧几里得算法是所有算法的鼻祖，因为它是现存最古老的非凡算法。”这个算法可能并非欧几里得发明，因为他也有将先前其他数学家的一些成果编进他的《几何原本》。数学家、历史学家范德瓦尔登认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯(大约公元前375年)所知，甚至可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了ἀνθυφαίρεσις一词(意为“辗转相减”)。
几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”。《孙子算经》中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其《数学九章》中解答了该定理的一般情况，当中用到了他发明的“大衍求一术”。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于克劳德·巴希特的著作中。在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家桑德森在其著作中收编了扩展欧几里得算法，作为一个有效计算连分数的方法。他将此法的来源归名于罗杰·科茨。
19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。辗转相除法也是历史上第一个整数关系算法，即寻找两个可通约实数的整数关系的算法。
好了，欧几里得算法的原理和相关历史知识就介绍到这里。总而言之，欧几里得算法是一个非常重要的知识，同学们要理解并熟练掌握它。