乘法逆元

前置知识

二元线性丢番图方程

形如 \(ax + by = c\) 的方程称为二元线性丢番图方程，其中 \(a, b, c \in \Z\).

在后文中如无特殊说明默认一个二元线性丢番图方程的系数均为整数.

裴蜀定理

对于一个二元线性丢番图方程 \(ax + by = c\)，记 \(d = \gcd(a, b)\)，其存在整数解的充要条件是 \(d \mid c\).

如果存在一组整数解 \((x_0, y_0)\)，则所有解可以表示为 \(x = x_0 + \dfrac{b}{d} \cdot k, y = y_0 - \dfrac{a}{d} \cdot k\)，其中 \(k \in \Z\).

同余与同余式

\(\forall a, b \in \Z, m \in \N_+\)，若 \(m \mid (a - b)\)，则称 \(a\) 和 \(b\) 关于 \(m\) 同余，记作 \(a \equiv b \pmod m\).

一元线性同余方程

若 \(x\) 是未知数，给定 \(a, b, m\)，且 \(a, b, m \in \Z\)，求整数 \(x\)，满足 \(ax \equiv b \pmod m\).

欧几里得算法（辗转相除法）

\(\forall a, b \in \N_+\)，有 \(\gcd(a,b) = \gcd(b, a \bmod b)\).

扩展欧几里得算法

求二元线性丢番图方程的整数解

对于一个二元线性丢番图方程 \(ax + by = c\)，根据裴蜀定理，当且仅当 \(\gcd(a, b) | c\) 时，方程有整数解.

故可以先求

\[ax + by = \gcd(a, b) \]

的解，再在等式两边乘以 \(\dfrac {c}{\gcd(a, b)}\)，即可得到原方程的解.

由欧几里得算法我们可以得到

\[\gcd(b, a \bmod b) = \gcd(a, b) \]

那么我们可以再列出一个二元线性丢番图方程

\[bx_1 + (a \bmod b)y_1 = \gcd(b, a \bmod b) \]

整理一下

\[\begin{cases} \gcd(b, a \bmod b) = \gcd(a, b)\\ ax + by = \gcd(a, b)\\ bx_1 + (a \bmod b)y_1 = \gcd(b, a \bmod b)\\ \end{cases} \]

对于欧几里得算法的流程而言，求解 \(\gcd(b, a \bmod b)\) 是求解 \(\gcd(a, b)\) 的下一层状态，或者说是子问题，在欧几里得算法回溯时我们需要根据 \(bx_1 + (a \bmod b)y_1 = \gcd(b, a \bmod b)\) 的解来推导 \(ax + by = \gcd(a, b)\) 的解，接下来我们需要探究两方程解的关系.

因为有

\[\gcd(b, a \bmod b) = \gcd(a, b) \]

所以

\[bx_1 + (a \bmod b)y_1 = ax + by \]

又有

\[a \bmod b = a - \lfloor \dfrac{a}{b} \rfloor \cdot b \]

将其带入等式中可得

\[bx_1 + \left(a - \lfloor \dfrac{a}{b} \rfloor \cdot b \right)y_1 = ax + by \]

整理等式

\[ay_1 + bx_1 - \lfloor \dfrac{a}{b} \rfloor \cdot by_1 = ax + by \]

\[ay_1 + b\left(x_1 - \lfloor \dfrac{a}{b} \rfloor y_1\right) = ax + by \]

将等式左右两项分别对应可得

\[x = y_1, y = x_1 - \lfloor \dfrac{a}{b} \rfloor y_1 \]

在欧几里得算法的最终状态我们可以得到 \(a = \gcd(a, b), b = 0\)，此时方程 \(ax + by = \gcd(a, b)\) 的解显然是 \(x = 1, y = 0\). 由于欧几里得算法是递归的，故我们可以通过 \(x = 1, y = 0\) 以及刚才得出的结论逆推.

此时我们求的是 \(ax + by = \gcd(a, b)\) 的一组解，我们可以在等式两边同时乘以 \(\dfrac {c}{\gcd(a, b)}\)，就可以求得 \(ax + by = c\) 的解.

显然这只是方程的一组特解，记刚才所得的特解为 \(x_0, y_0\)，那么方程的通解为 \(x = x_0 + \dfrac{b}{\gcd(a, b)} \cdot k, y = y_0 - \dfrac{a}{\gcd(a, b)} \cdot k, k \in \Z\).

代码如下.

int Exgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1;	y = 0;
		return a;
	}
	int ans = Exgcd(b, a % b, x, y);
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
	return ans;
}