同余

同余的概念及其基本性质

同余的方法是德国数学家高斯在 1800 年前后创立的。同余是数论中最基本的概念，它是整除性理论的拓广与发展

同余式提供了一种描述整除性质的简便方式。事实上，同余式使得整除性理论非常类似于方程理论

定义 1.1：给定一个正整数 $m$，把它叫做模，如果用 $m$ 去除任意两个整数 $a$ 与 $b$ 所得的余数相同，则称 $a, b$ 关于模 $m$ 同余，记作 $a \equiv b\pmod m$；否则称 $a, b$ 关于模 $m$ 不同余。记作 $a \not \equiv b \pmod m$

定理 1.1: $a \equiv b \pmod m$ 的充要条件是 $m|(a - b)$ 或 $a = b + mk$

证：(必要性)设 $a \equiv b \pmod m$，即 $a = mq_1 + r, b = mq_2 + r(0 \le r < m, q_1, q_2$ 为整数)，则 $a - b = m(q_1 - q_2)$，故 $m \mid (a - b)$
(充分性)当 $m \mid (a - b)$ 时，设 $a - b = mk$($k$ 为整数)。若 $b = mq + r$，则 $a = b + mk = m(q + k) + r$，因此 $a \equiv b \pmod m$

定义 1.2: 设 $a, b$ 为整数，$m$ 为正整数，若 $m | (a - b)$，则称 $a, b$ 关于模 $m$ 同余，若 $m \not \mid (a - b)$，则称 $a, b$ 关于模 $m$ 不同余

定理 1.2: 若 $a_1 \equiv b_1 \pmod m, a_2 \equiv b_2 \pmod m$，则：
$(1) a_1 \pm a_2 \equiv b_1 \pm b_2 \pmod m$
$(2) a_1 a_2 \equiv b_1 b_2 \pmod m$

证：由假设，知 $m \mid (a_1 - b_1), m \mid (a_2 - b_2)$，所以：
$(1) m \mid [(a_1 - b_1)\pm (a_2 - b_2)]$，即 $m \mid [ (a_1 \pm a_2) - (b_1 \pm b_2) ]$，故 $a_1 \pm a_2 \equiv b_1 \pm b_2 \pmod m$
$(2) m \mid [a_2(a_1 - b_1) + b_1(a_2 - b_2)]$，即 $m \mid (a_1 a_2 - b_1 b_2)$，故 $a_1 a_2 \equiv b_1 b_2 \pmod m$

推论1: 若 $a \equiv b \pmod m$，$k$ 为整数，则 $a \pm k \equiv b \pm k \pmod m$
推论2: 若 $a \equiv b \pmod m$，$c$ 为整数，则 $ac \equiv bc \pmod m$
推论3: 若 $a \equiv b \pmod m$，$n$ 为正整数，则 $a^n \equiv b^n \pmod m$
推论4: 设 $p(x)$ 是任一整系数多项式。若 $a \equiv b \pmod m$，则 $p(a) \equiv p(b) \pmod m$
推论5: 设 $f(x) = \sum_{i = 0}^n a_i x^i, g(x) = \sum_{i = 0}^n b_i x^i$ 是两个系数多项式。若 $a_i \equiv b_i \pmod m(i = 1, 2, \cdots, n)$，则 $f(x) \equiv g(x) \pmod m$

定理 1.3: 若 $a_1 a_2 \equiv b_1b_2 \pmod m, a_2 \equiv b_2 \pmod m$，且 $(a_2, m) = 1$，则 $a_1 \equiv b_1 \pmod m$

证：利用等式 $(a_1 - b_1)a_2 + b_1(a_2 - b_2) = a_1 a_2 - b_1b_2$。由假设，知 $m \mid (a_1a_2 - b_1b_2), m \mid (a_2 - b_2)$，故 $m \mid (a_1 - b_1)a_2$。又由 $(a_2, m) = 1$，得 $m \mid (a_1 - b_1)$，即 $a_1 \equiv b_1 \pmod m$

