也被称为欧几里得算法

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（greatest common divisor）缩写为$gcd$

$gcd(a,b)=gcd(b,a\,mod\, b)(不妨设a>b且r=a\, mod\,b,r≠0)$

$a$ 可以表示成 $a=kb+r$($a，b，k，r$皆为正整数，且$r<b$)

则 $r=amodb$ 假设$d$是 $a,b$ 的一个公约数，即$a$和 $b$ 都可以被 $d$ 整除。

则 $r=a−kb$，两边同时除以 $d$，可得$\frac{r}{d}=\frac{a}{d}-\frac{kb}{d}=m$

由等式右边可知 $m$ 为整数（ $d$ 是$a$的公约数，$kb$是$b$ 的整倍数，所以$\frac{kb}{d}$也应该是整数），我们得出 $d$ 也为 $a$ 和 $b$ 的余数的公约数 即 $d$ 是 $(b ,a\,mod\,b)$ 的公约数

至此，我们得知，如果一个数是两个数的公约数，那么，它也是这两个数的余数和较小数公约数。

假设 $d$ 是 $(b,amodb)$的任意一个公约数, 则 $d$ 是 $b$ 的公约数, $d$ 是 $(a−kb)$ 的公约数, $k$是一个整数 我们假设 $b=xd, a−kb=yd$ 其中 $x,y$是正整数，根据上面的推断可得:$a=yd+kb$

两边同时除以 d 得$\frac ad=y+\frac {kb}d$

由已知可得 $y$为正整数， $d$ 是 $b$的公约数， $kbd$也肯定是正整数，故得$d$ 为 $a$的公约数. 因为 $d$既是 $b$公约数又是 $a$ 的公约数了， 所以证出$(a,b)$ 和 $(b,a\ mod\ b)$的公约数是一样的，其最大公约数也必然相等。