关于同余

文章迁移信息

本文写于 240328，原笔记名「🌻除法与模运算」，251011 由本地知识库迁移而来。

为了更好理解本章节，建议先学习 站内文章关于质数。

整除

如果 $a$ 和 $b$ 是整数，且 $a≠0$，如果有整数 $c$ 使得 $b = ac$，或者 $b/a$ 是一个整数，我们称 a 整除 b。

• $a$ 是 $b$ 的一个因子（或除数，约数）。$b$ 是 $a$ 的一个倍数。
• 记号 $a\mid b$ 表示 a 整除 b，$a\not\mid b$ 表示 $a$ 不能整除 $b$。

0 是所有非 0 整数的倍数。对于整数 $b\ne 0$，b 的约数只有有限个。

定理 TY-1

a，b，c 是整数且 $a≠0$，

1. 如果 $a \mid b$ 且 $a \mid c$ ，那么 $a \mid (b + c)$。同时也说明，如果 a 同时整除 b 和 c，那么它也必须整除 b 和 c 的差。
2. 如果 $a \mid b$ ，那么对于任意整数 c 都有 $a \mid bc$。
3. 如果 $a \mid b$ 且 $b \mid c$ ，那么 $a \mid c$。

小练习：证明任意相邻的两个奇数互质（互素）

一些推论 TY-2

1. 如果 a，b，c 是整数且 $a≠0$，满足 $a \mid b$ 和 $a \mid c$，当 m 和 n 是整数时，有 $a \mid mb + nc$ 。
2. $a\mid b\iff -a\mid b \iff a\mid -b\iff |a| \mid |b|$
3. $a\mid b \land b\mid a \implies b=\pm a$
4. 设 $m\ne 0$，那么 $a\mid b \iff ma \mid mb$
5. 设 $b\ne 0$，那么 $a\mid b \implies |a| \le |b|$
6. 设 $a\ne 0,b=qa+c$，那么 $a\mid b \iff a\mid c$

带余数除法

除法算法：如果 $a$ 是一个整数且 $d$ 是一个正整数，那么存在唯一整数 $q$ 和 $r$，其中 $0 ≤ r < d$, 使得 $a = dq + r$。

• $d$ 称为除数
• $a$ 称为被除数
• $q$ 称为商
• $r$ 称为余数。在这里的定义下，余数 $r$ 是最小非负余数。

有：

$$\begin{aligned} q=&a~ \textrm{div} ~d \\ r=&a \bmod d \end{aligned}$$

小学数学常识之中学语文知识：「除」和「除以」

$6÷2$ 读作：「六除以二」，也就是「（以）二除六」。在后一句中，主语是省略的（或者说主语就是你/我），谓语是「除」这个动作，宾语是作为分子的「六」，而「以二」则是状语。前一句是后一句的倒装。

同余

如果 a 和 b 为整数且 m 为正整数，则当 m 整除 $a - b$ 时称 a 模 m 同余 b。

• a 模 m 同余 b，记为 $a\equiv b ~(\bmod m)$
• a 和 b 不是模 m 同余的，记为 $a\not\equiv b ~(\bmod m)$

「同余」有时也称「等价」。

定理 TY-3：令 a 和 b 是整数，m 是正整数，则 $a\equiv b ~(\bmod m)\iff a \bmod m = b \bmod m$

ME：同余。顾名思义，就是两者之间都具有相同余数。

定理 TY-4：令 m 为正整数，$a\equiv b ~(\bmod m) \iff$ 存在整数 k 使得 a = b + km.

定理 TY-5

令 m 是正整数，如果 $a\equiv b ~(\bmod m), c\equiv d ~(\bmod m)$，则 $a+c ≡ b+d ~(\bmod m)$ 并且 $ac ≡ bd ~(\bmod m)$

• 将有效同余的两边加上（或减去）同一个整数可以保持有效性。
  • 如果 $a \equiv b(\bmod m)$ 那么 $c + a \equiv c + b(\bmod m)$，其中 c 是任意整数。
  • 加减法移项：$a+b\equiv c+d(\bmod m)$，可以移项得到 $a−c\equiv d−b(\bmod m)$
• 将有效同余的两边乘以同一个整数可以保持有效性。
  • 如果 $a ≡ b ~(\bmod m)$ 那么 $c\cdot a \equiv c\cdot b (\bmod m)$，其中 c 是任意整数。
  • 注意：将同余除以整数并不总是产生有效的同余。后文将会探讨。

推论 TY-6：分配律

设 m 是正整数且 a 和 b 是整数，那么:

• $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
• $a\cdot b \bmod m = ((a \bmod m)(b \bmod m)) \bmod m$

ME：用法就是将它们拆成或合并成好算的数。

一般地，如果 $x<0$ 且 $0≤y<m$，则式子 $x≡y(\bmod m)$ 相当于 $x \bmod m+m=y$

也就是用「模 m 加 m」可以把 x 调整为非负数。为避免判断 x<0，更一般的写法是 $(x \bmod m+m)\bmod m$。这样无论 x 是正是负还是零，运算结果都会落在区间 $[0,m−1]$ 中。

对于减法来说，当 a−b≥0 时，推论 TY-6 的加法恒等式可以调整为：

$$(a−b)\bmod m=((a\bmod m)−(b\bmod m)+m)\bmod m$$

练习题：🟩 3379. 转换数组 - 力扣（LeetCode）

Python 中只要 m 是正整数，取模运算的结果就一定是非负整数。Java 会出现模运算结果为负数的情况。

在模意义下的除法，我们不能简单的将除数和被除数都取模。但是在某些情况下，模意义下的除法也有简化的运算。

定理 TY-7

如果 p 是一个质数，a 是 b 的倍数且 b 和 p 互质（b 不是 p 的倍数），那么有

$$\frac{a}{b} ~\bmod p = (a\cdot b^{p-2}) \bmod p ​$$

上式中 a 和 b 可以是很大的数。

定理运用

本节定理不需死记硬背，仅供练习。

定理 TY-8

给定正整数 $x,y,z,p$，如果 $y\bmod p=x$，有：$(y-z)\bmod p=0 \iff z\bmod p=x$

证明：

ME：

1. 使用分配律：$(y-z)\bmod p=0 \iff (y \bmod p - z \bmod p) \bmod p=0 \iff (x-z\bmod p)\bmod p=0$。
2. 速记方式：y 本身带有余数 x，但是减去 z 之后没余数了，说明 z 带着余数 x。

定理 TY-9：给定正整数 $x,y,z,p$，有：$(y-z)\bmod p =x\iff z\bmod p=(y-x)\bmod p$

证明：

ME：

1. 使用分配律：$(y-z)\bmod p =x\iff (y\bmod p - z \bmod p)\bmod p = x\bmod p \iff (y\bmod p - x-z\bmod p)\bmod p=0$
   $\iff ((y-x)\bmod p-z \bmod p)\bmod p =0\iff(y-x)\bmod p-z \bmod p=0$
2. 速记方式：y-z 携带余数的一部分 x。z 携带余数的另一部分，这部分就是 y 减去 x 后剩下的部分。

模指数运算

详看 站内文章快速幂算法。

线性同余方程

线性同余方程：同余方程中形式为 $ax≡b~(\bmod m)$ 的方程，其中 m 是正整数，a 和 b 是整数，x 是变量。线性同余 $ax≡b~(\bmod m)$ 的解都是满足该同余方程的整数 x。

使得 $\bar{a}a\equiv1(\bmod m)$ 成立的整数 $\bar{a}$ 被称为模 m 的逆。

定理 TY-10：如果 a 和 m 为互素的整数且 m>1，则 a 模 m 的逆存在。而且这个模 m 的逆是唯一的。

即存在唯一小于 m 的正整数 ā 是 a 模 m 的逆，并且 a 模 m 的其他每个逆均与 ā 模 m 同余。（ME：注意这里的「唯一」的意思）。

证明：

1. 存在性。

• 由于 gcd(a，m)=1，根据贝祖定理 ZS-5，存在整数 s 和 t，使得 $sa+tm=1$。因此，$sa+tm≡1~(\bmod m)$.
• 由于 $tm ≡ 0~(\bmod m)$, 因此 $sa ≡ 1~(\bmod m)$
• 因此，s 是 a 模 m 的逆。

2. 唯一性。

• 假设 s 和 r 都是 a 模 m 的逆。$sa≡1~(\bmod m)$，$ra≡1~(\bmod m)$，所以 $sa≡ra~(\bmod m)$
• 由于 gcd(a，m)=1，根据引理 ZS-9，$s≡r~(\bmod m)$

例子：求 $\bar{a}$

例子：解线性同余方程

求线性同余方程 $3x≡4~(\bmod 7)$ 的解。

解：

