欧几里得算法 这个就是常说的辗转相除法，用于计算两个整数 $a,b$ 的最大公约数，即$$gcd(a,b)=gcd(b,a\;mod\;b)$$
扩展欧几里德算法 是用来在已知 $a,b$ 求解一组整数解 $x,y$ 使它们满足等式：$$ax+by=gcd(a, b)$$
（解一定存在，根据数论中的相关定理 具体怎么证明我也不清楚）
那么问题来了如何求出一组 $x,y$
证明如下（重点）：
设 $a>b$
显然当 $b=0$ , $gcd(a,b)=a$ 时，$x=1$ , $y=0$ ；
原文：https://www.cnblogs.com/Pedesis/p/10339787.html