非负数是数学中常常涉及到的概念。在实际问题中，计算非负数的最大公约数是非常重要的。欧几里得算法，又称辗转相除法，就是用来计算两个数的最大公约数的一种方法。
欧几里得算法基于这样一个事实：两个正整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。这可以用算法的形式表述：
输入两个非负整数m和n，其中m≥n。如果n=0，算法结束，m即为答案。
否则，计算m除以n所得的余数，令m为n，而n为该余数。算法回到第一步。
这个算法简单直观，而且时间复杂度为O(logn)，非常高效。欧几里得算法还可以推广到计算多个数的最大公约数。具体做法是将这些数两两配对，继续通过欧几里得算法求出它们的最大公约数，然后把所得的最大公约数再两两配对，直到所有数的最大公约数求出。
除了计算最大公约数，欧几里得算法还可以应用到其它许多问题中。比如，可以用它来判断两个数是否互质，即它们的最大公约数是否为1。在密码学中，欧几里得算法被用来计算模反元素，就是求出一个数的“倒数”模另一个数的值。欧几里得算法也可以用来实现辗转相除法求解同余方程，以及一些其他的数论问题。
