拓展欧几里得入门

内容

扩展欧几里德算法是用来在已知a, b求解一组整数解x，y，使它们满足贝祖等式（具体不是很清楚是啥意思，反正就那样）： \(ax+by = gcd(a, b) =d\)（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

详细讲解+推导

• 对于普通的公式\(ax+by = c\)有整数解的条件是\(c=k*gcd(a, b)\)，k为任意常数。

• 对于公式\(ax+by = gcd(a, b) =d\)，求解其中一个x，y的方法及其证明

  1. 显然当 \(b=0,gcd(a,b)=a\)时，此时 \(x=1, y=0\)；

  2. \(a>b>0\) 时，设
     \[ ax_1+ by_1= gcd(a,b) \]

  \[ bx_2+ (a\ mod\ b)*y_2= gcd(b,\ a\ mod\ b) \]

  根据朴素的欧几里德原理有
  \[ gcd(a,b) = gcd(b,a\ mod\ b) \]
  则:
  \[ ax_1+ by_1= bx_2+ (a\ mod\ b)y_2 \]
  即:
  \[ ax_1+ by_1= bx_2+ (a - [a / b] * b)y_2=ay_2+ bx_2- [a / b] * by_2 \]
  说明： \(a-[a/b]b\)即为mod运算。\([a/b]\)代表取小于\(a/b\)的最大整数，下面同样适用。

  也就是
  \[ ax_1+ by_1 == ay_2+ b(x_2- [a / b] *y_2) \]
  根据恒等定理，对应项的系数相等得：
  \[ x_1=y_2 \]

  \[ y_1=x_2- [a / b] *y_2 \]

  这样我们就得到了求解 \(x_1,y_1\) 的方法：\(，，，x_1，y_1\) 的值基于\(，，， x_2，y_2\)。使用递归的话，上一层的值，取决于下一层。

  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

  递归边界：
  \[ gcd（a,\ 0）=1*a-0*0=a \]

• 对于公式\(ax+by = c\)，求解x，和y的方法

  1. 如果\(c\ \%\ gcd( a , b) != 0\)，即c不是gcd的整数倍，则无解。
  2. 如果\(c\ \%\ gcd(a,b) == 0\) ，则\(c\ /\ gcd(a,b) = t\)，那么求出方程 \(a * x + b * y = gcd(a,b)\)的所有解x,y，将x,y乘上t，对应的x’,y’即是方程\(a * x + b * y = t * gcd(a,b)\)的一个解

• 如何求\(ax+by = gcd(a, b) =d\)最小整数解，对于\(ax+by = c\)，c为常数，也适用。

  1. 我们可以用扩展欧几里得算法得出
  2. \(ax+by=gcd(a,b)\)的一组解\(（）（x_1,\ y_1）\)，那么其他解呢？任取另一组解\(（）（x_2,\ y_2）\)则

\[ ax_1+by_1=ax_2+by_2 \]

? （因为它们都等于\(gcd(a,b)\) ），变形得
\[ a(x_1-x_2)=b(y_2-y_1) \]
? 假设\(gcd(a,\ b)=g\)，方程左右两边同时除以g（如果g=0，说明a或b等于0，可以特殊判断），得
\[ a'(x_1-x_2)=b'(y_2-y_1) \]
? 其中\(，，，a'=a/g，b'=b/g\)。

? 注意，此时a‘和b‘互素（想想分数的化简）
\[ x_1-x_2=\frac{b'}{a'}*(y_2-y_1) \]
? 则因此\(x_1-x_2\)一定是b‘的整数倍（因为a‘中不包含b‘，所以\(x_1-x_2\)一定包含b‘）。

? 设它为\(x_1-x_2=k*b'\)，计算得\(y_2-y_1=k*a'\)。注意，上述的推导过程并没有用到\(ax+by\)的右边是什 么，因此得出以下结论：

? 设a,b,c为任意整数，若方程\(ax+by=c\)的一组解是\((x_0,y_0)\)，则它的任意整数解都可以写

? \((x_0+k*b',y_0-k*a')\)，其中\(a'=[a/gcd(a,b)]\)，\(b'=[b/gcd(a,b)]\)，k取任意整数。

? 这样我们就可以求出来最小的整数解了。（先用扩展欧几里得算法求出一组解，然后进行变换）

例题

请参考我的另一篇文章

END

拓展欧几里得入门+推导

原文：https://www.cnblogs.com/alking1001/p/11268144.html