欧几里得算法，也称辗转相除法，是解决数学类问题中求两个数的最大公约数的常用算法，其原理为: $gcd(x,y) = gcd(y,x (mod~y))$

那么现在我们要证明其原理的正确性

---

证明：

$1.$

我们要证明$x,y$的最大公约数与$y，x~mod~y$的最大公约数相等

我们不妨设$x = ky~+~b$，显然有$b = x~mod~y$

$b = x-ky$

继续设$x~mod~d = 0$ && $y~mod~d = 0$

则有等式$x/d-(y/d)*k = b/d$

由等式左边可得，$d|b$

分析等式可得d是$x，y$的公约数，它也会是$y,x~mod~y$的公约数

$2.$

反过来也需要证明

设$y~mod~d = 0$ && $b~mod~d = 0$

我们依然可以得到之前的等式：

$x/d-(y/d)*k = b/d$

即 $b/d+(y/d)*k = x/d$

左边的式子即为整数，所以d|x

既然有整数$d$既是$x,y$的公约数，又是$y,x$的公约数

那么我们完全可以得出$gcd(x,y) = gcd(y,x(mod~y))$

则欧几里得算法的正确性是毋庸置疑的

---

证毕