推论：若 $ac \equiv bc \pmod m$，且 $(c, m) = 1$，则 $a \equiv b \pmod m$
该推论表明，若同余式两边由公因数与模互素，则可将其约去

整数性判别法

利用同余的性质，可以很方便地推导出一些众所周知的整数性判别法

被 $2^m$(或 $5^m$)整除的判别法
定理 1.4: 一个整数 $N$ 能被 $2^m$(或 $5^m$)整除的充要条件时，它的最后 $m$ 位数能被 $2^m$(或 $5^m$)整除
证： 设 $N = \overline {a_n a_{n-1} \cdots a_m a_{m - 1} \cdots a_1 a_0}$，则 $N \equiv \overline {a_{m - 1} \cdots a_1 a_0} \pmod {10^m}$
即 $N \equiv \overline {a_{m - 1} \cdots a_1 a_0} \pmod {2^m}$，或 $N \equiv \overline {a_{m - 1} \cdots a_1 a_0} \pmod {5^m}$
故当且仅当 $2^m \mid \overline {a_{m - 1} \cdots a_1 a_0}$ 时，$2^m \mid N$
同样，当且仅当 $5^m \mid \overline {a_{m - 1} \cdots a_1 a_0}$ 时，$5^m \mid N$

被 $3$(或 $9$)整除的判别法
定理 1.5: 一个整数 $N$ 能被 $3$(或 $9$)整除的充要条件是，它的十进制数码的和能被 $3$(或 $9$)整除
证： 设 $N = \overline {a_n a_{n - 1} \cdots a_1 a_0} = a_n \cdot 10^n + a_{n - 1} \cdot 10^{n - 1} + \cdots + a_1 \cdot 10 + a_0$
这里，$0 \le a_i < 10$，$a_i$ 为整数，$i = 0, 1, \cdots, n - 1, a_n \not = 0$
因为 $10 \equiv 1 \pmod 3$，所以 $N \equiv a_n \cdot 1^n + a_{n - 1} \cdot 1^{n - 1} + \cdots + a_1 \cdot 1 + a_0 \equiv a_n + a_{n - 1} + \cdots + a_1 + a_0 \pmod 3$
因而，当且仅当 $3 \mid \sum_{i = 0}^n a_i$ 时，$3 \mid N$
又 $10 \equiv 1 \pmod 9$，同理可证，当且仅当 $9 \mid \sum_{i = 0}^n a_i$ 时，$9 \mid N$

一次同余式

代数的一个主要问题是解方程，这里讨论类似的问题，求同余式的解

定义 1：若用 $f(x)$ 表示多项式 $a_n x^n + a_{n-1}x^{n-1} + \cdots + a_0$，其中 $a_i$ 是整数，又设 $m$ 是一个正整数，则

$$f(x) \equiv 0 \pmod m \tag{1}$$

叫模 $m$ 的同余式。若 $a_n \not \equiv 0 \pmod m$，则 $n$ 叫做 $(1)$ 的次数

定义 2：如果 $a, b$ 都是整数，而 $m$ 是一个正整数，当 $a \not \equiv 0 \pmod m$ 时，我们把

$$ax + b \equiv 0 \pmod m \tag{2}$$

叫做模 $m$ 的一次同余式

定理 1：如果 $c$ 是使 $(2)$ 式成立的一个整数，即 $ac + b \equiv 0 \pmod m$，则满足 $x \equiv c \pmod m$ 的一切整数 $x$ 都能使 $(2)$ 式成立

证： 由 $x \equiv c \pmod m$，得到 $m \mid (x - c)$，即 $x - c = mn$，其中 $n$ 是一个整数。由 $x = mn + c$ 和 $ac + b \equiv 0 \pmod m$，得到 $ax + b \equiv a(mn + c) + b \equiv ac + b \equiv 0 \pmod m$

定义 3： 如果 $c$ 是使 $ax + b \equiv 0 \pmod m$ 成立的一个整数，则 $x \equiv c \pmod m$ 叫做 $(2)$ 式的一个解。这就是说今后我们把适合 $(2)$ 式对模 $m$ 相互同余的一切整数叫做 $(2)$ 式的一个解

