扩展欧几里德|模线性方程

定义

对于不完全为0的整数a，b，gcd(a,b)表示a，b的最大公约数。那么一定存在整数x，y 使得gcd(a,b)=ax+by。

求解

求一组解x,y，使得 $ax+by=gcd(a,b)$

因为欧几里得定理，可以得到 $gcd(a,b)=gcd(b,a\%b)$

令x',y'为变量，得 $bx'+(a\%b)y'=gcd(b,a\%b)$

所以 $ax+by=bx'+(a\%b)y'$

因为 $a\%b=a-\left \lfloor \frac{a}{b} \right \rfloor*b$

所以 $ax+by=bx'+(a-\left \lfloor \frac{a}{b} \right \rfloor*b)y'$

整理 $ax+by=ay'+b(x'-\left \lfloor \frac{a}{b} \right \rfloor*y')$

得到 $x=y',y=x'-\left \lfloor \frac{a}{b} \right \rfloor*y'$

由最后的表达式可以看出，我们可以通过递归进行求解。

//求解ax+by=gcd(a,b)一组特解
long long exgcd(long long a,long long b,long long &x,long long &y)
{  
  if(!b) {x=1;y=0;return a;}
  long long ans=exgcd(b,a%b,x,y);
  long long t=x;
  x=y;
  y=t-(a/b)*y;
  return ans;
}

模线性方程

模线性方程的一般形式为 $ax\equiv b \ \ (mod \ n)$ ， $ax\equiv b \ \ (mod \ n)$ 等价为 $ax+yn=b$ 。

性质：

①方程ax≡b(mod n)对于x有解，当且仅当gcd(a,n)|b。

②方程ax≡b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。

③设d=gcd(a,n)，假定一对整数x和y满足d=ax+by。如果d|b，则方程ax=b(mod n)有一个解x满足x0=x*(b/d)mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod (n/d)，最大整数解x2=x1+(d-1)*(n/d)。

④假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。

求解

由性质可以看出，模线性方程的所有解可以通过求一个特解从而间接求出。

由扩展欧几里德定理求出方程特解x0，再通过xi=x0+i*(n/d) mod n 求出所有解。

本博客仅为本人学习，总结，归纳，交流所用，若文章中存在错误或有不当之处，十分抱歉，劳烦指出，不胜感激！！！