求解最大公因子

$$(a,b)=(a,b-qa)$$

欧几里得除法

$$r_{n-2}=q_{n-1}{r}_{n-1}+r_n,0\le r_n<r_{n-1}$$ $$r_n=(a,b)$$

从下往上推是公因数之一，从上往下任意设一个公因数根据整除的线性组合能够推出也整除最终的 $r_n$

如果把递推式全部展开，则最后的最大公因子就是两个数的线性组合。所以如果是最大公因数，那么一定能够找到一组线性组合出来（但是不唯一）

$$sa+tb=(a,b)=r_n$$

---

求逆元

指向原始笔记的链接