• -2 是 3 模 7 的逆
• 两边同乘以 -2 得 $-2\cdot 3x≡-2\cdot 4~(\bmod 7)$
• 因为 $-6≡1~(\bmod 7)$ （ME：毕竟 3 刚刚和它的逆 -2 相乘，那么 $-6x\equiv 1\cdot x(\bmod 7)$）
• 又因为 $-8≡6~(\bmod 7)$ （ME：所以结果的右边应为 6）
• 所以 $x≡6~(\bmod 7)$
• x 的解是使得 $x≡6~(\bmod 7)$ 的整数，即 $6,13,...,-1,-8\dots$

求解同余方程的本质是求逆，求逆的本质是求贝祖系数。

中国剩余定理

小故事

故事 1：在公元一世纪时，中国数学家孙子问道：「有物不知其数，三分之余二，五分之余三，七分之余二，此物几何？」

故事 2：淮安民间传说着一则故事——韩信点兵，其次有成语「韩信点兵，多多益善」。韩信带 1500 名兵士打仗，战死四五百人，站 3 人一排，多出 2 人；站 5 人一排，多出 4 人；站 7 人一排，多出 3 人。

定理 TY-11：中国剩余定理

令 $m_{1},m_{2},\dots,m_{n}$ 为大于 1 的两两互素的正整数，而 $a_{1},a_{2},\dots,a_{n}$ 是任意整数。则同余方程组
$x\equiv a_{1} (\bmod m_{1})$
$x\equiv a_{2} (\bmod m_{2})$
$\vdots$
$x\equiv a_{n} (\bmod m_{n})$
有唯一的 模 $m=m_{1}m_{2}\dots m_{n}$ 的 解。即存在一个数满足 $0\leq x\leq m$ 的解 x，而所有其他的解均与此解模 m 同余。

证明：下图中的 TY-9 应为 TY-10

例子：求解同余方程组

例 1：利用中国剩余定理求解
$x\equiv 2 (\bmod 3)$
$x\equiv 3 (\bmod 5)$
$x\equiv 2 (\bmod 7)$

例 2：使用反向替换方法求解
$x\equiv 1 (\bmod 5)$
$x\equiv 2 (\bmod 6)$
$x\equiv 3 (\bmod 7)$

费马小定理

定理 TY-12：费马小定理

如果 p 是素数，对每个整数 a 都有 $a^p ≡ a ~(\bmod p)$；
如果 p 是素数，$p \not\mid a$，那么 $a^{p-1} ≡ 1 ~(\bmod p)$。

以上两个命题，当 $p \not\mid a$ 时，命题等价；而当 $p \mid a$ 时，$a^p ≡0≡ a ~(\bmod p)$ 平凡成立。因此，以上两个命题等价。

证明思路：

注意，费马小定理的逆命题不成立。

例子：利用费马小定理化简运算

求 $7^{121}\bmod 13$

解题步骤：

• 根据费马小定理，$7^{12} ≡ 1 (\mod 13)$
• 那么根据分配律有 $(7^{12})^k ≡ 1 (\mod 13)$，k 是任意整数
• $7^{121} = 7^{12 \cdot 10 +1} = (7^{12})^{10} \cdot 7 ≡ 1^{10} \cdot 7 ≡ 7 (\mod 13)$

同余的应用

校验位

比特串 $x_{1}x_{2}\dots x_{n}$ 的奇偶校验位 $x_{n+1}$ 定义为：

$$x_{n+1}=x_1+x_2+\dots+x_n \bmod 2$$

保证整个串为双数个 1。

零售产品通常由其通用产品代码（UPC）标识。UPC 最常用的形式是 12 位十进制数字：第一位数字标识产品种类，接着五位标识制造商，再五位标识特定产品，最后一位 $x_{12}$ 是校验码。校验码由同余式决定：

$$3x_{1}+x_{2}+3x_{3}+x_{4}+3x_{5}+x_{6}+3x_{7}+x_{8}+3x_{9}+x_{10}+3x_{11}+x_{12} \equiv 0 \bmod 10$$

所有图书都由一个国际标准书号（ISBN）标识。ISBN-10 包含不同分组来标识语言、出版商、出版公司赋予图书的编号、最后一位是校验码（或者是数字或者是字母 X 代表 10）。这个校验码的选择满足：

$$\sum_{i}^{10} i x_{i}\equiv 0 \bmod 11$$

本文参考

• 《算法导论》第 3 章 3.2 节模运算部分
• 研究生课程离散数学的数论与密码学部分
• 超级次方题解 - 力扣（LeetCode）
• 分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理/组合数） - 讨论 - 力扣（LeetCode）
• 费马小定理 & 欧拉定理 - OI Wiki
• 数论基础 - OI Wiki