定理 2：当 $a, m$ 的最大公因数 $(a, m)$ 不能整除 $b$(即 $(a, m) \not \mid b$)时，则一次同余式

$ax + b \equiv 0 \pmod m, a \not \equiv 0 \pmod m$

没有整数解

证：设存在有一个整数 $c$，使得 $ac + b \equiv 0 \pmod m$，即 $m \mid (ac + b)$，故存在有一个整数 $n$ 使得 $ac + b = mn$，而得

$$ac - mn = b \tag{3}$$

设 $(a, m) = l$，则有 $a = ld, m = le$，其中 $d$ 和 $e$ 都是整数。将它们代进 $(3)$ 式，得到

$$b = ac - mn = cld - len = l(cd - en) \tag{4}$$

由 $cd - en$ 是整数，得到 $l \mid b$，但是这和题设 $(a, m) \not \mid b$ 发生矛盾

中国剩余定理(孙子定理)

现在讨论如何解下面的同余式组

$$\begin{cases} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \\ \vdots \\ x \equiv b_k \pmod {m_k} \end{cases} \tag{1}$$

在我国古代的《孙子算经》(纪元前后)里已经提出了这种形式的问题，并且很好地解决了它
《孙子算经》里所提出的问题之一如下：
“今有物不知其数，三三数之胜二，五五数之剩三，七七数之剩二，问物几何？”“答曰二十三”(译：有一堆东西不知道有多少个，用三来除这堆东西的个数时所得到的余数是二，用五来除这堆东西的个数时所得到的余数是三，用七来除这堆东西的个数时所得到的余数是二，问这堆东西共有多少个？答案是二十三个)

把这个问题的提法用同余式的式子来表达，它可以被写成下面的形式：
解同余式组(设 $x$ 是所求物数)

$$\begin{cases} x \equiv 2 \pmod {3} \\ x \equiv 3 \pmod {5} \\ x \equiv 2 \pmod {7} \end{cases}$$

定理 1(孙子定理)：设 $m_1, m_2, \cdots, m_k$ 是 $k$ 个两两互素的正整数，$m = m_1m_2 \cdots m_k, m = m_i M_i(i = 1, 2, \cdots, k)$，则同余式组 $(1)$ 的解是：

