7.3 高德纳的精辟评价
用现代语言表示当年原始的欧几里得算法，是由算法和程序设计技术的先驱、计算机排版系统TeX的发明者高德纳[1]做出的。
这段论述，观点精辟，发人深思。
欧几里得算法见于欧几里得的《原本》一书（大约公元前300年）的卷7，命题1和2，但这大概不是他自己的发明。学者们相信这个方法大约在那之前200年就已经知道了，至少以它的减法形式，而且几乎肯定为Eudoxus（约公元前375年）所知。
我们可以把欧几里得算法称作所有算法的祖先，因为它是今日幸存的最老的不寻常的算法，主要能与这一荣耀相抗衡的也许是古老的埃及的乘法方法，它是以加倍和加法为基础的，形成有效计算第n次乘方的基础。但是埃及的原稿仅给出不是完全系统的一些例子，而且这些例子肯定未加系统阐述。因此埃及的算法肯定配不上算法的名字。我们也知道用于诸如解两个变量的特殊二次方程组的若干古代巴比伦人的方法，其中包含了一些真正的算法，而不仅仅是对于某些输入参数的方程特殊解。尽管巴比伦人总是联系对具体的输入数据进行工作的例子来介绍每个方法，但他们总是有规律地伴随着正文来说明一般过程。这些巴比伦算法中有许多比欧几里得算法早大约1500年，而且它们是已知最早的关于数学的书面过程的例证。但它们都没有欧几里得算法的气质，因为它们都不含迭代，而且还因为它们已为现代代数方法所代替。
由于欧几里得算法从实用上和从历史上说都是重要的，现在就让我们考虑欧几里得本人是怎样处理它的。把他的话语译成现代术语，欧几里得所说的就是：
命题 给定两个正整数，求它们的最大公因子。
设A和C是两个给定的两个正整数，求它们的最大公因子。如果C整除A，则C就是C和A的一个公因子，因为它也整除本身。而且事实上显然它是最大的，因为再无比C大的数能整除C了。
但如果C不整除A，则不断地从A，C两数中之大者减去小者，直到得出整除前一数的某个数。这种情况最终一定要发生，因为如果得到的是1，则它就整除前一个数。
现在设E是A除以C的正余数；设F是C除以E的正余数，而且设F是E的一个因子。由于F整除E和E整除C-F，故F也整除C-F，但它也整除本身，所以它整除C。而且C整除A-E，因此F也整除A-E，但它也整除E，因此它整除A。于是它是A和C的一个公因子。
现在论证它也是最大的。如果F不是A和C最大的公因子，则将有某个更大的数整除它们。设这样的一个数是G。
现在由于G整除C而C整除A-E，故G整除A-E，但也整除整个A，所以它整除余数E，但E整除C-F，因此G也整除C-F，但G也整除整个C，所以它整除余数F，即一个较大的数整除一个较小的数，这是不可能的。
因此，没有大于F的数能整除A和C，所以F是它们的最大公因子。
推论 这一论证使得下列结论成为显然：整除两个数的任何数必整除两个数的最大公因子。证毕。
这里在一个重要方面简化了欧几里得的叙述：希腊数学家不认为1是另外的正整数的“因子”。两个正整数或者都为1，或者互素，或者有一个最大的公因子。事实上，1甚至不被认为是一个“数”，而且0当然是不存在的。这些相当笨拙的约定使得欧几里得有必要重复他的许多讨论，而且他已经给出了两个分开的命题，其中每一个实际上都同现在给出的这个相类似。
在欧几里得的讨论中，他首先提出重复地从两个现有数的大者减去小者，直到我们得到这样两个数——其中一个是另一个的倍数为止。但在证明中，他实际上依赖于一个数除以另一个数的余数，由于他没有0的简单概念，故他不能说一个数整除另一个时的余数是什么。所以可以合理地认为，他想象每个除法（不是个别的减法）都是算法的一个单一的步骤，因此对他的算法的“真正的”意译也许可以说是下面的算法：
算法E（原始欧几里得算法） 给定两个大于1的整数A和C，本算法求它们的最大公因子。
E1.[A可被C整除？] 如果C整除A，则这算法以C作为答案终止。
E2.[以余数代替A] 如果A mod C等于1，则给定的数互素，所以算法终止。否则，以（C，A mod C）代替（A，C）并返回步骤E1。
上面摘录的欧几里得给出的证明，是特别有趣的，因为它实质上全然不是证明！他只是实施步骤E1一次或三次验证了这个算法的结果，他必然认识到步骤E1可进行三次以上，尽管他没有提出这样的可能性。由于没有用数学归纳法给出一个证明的思想，他仅仅对于有限种情况给出了一个证明（事实上，对于要求对一般的n建立的过程，他通常仅仅证明n=3的情况）。尽管欧几里得由于在逻辑推导的技巧上所作的推进而应得地闻名于世，但通过归纳法给出正确证明的技术直到现在才真正搞清楚。
设A和C是两个给定的正整数，求它们的最大公约数。
若C能整除A，显然它也整除本身，则C就是C和A的一个公约数。同时也没有比C大的数能整除C，所以C就是A和C的最大公约数，算法终止。
若C不能整除A，则重复从A，C两数中的大数减去小数，直到得出一个数能整除另一个数，则最后被整除的数就是A和C的最大公约数，算法终止。
可以看到，欧几里得以整除作为判断最大公约数的标志。
当时的希腊数学家不认为1是另外的正整数的“因子”。两个正整数或者都为1，或者互素，或者有一个最大的公因子。事实上，1甚至不被认为是一个“数”，0当然是不存在的。欧几里得实际上依赖于一个数除以另一个数的余数，由于他没有0的简单概念，说不出一个数整除另一个数时的余数是什么。