# 同余的基本性质

# 基本概念

设 $m$ 是正整数，$a,b$ 为两个整数，如果 $a-b$ 是 $m$ 的倍数，那么称 $a$ 和 $b$ 关于 $m$ 同余，记作 $a\equiv b\pmod m$

• 同余是等价关系

证明题需要充分利用 $a,b$ 关于 $m$ 同余 $\Leftrightarrow$ $m|a - b$

模 m 剩余类

设 $m$ 是正整数，全体整数按照模 $m$ 同余划分成 $m$ 个不同的等价类。整数 $a$ 所在的剩余类记为 $\bar a$，整数 $x$ 属于剩余类 $\bar a$ 当且仅当 $x\equiv a\pmod m$

• 如果 $a$ 和 $m$ 互素， 剩余类中 $\bar a$ 中的每个元素都和 $m$ 互素

  证明

  当 $a\equiv b\pmod m$ 时，$a=mq+b$

  $\Rightarrow (a,m)=(b,m)$

  $\Rightarrow$ 如果 $a$ 与 $m$ 互素，那么剩余类中所有元素和 $m$ 互素

模 m 完全剩余系

从每个剩余类取出一个整数形成 $m$ 元集合

证明一个系不是模 $m$ 完全剩余系 $\Rightarrow$ 证明系中有两个元素模 $m$ 相等

模 m 简化剩余类

如果整数 $a$ 与 $m$ 互素，那么 $a$ 所在的剩余类 $\bar a$ 称为模 $m$ 简化剩余类

模 m​ 简化剩余系

从每个简化剩余类中取出一个整数形成的集合称为模 $m$ 简化剩余系

欧拉函数

在整数 $1,2,3,...,m$ 中，所有和 $m$ 互素的整数的个数称为 $m$ 的欧拉函数，记作 $\varphi (m)$

• 注意整数不含 $0$
• 当 $p$ 是素数时， $\varphi(p) = p- 1$
• 欧拉函数 即 简化剩余系的个数

# 运算的性质

设 $m, n$ 为正整数，模 $m$ 的剩余类 $\bar a$ 可以拆分成 $n$ 个模 $mn$ 的剩余类， $\bar a$$, \overline{a+m}$$,...,$$\overline{\text{a+m(n-1)}}$

设 $m, n$ 为正整数，若 $a\equiv b\pmod {mn}$，则 $a\equiv b\pmod m,a\equiv b\pmod n$（逆定理不成立）

设 $m, n$ 为正整数，若 $a\equiv b\pmod m,a\equiv b\pmod n$，则 $a \equiv b\ (mod\ {[m,n]})$

模的运算性质：

若 $a\equiv b\pmod m$，则 $a+b\equiv b+c\pmod m$

若 $a\equiv b\pmod m$，$k$ 为整数，则 $ak\equiv bk\pmod m$

若 $ak\equiv bk\pmod m$，$k$ 为整数，且 $\Large{(k,m)=1}$，则 $a\equiv b\pmod m$

若 $a\equiv b\pmod m$，那么 $a/c\equiv b/c\pmod {\frac{m}{(m,c)}}$

若 $a\equiv b\pmod m$，$k$ 为正整数，则 $ak\equiv bk\pmod mk$，反之亦然

若$a\equiv b\pmod m$，$f(x)$ 为任一整系数多项式，则 $f(a)\equiv f(b)\pmod m$

若 $a_1\equiv a_2\pmod m,b_1\equiv b_2\pmod m$，则$a_1+b_1\equiv a_2+b_2\pmod m,a_1b_2\equiv a_2b_2\pmod m$

1
2
3
4

  123 -- ①
× 258 -- ②
----------
  31734 -- ③

# 抽象的性质

设 $m$ 是正整数，若 $(a,m)=1$， 则

• 当 $x$ 遍历模 $m$ 的一个完全剩余系时，对于任意整数 $b$ ， $ax+b$ 遍历模 $m$ 的一个完全剩余系
• 当 $x$ 遍历模$m$ 的一个简化剩余系时， $ax$ 遍历模 $m$ 的一个简化剩余系

设 $m,n$ 为正整数，$(m,n)=1$，则

• 当 $x$ 遍历模 $n$ 的一个完全剩余系时， $y$ 遍历模 $m$ 的一个完全剩余系时， $mx+ny$ 遍历模 $mn$ 的一个完全剩余系

• 当 $x$ 遍历模 $n$ 的一个简化剩余系时， $y$ 遍历模 $m$ 的一个简化剩余系时， $mx+ny$ 遍历模 $mn$ 的一个简化剩余系，

  即

  $$\varphi (mn) = \varphi(m)\varphi(n)$$

习题：

# 欧拉定理和费马小定理

设 $p$ 为素数， $e$ 为正整数，则 $\varphi(p^e)=p^e-p^{\text{e-1}}$

设 $m$ 为正整数，其标准分解式 $m=\prod\limits_{i=1}^sp_i^{\alpha_i}$，则 $\varphi(m)=m\prod\limits_{i=1}^s (1-\frac{1}{p_i})$