$$x \equiv M_1^{'} M_1 b_1 + M_2^{'} M_2 b_2 + \cdots + M_k^{'} M_k b_k \pmod m \tag{2}$$

其中

$$M_i^{'}M_i \equiv 1 \pmod {m_i} (i = 1, 2, \cdots, k)$$

证：因为 $m_1, m_2, \cdots, m_k$ 是两两互素的，所以当 $i \not = j$ 时，则有 $(m_i, m_j) = 1$。由于 $M_i = \frac{m}{m_i}$，得到 $(M_i, m_i) = 1$
所以 $(M_1, m_1) = (M_2, m_2) = \cdots = (M_k, m_k) = 1$
由 $(M_1, m_1) = 1$，我们知道存在有两个整数 $M_1^{'}, n_1$ 使得 $M_1 M_1^{'} + m_1 n_1 = 1$，所以存在有一个 $M_1^{'}$ 使得 $M_1^{'} M_1 \equiv 1 \pmod {m_1}$ 成立
用同样的方法知道对于每一个 $M_i$，一定存在有一个正整数 $M_i^{'}$ 使得

$$M_i^{'}M_i \equiv 1 \pmod {m_i} \tag{3}$$

另一方面，当 $i \not = j$ 时，则由 $(m_i, m_j) = 1$ 和 $M_j = \frac{M}{m_j}$ 得到 $m_i \mid M_j$，所以有

$$b_j M_j^{'} M_j \equiv 0 \pmod {m_i} \tag{4}$$

由 $(3)$ 式和 $(4)$ 式我们有

$$M_1^{'} M_1 b_1 + M_2^{'} M_2 b_2 + \cdots + M_k^{'} M_k b_k \equiv b_i \pmod {m_i} \tag{5}$$

由 $m_1, m_2, \cdots, m_k$ 是两两互素的和 $(5)$ 式，知道 $(2)$ 式是满足 $(1)$ 式的正整数解

可以使用扩展欧几里得算法求出每一个 $M_i^{'}$ 的最小正整数解，最后就可以得到同余式组 $(1)$ 的一个最小正整数解

51Nod 1079 中国剩余定理

#include <cstdio>
int k, b[15], m[15];
long long product = 1, x, y, ans;
void ext_gcd(long long a, long long b) {
    if (b == 0) { x = 1; y = 0; return; }
    ext_gcd(b, a % b); long long t = x; x = y; y = t - a / b * y;
}
int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) { 
        scanf("%d %d", &m[i], &b[i]); product *= m[i];
    }
    for (int i = 1; i <= k; ++i) {
        long long tmp = product / m[i]; ext_gcd(tmp, m[i]);
        x %= m[i]; if (x < 0) { x += m[i]; }
        ans += x * tmp * b[i]; ans %= product;
    }
    printf("%lld\n", ans);
    return 0;
}

剩余类及完全剩余系

有了同余的概念，就可以把余数相同的整数放在一起考虑，这就产生了“剩余类”的概念，同时也就引出了模 $m$ 的完全剩余系的概念

定义1：设 $m$ 是一个给定的正整数，我们把被模 $m$ 除所得的余数为 $r$ 的整数归于一类，记作

$$S_r = \{mq + r \mid q \text{为整数}, 0 \le r \le m - 1\}$$

所形成的 $m$ 类：$S_0, S_1, \cdots, S_{m - 1}$，称为模 $m$ 的剩余类

例如，以 $2$ 为模，可把全体整数分为奇数、偶数两大类
不难看出，$a, b$ 关于模 $m$ 属于同一类当且仅当 $a, b$ 关于模 $m$ 同余

定义2: 从模 $m$ 的每一个剩余类中各取一个数作为代表所得到的 $m$ 个数，称为模 $m$ 的一个完全剩余系

由于模 $m$ 的完全剩余系具有多种多样的形式，所以我们给出如下的定义：

定义3: $0, 1, \cdots, m - 1$ 这 $m$ 个整数称为模 $m$ 的非负最小完全剩余系

完全剩余系的基本性质

模 $m$ 的完全剩余系具有下列基本性质

定理1: 若 $a_1, a_2, \cdots, a_m$ 是关于模 $m$ 的两两不互余的 $m$ 个整数，则这些整数就构成了模 $m$ 的完全剩余系

定理2: 设 $m$ 是正整数，$(a, m) = 1, b$ 是任意整数，若 $x$ 通过模 $m$ 的一个完全剩余系，则 $ax + b$ 也通过模 $m$ 的完全剩余系
证：设 $a_0, a_1, \cdots, a_{m - 1}$ 是模 $m$ 的一个完全剩余系。只需证明 $m$ 个整数 $aa_0 + b, aa_1 + b, \cdots, aa_{m - 1} + b$ 关于模 $m$ 两两不同余即可
用反证法。假定 $aa_i + b \equiv aa_j + b \pmod m (i, j = 0, 1, \cdots, m - 1, i \not = j)$，那么有 $aa_i \equiv aa_j \pmod m$。因 $(a, m) = 1$，故 $a_i \equiv a_j \pmod m$。这与 $a_0, a_1, \cdots a_{m - 1}$ 是完全剩余系的假设矛盾，因此结论成立

定理3: 设 $m_1, m_2$ 是互素的两个正整数，若 $x_1, x_2$ 分别通过模 $m_1, m_2$ 的完全剩余系，则 $m_2 x_1 + m_1x_2$ 通过模 $m_1, m_2$ 的完全剩余系

证：由假设，知 $x_1, x_2$ 分别通过 $m_1, m_2$ 个整数，因此 $m_2 x_1 + m_1x_2$ 通过 $m_1m_2$ 个整数。只需证明这 $m_1 m_2$ 个整数关于模 $m_1m_2$ 两两不同余即可
假定 $m_2x_1^{'} + m_1x_2^{'} \equiv m_2x_1^{''} + m_1 x_2^{''} \pmod {m_1m_2}$。这里 $x_1^{'}, x_1^{''}$ 是 $x_1$ 所通过的完全剩余系中的整数，而 $x_2^{'}, x_2^{''}$ 是 $x_2$ 所通过的完全剩余系中的整数，则有

$$m_2x_1^{'} \equiv m_2 x_1^{''} \pmod {m_1}, m_1x_2^{'} \equiv m_1 x_2^{''} \pmod {m_2}$$

由 $(m_1, m_2) = 1$，得 $x_1^{'} \equiv x_1^{''} \pmod {m_1}, x_2^{'} \equiv x_2^{''} \pmod {m_2}$。但 $x_1^{'}, x_1^{''}$ 是模 $m_1$ 的一个完全剩余系中的整数，$x_2^{'}, x_2^{''}$ 是模 $m_2$ 的一个完全剩余系中的整数，所以 $x_1^{'} = x_1^{''}, x_2^{'} = x_2^{''}$。这表明，如果 $x_1^{'}$ 与 $x_1^{''}$、$x_2^{'}$ 与 $x_2^{''}$ 不全相同，则 $m_2 x_1^{'} + m_1x_2^{'} \not \equiv m_2 x_1^{''} + m_1 x_2^{''} \pmod {m_1m_2}$，因此结论成立

缩系和欧拉函数

定义1：欧拉函数 $\phi(m)$ 表示不超过正整数 $m$ 且与 $m$ 互素的正整数的个数。

例如，不超过 $10$ 且与 $10$ 互素的正整数有 $1, 3, 7, 9$ 四个数，故 $\phi(10) = 4$
显然，$\phi(1) = 1$。若 $p$ 为素数，则 $\phi(p) = p - 1$

定义2: 如果一个模 $m$ 的剩余类里面的数与 $m$ 互素(显然，只要有一个与 $m$ 互素，其余的均与 $m$ 互素)，就把它叫做一个与模 $m$ 互素的剩余类。在与模 $m$ 互素的全部剩余类中，各任取一数所组成的集叫做缩系

定理1: 与模 $m$ 互素的剩余类的个数是 $\phi(m)$

定理2: 若 $a_1, a_2, \cdots, a_{\phi(m)}$ 是 $\phi(m)$ 个与 $m$ 互素的整数，则 $a_1, a_2, \cdots, a_{\phi(m)}$ 是模 $m$ 的一个缩系的充分必要条件是它们两两对模 $m$ 不同余

定理3: 若 $(a, m) = 1$，$x$ 通过模 $m$ 的缩系，则 $ax$ 也通过模 $m$ 的缩系
证：$ax$ 通过 $\phi(m)$ 个整数，由于 $(a, m) = 1, (x, m) = 1$，故 $(ax, m) = 1$，若 $ax_1 \equiv ax_2 \pmod m$，可得 $x_1 \equiv x_2 \pmod m$，这与原假设矛盾，故由定理 $2$，定理得证

定理4(欧拉定理)：设 $m$ 是大于 $1$ 的整数，$(a, m) = 1$，则

$$a^{\phi(m)} \equiv 1 \pmod m$$

证：设 $r_1, r_2, \cdots, r_{\phi(m)}$ 是模 $m$ 的缩系，则由定理 $3$，$ar_1, ar_2, \cdots, ar_{\phi(m)}$ 也是模 $m$ 的缩系，故 $(ar_1)(ar_2)\cdots(ar_{\phi(m)}) \equiv r_1r_2 \cdots r_{\phi(m)} \pmod m$
即 $a^{\phi(m)}r_1r_2\cdots r_{\phi(m)} \equiv r_1r_2 \cdots r_{\phi(m)} \pmod m$。由 $(r_i, m) = 1, i = 1, 2, \cdots, \phi(m)$，得 $(r_1r_2\cdots r_{\phi(m)}, m) = 1$，故有 $a^{\phi(m)} \equiv 1 \pmod m$

由定理 $4$ 立刻推出定理 $5$

定理5(费马小定理): 若 $p$ 是素数，$p \not \mid a$ 则

$$a^{p - 1} \equiv 1 \pmod p$$

证：由于 $p$ 是一个素数，所以 $\phi(p) = p - 1$。又 $p \not \mid a$，故 $(a, p) = 1$，因此在定理 $4$ 中取 $m = p$，就有 $a^{p - 1} \equiv 1 \pmod p$

推论：若 $p$ 为素数，则对一切整数 $a$，有

$$a^p \equiv a \pmod p$$

证：若 $(a, p) = 1$，由定理 $5$，得 $a^{p - 1} \equiv 1 \pmod p$，所以 $a^p \equiv a \pmod p$
若 $(a, p) = p$，即 $p \mid a$，此时显然有 $a^p \equiv 0 \equiv a \pmod p$

$\phi(m)$ 的积性

定理6: 若 $m_1, m_2$ 是两个互素的正整数，$x_1, x_2$ 分别通过模 $m_1, m_2$ 的缩系，则 $m_2x_1 + m_1x_2$ 通过模 $m_1 m_2$ 的缩系，则 $m_x x_1 + m_1 x_2$ 通过模 $m_1m_2$ 的缩系

证：(1) 若 $(x_1, m_1) = 1, (x_2, m_2) = 1$，则由 $(m_1, m_2) = 1$ 得 $(m_2x_1, m_1) = (m_1x_2, m_2) = 1$，所以 $(m_2 x_1 + m_1x_2, m_1) = (m_2x_1 + m_1x_2, m_2) = 1$，故 $(m_2 x_1 + m_1x_2, m_1 m_2) = 1$
(2) 反之，凡与 $m_1m_2$ 互素之 $a$ 必与 $m_2 x_1 + m_1 x_2$ 中之一同余。对任一整数 $a$ 必有必有 $x_1, x_2$ 使 $a \equiv m_2x_1 + m_1x_2 \pmod {m_1m_2}$，所以只需说明当 $(a, m_1m_2) = 1$ 时，$(x_1, m_1) = (x_2, m_2) - 1$ 就够了，今若 $(x_1, m_1) = d > 1$，则 $(a, m_1) = (m_2x_1 + m_1x_2, m_1) = (m_2x_1, m_1) = (x_1, m_1) = d$，此与 $(a, m_1m_2) = 1$ 矛盾。同样可证 $(x_2, m_2) = 1$
(3) $m_2x_1 + m_1x_2$ 中任两个对模 $m_1m_2$ 均不同余
综上所述，定理得证

由这一定理即可推出下面两个定理

定理7：若 $(m_1, m_2) = 1$，则 $\phi(m_1m_2) = \phi(m_1)\phi(m_2)$

定理8：设 $n$ 的标准分解式为 $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$，则

$$\phi(n) = n\frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}$$

证：(1) 由定理 $7$ 即得 $\phi(n) = \phi(p_1^{\alpha_1})\phi(p_2^{\alpha_2})\cdots \phi(p_k^{\alpha_k})$
(2) 今证明 $\phi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}$。由 $\phi(n)$ 的定义知 $\phi(p^{\alpha})$ 等于从 $p^{\alpha}$ 减去 $1, \cdots, p^{\alpha}$ 中与 $p^{\alpha}$ 不互素(即与 $p$ 不互素)的数的个数。由于 $p$ 是素数，故 $\phi(p^{\alpha})$ 等于从 $p^{\alpha}$ 减去 $1, \cdots, p^{\alpha}$ 中被 $p$ 整除的数的个数 $\frac{p^{\alpha}}{p} = p^{\alpha - 1}$，故 $\phi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}$ (3) 由(1),(2)即得 $\phi(n) = (p_1^{\alpha_1} - p_1^{\alpha_1 - 1})(p_2^{\alpha_2} - p_2^{\alpha_2 - 1})\cdots(p_k^{\alpha_k} - p_k^{\alpha_k - 1}) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k}) = n\frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}$
证完