模运算

表示数 $n$ 和 $a$ 除以 $b$ 的余数相同。等价地说，$b$ 整除 $n - a$。读作“$n$ 与 $a$ 模 $b$ 同余”。

若 $a \equiv x \pmod{n}$ 且 $b \equiv y \pmod{n}$，则

（原书把第一个同余式印成了“$a = x \pmod n$”，意思是 $\equiv$。）

若 $a \equiv x \pmod{n}$，则对每个正整数 $m$，都有

要求一个很大的幂 $a^b$ 的末一位（或末几位）数字，先算出 $a^b$ 的前几个值，找出规律。余数最终一定会重复，所以这个规律可以推广到很大的 $b$。

若 $n$ 的质因数分解是 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，则

其中 $\varphi(n)$ 是不超过 $n$ 且与 $n$ 互质的正整数的个数。

步骤： 1. 求出 $n$ 的质因数分解。2. 对每个质数 $p_i$，写出 $1 - \frac{1}{p_i}$，并把它们相乘。3. 再把这个积乘以 $n$。

对 $n > 1$，

成立当且仅当 $\gcd(a, n) = 1$。

若 $p$ 是质数且 $p \nmid a$，则

（原书写的是“当且仅当 $p$ 是质数且 $\gcd(a, n) = 1$”。逆命题是错的：$561 = 3 \cdot 11 \cdot 17$ 不是质数，但对每个与 $561$ 互质的 $a$，都有 $a^{560} \equiv 1 \pmod{561}$。）

若 $ab \equiv 1 \pmod{n}$，则 $a$ 是 $b$（模 $n$）的模逆元，$b$ 也是 $a$ 的逆元。记作

$a$ 的逆元存在，当且仅当 $\gcd(a, n) = 1$。

对质数 $p$，

对非负整数 $n$，

在模运算中，把大的底数写成“小数 + 10 的倍数”：在 $(1 + 10)^{n}$ 中，从 $10^3$ 开始的每一项模 $1000$ 都是 0，所以 $(1 + 10)^n \equiv 1 + 10n + 100\binom{n}{2} \pmod{1000}$。

若正整数 $x$ 满足

其中 $n_i$ 两两互质，则 $x$ 模 $n_1 n_2 \cdots n_k$ 有唯一解。

解两个同余式组成的方程组，可以尝试检验，直到找到同时满足两个条件的数；也可以用代数方法：

1. 从 $n \equiv r_1 \pmod{m_1}$ 和 $n \equiv r_2 \pmod{m_2}$ 出发，其中 $m_1$ 与 $m_2$ 互质。
2. 把第一个改写成等式：$n = k m_1 + r_1$。
3. 代入第二个：$k m_1 + r_1 \equiv r_2 \pmod{m_2}$，所以 $k \equiv (r_2 - r_1)\cdot m_1^{-1} \pmod{m_2}$。
4. 用尝试检验求出 $m_1^{-1} \pmod{m_2}$。
5. 现在知道 $k \equiv k_0 \pmod{m_2}$；写成 $k = m_2 t + k_0$。
6. 代回 $n = k m_1 + r_1$。
7. 读出最后的同余式 $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$。

（原书第 3 步写成“$m_1 \equiv (r_2 - r_1)\cdot k^{-1}$”，第 5 步用了未定义的字母 $b, d$；这里已改正。）

对互质的 $m_1, m_2$，$n \equiv r_1 \pmod{m_1}$ 与 $n \equiv r_2 \pmod{m_2}$ 的解是

（原书漏掉了最后的模 $m_1 m_2$。）