欧几里得算法及其扩展
前言
整除：对于整数 \(a(a\ne 0)\) 和 \(b\)，如果 \(\exists q\in Z\)，使得 \(b=a\times q\)，则称 \(a\) 能整除 \(b\)，记作 \(a\mid b\)。否则，称 \(a\) 不能整除 \(b\)，记作 \(a\nmid b\)。
最大公约数
公约数：如果一个整数是集合中任意一个元素的约数，则这个整数是该集合中的最大公约数。
最大公约数：集合的公约数中最大的一个，通常用 \(gcd\) 表示
欧几里得算法
过程
已知两个整数 \(a\) 和 \(b\)，其中 \(a>b\)
若 \(b\mid a\)，则 \(b\) 就是二者的最大公约数
若 \(b\nmid a\)，则对于 \(a=b\times q+r\)，有 \(gcd(a,b)=gcd(b,r)\)
证明：
设 \(a=gcd(a,b)\times m,b=gcd(a,b)\times n\)，有 \(r=a-bq=gcd(a,b)\times m-gcd(a,b)\times n\times q=gcd(a,b)\times(m-n\times q)\)
则 \(gcd(a,b)\mid r\)，所以 \(gcd(a,b)\) 也是 \(r\) 的约数
设 \(b=gcd(b,r)\times x,\ r=gcd(b,r)\times y\)，有 \(a=bq+r=gcd(b,r)\times x\times q+gcd(b,r)\times y=gcd(b,r)\times(xq+y)\)
则 \(gcd(b,r)\mid a\)，所以 \(gcd(b,r)\) 也是 \(a\) 的约数
所以，公约数相同，最大的公约数也相同
实现
static int gcd(int a, int b) {
if (a % b == 0) return a;
// 或 if(b==0) return a;
return gcd(b, a % b);
}
可以写成迭代的形式
static int gcd(int a, int b) {
if (a < b) return gcd(b, a);
while (b != 0) {
int t = a;
a = b;
b = t % b;
}
return a;
}
最小公倍数
公倍数：如果一个整数能被集合中任意一个数整除，则这个整数是该集合的公倍数。
最小公倍数：集合的公倍数中最小的一个，通常用 \(lcm\) 表示。
对于正整数 \(a\) 和 \(b\)
由算术基本定理得：\(a=p_1^{x_1}p_2^{x_2}\cdots p_n^{x_n}\)，\(b=p_1^{y_1}p_2^{y_2}\cdots p_n^{y_n}\)
则最小公倍数等于 \(p_1^{min(x_1,y_1)}p_2^{min(x_2,y_2)}\cdots p_n^{min(x_n,y_n)}\)
最大公约数等于 \(p_1^{max(x_1,y_1)}p_2^{max(x_2,y_2)}\cdots p_n^{max(x_n,y_n)}\)
由于 \(x_k+y_k=min(x_k,y_k)+max(x_k,y_k)\)
所以 \(gcd(a,b)\times lcm(a,b)=a\times b\)
所以 \(lcm(a,b)=\dfrac{a\times b}{gcd(a,b)}\)
扩展欧几里得算法
常用于求 \(ax+by=gcd(a,b)\) 的一组可行解
过程
\[\begin{aligned} ax+by&=gcd(a,b)\\ &=gcd(b,a\ mod\ b)&(1)\\ &=bx^{\prime}+(a\ mod\ b)y^{\prime}&(2)\\ &=bx^{\prime}+(a-b\cdot \big\lfloor\dfrac{a}{b}\big\rfloor)y^{\prime}&(3)\\ &=ay^{\prime}+b(x^{\prime}-\big\lfloor\dfrac{a}{b}\big\rfloor\cdot y^{\prime})&(4) \end{aligned} \]- 欧几里得定理
- \(gcd(a,b)=ax+by\)，\(b\)代入\(a\)，\(a\ mod\ b\)带入\(b\)
- 正整数取模定义，\(a\ mod\ b=a-\big\lfloor\dfrac{a}{b}\big\rfloor\cdot b\)
- 合并同类项
因此，\(ax+by=ay^{\prime}+b(x^{\prime}-\big\lfloor\dfrac{a}{b}\big\rfloor\cdot y^{\prime})\)
对比系数得：
\[\left\{\begin{array}{l} x=y^{\prime} \\ y=x^{\prime}-\left\lfloor\frac{a}{b}\right\rfloor y^{\prime} \end{array}\right. \]当 \(b=0\) 时， \(a=gcd(a,b)\)，由 \(ax+by=gcd(a,b)\) 得 \(gcd\cdot x+0\cdot y=gcd\)，则 \(x=1,y\in Z\) 是此时 \((a,b)\)的 一个整数解
作为人类，通常会选择令最后一层的 \(y=0\)
因为 \(y\) 在回代时会增长很快，无论正负
再从下至上递归求出 最开始的 \(ax+by=gcd(a,b)\) 的一组整数解 \((x_0,y_0)\)
此时可以得到方程的通解为 \(x=x_0+\dfrac{b}{gcd(a,b)}\cdot t\)，\(y=y_0-\dfrac{a}{gcd(a,b)}\cdot t\)，其中 \(t\in Z\)
若要求得 \(x\) 的最小正整数解，可以通过 \((x_0\%b+b)\%b\) 求得
值域分析
由于 \(ax+by=gcd(a,b)\) 的解有无数个，那求出的解如果趋近于无穷呢？
若 \(b\ne 0\)，扩展欧几里得算法求出的可行解必有 \(|x|\le b,|y|\le a\)
实现
static int x = 0, y = 0;
static int exgcd(int a, int b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int gcd = exgcd(b, a % b), t = x;
x = y;
y = t - a / b * y;
return gcd;
}
迭代方法
欧几里得算法可以通过迭代的方式求得最大公约数，那扩展欧几里得是否也能迭代呢？
答案是肯定的。
若 \(x,y\) 对应当前层，\(x^{\prime},y^{\prime}\) 对应下一层
初始情况，当 \(x=1\)，\(y=0\)，\(x^{\prime}=0\)，\(y^{\prime}=1\)时，则 \(ax+by=a\)，\(ax^{\prime}+by^{\prime}=b\)，方程成立。
由 \(gcd(a,b)=gcd(b,a-\left\lfloor\frac{a}{b}\right\rfloor b)\)，存储两层，顺次向下一层递推
\[\begin{aligned} ax+by&=a&(1)\\ a x^{\prime}+b y^{\prime}&=b&(2) \end{aligned} \]\((1)-\left\lfloor\frac{a}{b}\right\rfloor\times(2)\) 得 \((3)\)：\(a\left(x-\left\lfloor\frac{a}{b}\right\rfloor x^{\prime}\right)+b\left(y-\left\lfloor\frac{a}{b}\right\rfloor y^{\prime}\right) =a-\left\lfloor\frac{a}{b}\right\rfloor b\)
接下来 \((2)\) 变 \((1)\)，\((3)\) 变 \((2)\)，继续递推，直至求出 \(gcd\)，即 \(b=0\)
static int x = 0, y = 0;
static int exgcd(int a, int b) {
x = 1;
y = 0;
int nx = 0, ny = 1, q, t;
while (b != 0) {
q = a / b;
x -= q * nx;
t = x; x = nx; nx = t;
y -= q * ny;
t = y; y = ny; ny = t;
a -= q * b;
t = b; b = a; a = t;
}
return a;
}
int x, y;
int exgcd(int a, int b) {
x = 1, y = 0;
int nx = 0, ny = 1, q;
while (b != 0) {
q = a / b;
std::swap(x -= q * nx, nx);
std::swap(y -= q * ny, ny);
std::swap(a -= q * b, b);
}
return a;
}
二元一次不定方程
关于 \(x,y\) 的形如 \(ax+by=c\) 的方程是二元一次不定方程
裴蜀定理
对于 \(\forall a,b\in Z,\ \exists x,y\in Z\) 使得 \(ax+by=gcd(a,b)\)
证明（By other）：
首先，显然有 \(\operatorname{gcd}(a, b)|a\) ， \(\operatorname{gcd}(a, b)| b\) 。由整除的性质可知 $\forall x, y \in Z, g c d(a, b) \mid(a x+b y) $。设 \(s\) 为 \(a x+b y\) 的最小正值，故有 \(\operatorname{gcd}(a, b) \mid s\)。
设 \(k=\left\lfloor\frac{a}{s}\right\rfloor, r=a \bmod s\) ，则有 \(r=a-k(a x+b y)=a(1-k x)+b(-k y)\) ，发现 \(r\) 也为 \((a, b)\) 的线性组合，而 \(r\) 又在模 \(s\) 剩余系中，故 \(r \in[0, s-1]\)，又由于 \(s\) 为最小正值，故 \(r=0\)。
所以 \(s \mid a\)，同理 \(s \mid b\)，根据两个数的公约数必为这两个数的最大公约数的约数，有 \(s \mid \operatorname{gcd}(a, b)\)，而上文已证明 \(\operatorname{gcd}(a, b) \mid s\)，故 \(s=\operatorname{gcd}(a, b)\)。
进而得证，故 \(a x+b y=g c d(a, b)\) 这个方程一定有解
判断方程有整数解的条件
方程 \(ax+by=c\) 有整数解的充要条件是 \(gcd(a,b)\mid c\)
证明（By other）：
考虑将 \(ax+by=\operatorname{gcd}(a, b)\) 变为 \(ax+by=c\)
为了区分这两个方程，我们将前者改为 \(a^{\prime} x+b^{\prime} y=\operatorname{gcd}\left(a^{\prime}, b^{\prime}\right)\)
令 \(k=\operatorname{gcd}\left(a^{\prime}, b^{\prime}\right)\)，方程两边同除 \(k\)，得: \(\frac{a^{\prime}}{k} x+\frac{b^{\prime}}{k} y=1\)方程两边同乘c得：\(\frac{a^{\prime} c}{k} x+\frac{b^{\prime} c}{k} y=c\)
只要通过换元，即令 \(a=\frac{a^{\prime} c}{k}, b=\frac{b^{\prime} c}{k}\)，即可将方程转化为 \(a x+b y=c\) 的形式
考虑到 \(\operatorname{gcd}\left(\frac{a^{\prime} c}{k}, \frac{b^{\prime} c}{k}\right)=c=\operatorname{gcd}(a, b)\)，且对于一般的方程: $a t x+b t y=c{\prime}\left(c=c t, t \in Z\right) $
故只有 \(c\) 为 \(\operatorname{gcd}(a, b)\) 倍数时原方程有解，即 \(\operatorname{gcd}(a, b) \mid c\)，从而得证。
求解二元一次不定方程
对于解方程 \(ax+by=c\)，可以先解方程 \(ax+b y=\operatorname{gcd}\left(a, b\right)\)
当我们得到了 \(a x+b y=\operatorname{gcd}\left(a, b\right)\) 的一组解 \(x_0^{\prime},y_0^{\prime}\)，即 \(ax_0^{\prime}+by_0^{\prime}=gcd(a,b)\)
两边同时除以 \(gcd(a,b)\)，再乘以 \(c\)，即 \(a\dfrac{c\times x_0^{\prime}}{gcd(a,b)}+b\dfrac{c\times y_0^{\prime}}{gcd(a,b)}=c\)
则 \(x_0=\dfrac{c\times x_0^{\prime}}{gcd(a,b)},\ y_0=\dfrac{c\times y_0^{\prime}}{gcd(a,b)}\) 是 \(ax+by=c\) 的一组特解
此时可以得到方程的通解为 \(x=x_0+\dfrac{b}{gcd(a,b)}\cdot t\)，\(y=y_0-\dfrac{a}{gcd(a,b)}\cdot t\)，其中 \(t\in Z\)
若要求得 \(x\) 的最小正整数解，可以通过 \((x_0\%b+b)\%b\) 求得
线性同余方程
关于 \(x\) 的形如 \(ax\equiv c(mod\ b)\) 的方程被称为线性同余方程。
与 二元一次不定方程 等价
对于方程 \(ax\equiv c(mod\ b)\)，等价于 \(ax+by=c\)，其中 \(y=\left\lfloor\frac{c}{b}\right\rfloor-\left\lfloor\frac{a x}{b}\right\rfloor\)
证明：
\[\begin{aligned} ax&\equiv c(mod\ b)\\ ax\ mod\ c&= b\ mod\ c&(1)\\ ax-b\times \left\lfloor\frac{a x}{b}\right\rfloor&=c-b\times\left\lfloor\frac{c}{b}\right\rfloor&(2)\\ ax+(\left\lfloor\frac{c}{b}\right\rfloor-\left\lfloor\frac{a x}{b}\right\rfloor)b&=c&(3)\\ \end{aligned} \]
- 同余号转等号
- 取模定义 \(a\ mod\ b=a-b\times \big\lfloor\dfrac{a}{b}\big\rfloor\)
- 合并同类项
求解线性同余方程
转化为 二元一次不定方程，求解该不定方程，即是求解线性同余方程
参考资料
求解一类方程的方法 - Nickel_Angel's nest
标签：prime,right,gcd,int,欧几里得,扩展,times,算法,ax From： https://www.cnblogs.com/Cattle-Horse/p/17095576.html