扩展的欧几里得算法

最大公约数表示定理

$a,b\in \mathbb{Z},gcd(a,b)=d⟺\exists a,t\in \mathbb{Z},as+bt=d$ 特别地，$gcd(a,b)=1⟺as+bt=1$ 推论：$d|v⟺as+bt=v$

广义欧几里得算法就是用于计算