欧几里得与扩展欧几里得总结

欧几里得

来看看一个常见的(gcd)代码

int Gcd(a,b){
    return (b==0)?a:Gcd(b,a%b);
}

入门的一个知识吧，但是你会证明吗？

(emmm) 好吧我就只是背背代码过来的

• 证明：
  别想太多，我们只是要证(gcd(a,b)=gcd(b,a\%b))而已啦
  设(r=a\%b)
  则(a=kb+r)其实(k)为常数
  设有实数(d)满足(d|a,d|b)
  (a=kb+r Rightarrow r=a-kb)
  ( herefore d|r) (d)是(b,r)的公约数

扩展欧几里得

(exgcd)代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

似乎背这个的更多(滑稽

• 证明：
  必定存在整数对((x,y))使得(ax+by=gcd(a,b))
  (ax_1+by_1=gcd(a,b))
  (bx_2+(a\%b)y_2=gcd(b,a\%b))
  ( herefore ax_1+by_1=bx_2+(a\%b)y_2)
  (Rightarrow ax_1+by_1=bx_2+(a-(a/b)*b)y_2)
  (~~~~~~~~~~~~~~~~~~~=ay_2+bx_2-(a/b)*b*y_2)
  根据恒等定理 (x_1=y_2,y1=x_2-(a/b)y_2)
  至此，我们得到了求解((x1,y1))的方法
  由于((x1,y1))的值基于((x2,y2))
  欧几里得因为求(gcd)不断的递归求解一定会(b=0)所以递归可以结束
  只需要在原有欧几里得算法基础上稍微加一点代码就得出扩展欧几里得算法啦

应用

解不定方程(ax+by=c)
前置芝士

• 1.((a,b))的最小线性组合元素是(gcd(a,b))
  证明：
  设s为((a,b))的最小线性组合元素，(a\%s)也是((a,b))的线性组合元素
  (ecause s为)(a,b)(的最小线性组合元素 herefore a\%s=0,s|a)
  同理(s|b)，所也(s)为(a,b)的公约数
  ( herefore gcd(a,b)|s Rightarrow gcd(a,b)<=s)
  由于基本事实 (s>0)且(gcd(a,b)>=s)
  得出推论：((a,b))的最小线性组合元素是(gcd(a,b))

• 2.裴蜀定理：不定方程(ax+by=c) (gcd(a,b)|c)时有解
  证明：这还需要证明吗(逃 确实根据上面的随便想想就懂了

做法

• 其实就是解(ax+by=gcd(a,b))然后解乘上(dfrac{c}{gcd(a,b)})
  关于(ax+by=gcd(a,b))的方程，对于一组解((x_0,y_0))
  对应的一组关于原方程的解((x_1=x_0*dfrac{c}{gcd(a,b)},y_1=y_0*dfrac{c}{gcd(a,b)}))

• ((x_1+b/gcd(a,b)*t,y_1-a/gcd(a,b)*t))其中t为任意整数，是不是有点难理解qwq，带进去就懂了：

[egin{aligned}\ a(x_1+b/gcd(a,b)*t)+b(y_1-a/gcd(a,b)*t))&=ax_1+ab/gcd(a,b)*t+by_1-ab/gcd(a,b)*t\ &=ax_1+by_1\ end{aligned}]

• 通常我们会要求最小解，怎么办呢？
  显然(b/gcd(a,b))是解集({x})的最小间隔
  设(s)为这个最小间隔
  则(x)的最小正整数解为((x1\%s+s)\%s)
  就不证明啦。。。自己理解一下吧，最小间隔都告诉你了，不就是加上或减去若干个(s)嘛