扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 ax+by=gcd(a,b)ax+by=\gcd(a,b) 的一组可行解。
扩展欧几里得算法
设 ax1+by1=gcd(a,b)ax_1+by_1=\gcd(a,b), bx2+(a mod b)y2=gcd(b,a mod b)bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)
由欧几里得定理可知：gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)
所以 ax1+by1=bx2+(a mod b)y2ax_1+by_1=bx_2+(a\bmod b)y_2
又因为 a mod b=a−(⌊ab⌋×b)a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)
所以 ax1+by1=bx2+(a−(⌊ab⌋×b))y2ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2
ax1+by1=ay2+bx2−⌊ab⌋×by2=ay2+b(x2−⌊ab⌋y2)ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)
因为 a=a,b=ba=a,b=b，所以 x1=y2,y1=x2−⌊ab⌋y2x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2
将 x2,y2x_2,y_2 不断代入递归求解直至 gcd\gcd（最大公约数，下同）为 00 递归 x=1,y=0x=1,y=0 回去求解。
扩展欧几里得算法的矩阵形式
(n1k1)→初等行变换(1uv0st)⇒un+vk=1⇒v‾⋅k‾=1‾∈Zn\begin{pmatrix}n&1&\\k&&1\end{pmatrix} \xrightarrow{\text{初等行变换}} \begin{pmatrix}1&u&v\\0&s&t\end{pmatrix} \Rightarrow un+vk=1 \Rightarrow\overline{v}\cdot\overline{k}=\overline{1}\in Z_n
示例
65x+83y=165x+83y=1
(651831)→(123−183−1411)\begin{pmatrix}65&1&\\83&&1\end{pmatrix} \rightarrow \begin{pmatrix}1&23&-18\\3&-14&11\end{pmatrix}
x=23,y=−18x=23,y=-18