##### 扩展欧几里得算法 - 扩展欧几里得算法 - **扩展欧几里得算法**是对[[欧几里得算法]]的扩展, 它不仅能求出两个[[整数]]的[[公约数|最大公约数]] $\gcd(a, b)$, 还能求出[[裴蜀定理]]中的一组整数 $x$, $y$. 关键在于反向回代, 即从求解最大公约数的过程中回推, 得到满足 $ax + by = \gcd(a, b)$ 的整数解