# 欧拉定理

设 $m$ 为正整数， $\Large (a,m)=1$，那么 $a^{\varphi(m)}\equiv 1\pmod m$

# 费马小定理

设 $p$ 为素数，那么对于任意整数 $a$， $a^p\equiv a\pmod p$

# 扩展欧拉定理

设 $p$ 为素数， $k\geq 0, \Large r\geq t$，那么对于任意整数 $a$,

$$a^{k\varphi(p^t)+r}\equiv a^r(\ mod\ p^i)$$

# 模重复平方法

空间换时间

习题：

# 同余式

设 $f(x)=\sum\limits_{i=0}^n a_ix^i$ 是一个整系数多项式， $m$ 为正整数，那么称 $f(x)\equiv 0\pmod m$ 为模 $m$ 同余式

• 如果 $a_n\not\equiv 0\pmod m$，则称同余式的次数是 $n$

• 如果整数 $a$ 满足 $f(a)\equiv 0\pmod m$，称 $a$ 为同余式的解

若 $b\equiv a\pmod m$，则 $f(a)\equiv f(b)\equiv 0\pmod m$，所以 $b$ 也是同余式的解

• 一般地，若 $a$ 是同余式的解，那么模 $m$ 剩余类 $\bar a$ 中的所有整数都是同余式的解，记作 $x\equiv a\pmod m$

模 $m$ 的完全剩余系中同余式的解的个数成为同余式的解数

# 解同余式

设 $m$ 为正整数，同余式 $ax\equiv b\pmod m$ 有解的充要条件是 $(a,m)|b$

在有解的情况下，解数为 $(a,m)$

若 $x = x_0$ 是同余式的一个特解，那么同余式的所有解可以表示为

$$x\equiv x_0+\frac{m}{(a,m)}t\pmod m$$

# 逆元

设 $m$ 为正整数，$(a,m)=1$，同余式 $ax\equiv 1\pmod m$ 的解称为 $a$ 模 $m$ 的逆元，记作 $x\equiv a^{-1}\pmod m$

设 $m$ 为正整数，$(a,m)=1$，那么 $a^{\varphi(m)-1}$ 是 $a$ 模 $m$ 的逆元

Wilson 定理：设 $p$ 是素数，那么 $(p-1)!\equiv -1\pmod p$

# 中国剩余定理

设 $m_1,m_2,...,m_s$ 为两两互素的正整数，$b_1,b_2,...,b_s$ 为任意整数，那么同余式组

$$\left\{\begin{matrix} x\equiv b_1\pmod {m_1} \\ x\equiv b_2\pmod{m_2} \\ ...\\ x\equiv b_s\pmod{m_s} \end{matrix}\right.$$

模 $M=m_1m_2...m_s$ 有唯一解 $x\equiv \sum\limits_{i=1}^sb_i\cdot\frac{M}{m_i}[(\frac{M}{m_i})^{-1}\pmod {m_i}]\pmod M$

习题

带公式版本：

带入版本：（不需要$m_i$ 互素）

技巧版本：

设 $m_1,m_2,...,m_s$ 为两两互素的正整数，若对于 $1\leq i\leq s$，同余式 $f_i(x)\equiv 0\pmod {m_i}$ 有 $C_i$ 个解，那么同余式组

$$\left\{\begin{matrix} f_1(x)\equiv 0\pmod {m_1} \\ f_2(x)\equiv 0\pmod{m_2} \\ ...\\ f_s(x)\equiv 0\pmod{m_s} \end{matrix}\right.$$

模 $M=m_1m_2...m_s$ 有 $C_1C_2...C_s$ 个解

设 $p$ 为素数，$i_1\geq i_2\geq ...\geq i_s,b_1,b_2,...,b_s$ 为任意整数，同余式组

$$\left\{\begin{matrix} x\equiv b_1\pmod{p^{i_1}}\\ x\equiv b_2\pmod{p^{i_2}}\\ ...\\ x\equiv b_s\pmod{p^{i_s}} \end{matrix}\right.$$

如果有解，其解为

$$x\equiv b_1\pmod{p^{i_1}}$$

有解充要条件是

$$\left\{\begin{matrix} b_1\equiv b_2\pmod{p^{i_2}}\\ b_2\equiv b_3\pmod{p^{i_3}}\\ ...\\ b_s\equiv b_s\pmod{p^{i_s}} \end{matrix}\right.$$

习题

# 模为素数幂的同余式的解法

设 $p$ 为素数，

1. 若 $x \equiv x_1 \pmod{p}$ 是同余式 $f(x) \equiv 0 \pmod{p}$ 的一个解
2. 且满足 $(f'(x_1), p) = 1$

则对于任意正整数 $k > 1$，$f(x) \equiv 0 \pmod{p^k}$ 的满足 $x \equiv x_1 \pmod{p}$ 的解 $x_k$ 可通过如下递推公式得到：

$$x_i \equiv x_{i-1} - f(x_{i-1}) \cdot \left(f'(x_1)^{-1} \pmod{p}\right) \pmod{p^i}, \quad i=2,3,\cdots,k$$

习题