数学-数论-扩展欧几里得算法

Posted by

定义

扩展欧几里得算法用于已知$a,b$,求解一组$x,y$,使得他们满足$ax+by=gcd(a,b)=d$。

有关概念

  1. 设$a,b$是整数,则一定存在$x,y$,使得方程$ax+by=m$有解,其中$m$满足$gcd(a,b)|m$。我们称之为裴蜀定理(贝祖定理),它保证了扩展欧几里得算法所要求的方程有解。

求解算法

思路与简单证明

首先设$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-\lfloor \frac ab\rfloor\times b)y_2$;
得$ax_1+by_1=ay_2+b(x_2-\lfloor \frac ab\rfloor y_2)$;
根据多项式恒等定理,得:
$x_1=y_2,y_1=x_2-\lfloor \frac ab\rfloor y_2$
于是我们发现,可以按照类似欧几里得算法的形式递归求解,边界条件:
当$b=0$时,$gcd(a,b)=a$,此时方程的解为$x=1,y=0$。

实现

应用

  1. 求解线性同余方程$ax+by=c$:
    先用扩展欧几里得算法求出一组解$x_0,y_0$,之后等号两边同时除以$gcd(a,b)$,再同时乘以$c$,就求得了方程的一个解。 该方程的任意一组解可以表示为$x=x_0+bt,y=y_0-at,\quad t\in Z$。

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注