同余

定义

费马小定理

定理内容：若 $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$ 互质。
可以用扩展欧几里德算法求出不定方程的一组解，方法如下：

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

代码实现如下：

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;
}