算法和数据结构笔记

同余

1. 同余的定义

定义 两个整数 a, ba,\,b 除以正整数 mm，若余数相同，则称 aa 与 bb 关于模 mm 同余，记作 a≡b(modm)a \equiv b \pmod m。

显然

a≡b(modm)⇔a=km+b (k∈Z)⇔m∣(a−b) a \equiv b \pmod m \Leftrightarrow a = km+b\,(k \in \mathbb{Z}) \Leftrightarrow m \mid (a-b)

在数论的上下文中，记号 (c, m)(c,\,m) 表示 cc 与 mm 的最大公约数。

2. 同余的性质

2.1 常用性质

模为正整数，下列的数字都是整数。

  1. a≡a(modm)a \equiv a \pmod m（自反性）
  2. a≡b(modm)⇔a≡a(modm)a \equiv b \pmod m\Leftrightarrow a \equiv a \pmod m（对称性）
  3. a≡b(modm), b≡c(modm)⇒a≡c(modm)a \equiv b\pmod m,\, b \equiv c \pmod m\Rightarrow a \equiv c \pmod m（传递性）
  4. a≡b(modm), c≡d(modm)⇒a±c≡b±d(modm)a \equiv b\pmod m,\, c \equiv d \pmod m\Rightarrow a \pm c \equiv b \pm d \pmod m
  5. a≡b(modm), c≡d(modm)⇒ac≡bd(modm)a \equiv b\pmod m,\, c \equiv d \pmod m\Rightarrow ac \equiv bd \pmod m
    • 特别地 a≡b(modm)⇒ak≡bk(modm), k∈Za \equiv b \pmod m \Rightarrow ak \equiv bk \pmod m,\,k \in \mathbb{Z}
    • 反复运用上面的结论，得 a≡b(modm)⇒an≡bn(modm), n∈Na \equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m,\,n \in \mathbb{N}
  6. 若 ac≡bc(modm)ac \equiv bc \pmod m
    • 当 (c, m)=1(c,\,m) = 1 时，a≡b(modm)a \equiv b \pmod m
    • 当 (c, m)=d(c,\,m) = d 时，a≡b(modm/d)a \equiv b \pmod {m/d}
  7. A≡a(modm1), A≡a(modm2), (m1, m2)=1⇒A≡a(modm1m2)A \equiv a \pmod {m_1},\, A \equiv a \pmod {m_2},\,(m_1,\,m_2) = 1 \Rightarrow A \equiv a \pmod {m_1 m_2}

2.2 费尔马小定理

设 pp 是素数，aa 是正整数，且 (m1, m2)=1(m_1,\, m_2) = 1，则

ap−1≡1(modp) a^{p-1} \equiv 1 \pmod p

证明

由于 a, 2a, ⋯ , (p−1)aa,\,2a,\,\cdots,\,(p-1)a 模 pp 的余数各不相同，否则，若存在 ia≡ja(modp)ia \equiv ja \pmod p，其中 1⩽i<j⩽p−11 \leqslant i < j \leqslant p-1，则 p∣(j−i)ap \mid (j-i)a，而 p∤ap \nmid a，那么 p∣(j−i)p \mid (j-i)，这是不可能的。因此 a, 2a, ⋯ , (p−1)aa,\,2a,\,\cdots,\,(p-1)a 模 pp 的余数必然取遍 1, 2, ⋯ , p−11,\,2,\,\cdots,\,p-1 这 p−1p-1 个数，仅可能顺序不同。

故

a⋅2a⋯(p−1)a≡1⋅2⋯(p−1)  (modm) a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1)\;\pmod m

又 pp 是素数，则

((p−1)! , p)=1 \left((p-1)!\,,\,p\right) = 1

所以由性质（6）得

ap−1≡1(modm) a^{p-1} \equiv 1 \pmod m

3. 剩余类和完全剩余系

3.1 剩余类定义

定义 设 m∈N+m \in \mathbb{N}^+，把全体整数按对模 mm 的余数进行分类，余数为 r(0⩽r⩽m−1)r(0 \leqslant r \leqslant m - 1) 的所有整数归为一类，记为 KrK_r，KrK_r 称为模 mm 的一个 剩余类（r=0, 1, 2, ⋯ , m−1r = 0,\,1,\,2,\,\cdots,\,m-1）。

显然，KrK_r 是一个以 mm 为公差的无穷等差数集，即

Kr={qm+r∣m 是模, r 是余数, q∈Z} K_r = \left\{qm+r \mid m \text{ 是模},\,r \text{ 是余数},\, q \in \mathbb{Z} \right\}

3.2 剩余类性质

  1. Z=K0∪K1∪⋯∪Km−1\mathbb{Z} = K_0 \cup K_1 \cup \cdots \cup K_{m-1}，且 Ki∩Kj=∅, i≠jK_i \cap K_j = \emptyset,\, i \neq j
  2. 对任意的 n∈Nn \in \mathbb{N}，有唯一的 r0r_0 使 n∈Kr0n \in K_{r_0}
  3. 对任意的 a, b∈Za,\,b \in \mathbb{Z} 有 a, b∈Kr⇔a≡b(modm)a,\,b \in K_r \Leftrightarrow a \equiv b\pmod m

3.3 完全剩余系

定义 设 K0, K1, ⋯ , Km−1K_0,\,K_1,\,\cdots,\,K_{m-1} 是模 mm 的全部剩余类，从每个 KrK_r 中任取一个数 ara_r，这 mm 个数 a0, a1, ⋯ ,am−1a_0,\,a_1,\,\cdots,a_{m-1} 组成模为 mm 的一个 完全剩余系，简称 完系。

定义 0, 1, 2, ⋯ , m−10,\,1,\,2,\,\cdots,\,m-1 称为模 mm 的 最小非负完系。

由定义易得结论：mm 个整数 a1, a2, ⋯ , ama_1,\,a_2,\,\cdots,\,a_m 是模 mm 的一个完系的充要条件是 i≠ji \neq j 时，不存在 a≡aj(modm)a \equiv a_j \pmod m。

4. 不定方程

5. 孙子定理

设 n⩾2, m1, m2, ⋯ , mnn \geqslant 2,\,m_1,\,m_2,\,\cdots,\,m_n 是两两互质的正整数，记

M=m1m2⋯mn, Mi=Mmi, i∈1, n‾ M = m_1m_2\cdots m_n,\, M_i = \frac{M}{m_i},\, i \in \overline{1,\,n}

则同余方程组

{x≡c1(modm)1,x≡c2(modm)2,⋯x≡cn(modm)n \left\{ \begin{aligned} x &\equiv c_1 \pmod m_1, \\ x &\equiv c_2 \pmod m_2, \\ &\cdots \\ x &\equiv c_n \pmod m_n \end{aligned} \right.

有且仅有唯一解

x≡∑i=1nMiaici(modM) x \equiv \sum_{i=1}^n M_i a_i c_i \pmod M

其中

Miai≡1(modm)i, i∈1, n‾ M_i a_i \equiv 1 \pmod m_i,\,i \in \overline{1,\,n}