『数论』扩展欧几里得算法
欧几里得算法
辗转相除计算两个数的最大公约数,求$gcd(a,b)$.
设 $a=b×p+q$ ,则 $gcd(b,q)|b$ , $gcd(b,q)|a$ ,故 $gcd(b,q)|gcd(a,b)$ .
同样 $q=a−b×p$ ,则 $gcd(a,b)|q$ ,故 $gcd(a,b)|gcd(b,q)$ .
可得 $gcd(a,b)=gcd(b,a)$ ,最终得到 $gcd(a,b)=gcd(c,0)=c$
int gcd(int a, int b)
return b ? gcd(b, a % b) : a;
存在整数对 $(x,y)$ 使得 $ax+by=gcd(a,b)$ .
设