去博客看吧，这里炸了
【数论】非递归扩展欧几里得定理/Exgcd-CSDN博客
2024-8-19 ·最后更新时间：2024-8-20
- 发现有纯迭代法扩展欧几里得定理没有讲 2024-8-20
本篇适用于像扩展Exgcd非递归版和OIwiki看不懂的同学，写这些也是因为Oiwiki上的太晦涩难懂了。
\Large\mathcal{1,Matrix representation}
首先我们我们们知道 a \mod b 就相当于 a-\lfloor\frac{a}{b}\rfloor b 这是很基础的东西不多赘述，同时也根据欧几里得定理可知 \gcd(a,b)=\gcd(b,a \mod b)=\gcd(b,a-\lfloor\frac{a}{b}\rfloor b) 于是我们由此产生了思考如果，换一种方式表达 \gcd(b,a \mod b)=\gcd(b,a-\lfloor\frac{a}{b}\rfloor b) 会发生什么呢？
我们不妨向矩阵的方向想一想，我们先把 b 和 a \mod b 放到向量一个 R^2 的向量中：
$$ \left[\begin{matrix}b \a \mod b \\end{matrix}\right] $$
那么根据我们原来对 a \mod b 的分析他是不是变成了：
\left[
\begin{matrix}
b \
a-\lfloor\frac{a}{b}\rfloor b \
\end{matrix}
\right]
等等？如果我们给他变成 2*2 的矩阵好像有一些奇妙的发现
\left[
\begin{matrix}
0 & b \
a & {\tiny -\lfloor\frac{a}{b}\rfloor b} \
\end{matrix}
\right]
欸？这个矩阵的每一列上都有相同的元素 a 或 b 所以，我们是不是可以把 a,b 单独提出来放到一个 R^2 的向量上？答案是可以的所以我们来转化一下，可以得到一个等式：
$$\left[\begin{matrix}b \a \mod b \\end{matrix}\right]=
\left[
\begin{matrix}
0 & 1 \
1 & -\lfloor\frac{a}{b}\rfloor b \
\end{matrix}
\right]
\left[\begin{matrix}a \b \\end{matrix}\right]
那么接下如果我们括号中的矩阵的乘积表示成一个独立的矩阵像：
那么
$$\left[\begin{matrix}\gcd(a,b) \0 \\end{matrix}\right]=
\left[
\begin{matrix}
x_1 & x_2 \
x_3 & x_4 \
\end{matrix}
\right]
\left[\begin{matrix}a \b \\end{matrix}\right]
V=
\left[
\begin{matrix}
x_1 & x_2 \
x_3 & x_4 \
\end{matrix}
\right]
\left[\begin{matrix}a \b \\end{matrix}\right]
V=
\left[
\begin{matrix}
ax_1+ax_2 \
ax_3+ax_4 \
\end{matrix}
\right]=
\left[\begin{matrix}\gcd(a,b) \0 \\end{matrix}\right]
\begin{cases}
ax+by=a\
ax’+by’=b
\end{cases}
⇒
\begin{cases}
ax’+by’=b\
a(x-\frac{a}{b}x’)+b(y-\frac{a}{b}y’)=a-\frac{a}{b}b
\end{cases}
\left[
\begin{matrix}
x & y & a\
x’ & y’ & b
\end{matrix}
\right]
\left[
\begin{matrix}
x’ & y’ & b\
x-\frac{a}{b}x’ & y-\frac{a}{b}y’ & a-\frac{a}{b}b
\end{matrix}
\right]