同余

定义

费马小定理

定理内容：若 \(p\) 是质数，则有：$ \forall a \in Z, a ^ p \equiv a \pmod p$。
推论：当 \(\gcd(a,p) = 1\) 时，\(a ^ {p - 1} \equiv 1 \pmod p\)。

裴蜀定理及拓展欧几里德算法

裴蜀定理：\(\forall a,b \in Z\)，一元二次不定方程 \(ax + by = \gcd(a,b)\) 有整数解。
逆定理：若 \(d\) 是 \(a,b\) 的公约数，且 \(\exist x,y \in Z, ax + by = d\)，则 \(d = \gcd(a,b)\)，特殊的，\(d = 1\) 时 \(a,b\) 互质。
可以用扩展欧几里德算法求出不定方程的一组解，方法如下：

1. 根据欧几里德算法，\(ax + by = d = \gcd(a, b) = \gcd (b, a \bmod b) = d'\)，设 \(x'b + y'(a - b \lfloor \frac{a}{b} \rfloor) = d'\)
2. 当 \(a' | b'\) 即 \(a \bmod b = 0\) 时，欧几里德定理求出 \(\gcd(a,b) = d' = b\)，则显然 \(x'=1,y'=0\) 是一组合法解, \(1 \times b' + 0 \times 0 = b'\)。
3. 当 \(x'\) 与 \(y'\) 已求出时，\(d' = x'b + y'(a - b \lfloor \frac{a}{b} \rfloor) = ay' + b(x' - \lfloor \frac{a}{b} \rfloor y') = d\)，则可求出 \(x = y', y = x' - \lfloor \frac{a}{b} \rfloor y'\)。
4. 递归即可求出原方程的一组解。

代码实现如下：

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

求解一元二次不定方程

设关于 \(x,y\) 的方程为：\(ax + by = c\), \(\gcd(a, b) = d\)

1. \(d \nmid c\)时，此时方程无解。
2. 设 \(t = c / d\)，则先求出 \(ax' + by' = d\) 的解 \(x', y'\)，对等式两边乘以 \(t\)，求出 \(x = tx', y = ty'\)。

容易发现，若 \(x,y\) 是原方程的一组解，则 \(x = x + \frac{b}{d}, y = y - \frac{b}{d}\) 也是原方程的一组解。