Exgcd学习笔记引理Bézout'stheorem对于\(gcd(a,b)=d\)的情况，一定\(\existsx,y\)，使得\(ax+by=d\)成立。相反的，当解方程\(ax+by=c\)时，若\(c\)不是\(d\)的倍数，那么此方程一定无解。Exgcd推导我们知道如何通过辗转相除法求出\(gcd(a,b)\)，那么结合贝祖定理，不难