数学知识--数论-526互联

扩展欧几里得

用于求解$ax + by = gcd(a,b)$的解，利用辗转相除法构造出x，y的通解

当$b = 0$时，$ax + by = a$，可令$x = 1，y = 0$

当$b \neq 0$时，因

$gcd(a, b)$ $=$ gcd(b,a % b$)$

而bx′

$bx^′ + (a % b)y^′=gcd(b,a % b)$

同余问题 ${a*x {\equiv} b(mod m)}$，化简成求解同余方程$a_i \times x_i + b_i \times y_i =gcd(a_i,b_i) $的问题，扩展欧几里得利用