模运算
好的，我们从一个你已经熟悉的概念——“同余”——出发，来探索一个更广泛、更基础的概念：模运算。如果说同余描述的是两个数之间的关系，那么模运算就是在这种关系上定义的一整套算术体系。
第一步：从同余到模运算
回忆一下同余的定义：对于给定的正整数 \(m\)（称为模数），如果两个整数 \(a\) 和 \(b\) 满足 \(a - b\) 能被 \(m\) 整除，即 \(m \mid (a - b)\)，我们就说 \(a\) 和 \(b\) 模 \(m\) 同余，记作 \(a \equiv b \ (\text{mod} \ m)\)。
模运算的核心思想是，我们不关心整数本身的大小，而只关心它除以模数 \(m\) 后的余数。所有模 \(m\) 同余的整数，在模 \(m\) 的世界里被视为“同一个东西”。这个“东西”我们称之为一个同余类。
- 定义（同余类）：给定模数 \(m\)，整数 \(a\) 所在的同余类是所有与 \(a\) 模 \(m\) 同余的整数的集合，记作 \([a]_m\)。即：
\[ [a]_m = \{ ..., a-2m, a-m, a, a+m, a+2m, ... \} \]
- 例子：当模数 \(m = 5\) 时，整数 \(7\) 所在的同余类是 \([7]_5\)。这个集合包含了 \(..., -3, 2, 7, 12, 17, ...\)。你会发现，这个集合里的每个数除以 \(5\) 的余数都是 \(2\)。所以，我们也可以把这个类记作 \([2]_5\)。
第二步：模运算的“舞台”——整数模 \(n\) 环
现在，我们把所有互不相同的同余类放在一起，形成一个集合。这个集合是模运算发生的“舞台”。
- 定义（整数模 \(n\) 集合）：模数 \(m\) 的所有不同同余类构成的集合，称为整数模 \(m\) 的集合，记作 \(\mathbb{Z}/m\mathbb{Z}\) 或 \(\mathbb{Z}_m\)。
\[ \mathbb{Z}/m\mathbb{Z} = \{ [0]_m, [1]_m, [2]_m, ..., [m-1]_m \} \]
这个集合里正好有 \(m\) 个元素，因为余数只能从 \(0\) 到 \(m-1\)。
- 例子：当 \(m = 5\) 时，
\[ \mathbb{Z}/5\mathbb{Z} = \{ [0]_5, [1]_5, [2]_5, [3]_5, [4]_5 \} \]
这个集合包含了模 \(5\) 意义下所有可能的“数”。
第三步：在“舞台”上定义运算
仅仅有集合还不够，我们需要定义这个集合上的加法和乘法，这样才能进行“运算”。定义的方式非常自然：对同余类进行运算，等于对它们代表的余数进行普通运算后，再取模。
- 定义（模运算）：在 \(\mathbb{Z}/m\mathbb{Z}\) 上，我们定义加法和乘法如下：
\[ [a]_m + [b]_m = [a + b]_m \]
\[ [a]_m \times [b]_m = [a \times b]_m \]
- 关键点：这个定义是“良定义”的。这意味着，无论你从同余类 \([a]_m\) 中挑选哪个数（比如 \(7\) 或 \(12\)）来代表这个类，最终运算结果所在的同余类都是唯一确定的。例如，在 \(\mathbb{Z}/5\mathbb{Z}\) 中：
- 计算 \([2]_5 + [4]_5\)：
- 用 \(2\) 和 \(4\) 算：\(2 + 4 = 6\)，\(6 \equiv 1 \ (\text{mod} \ 5)\)，所以结果是 \([1]_5\)。
- 用 \(7\)（属于 \([2]_5\)）和 \(9\)（属于 \([4]_5\)）算：\(7 + 9 = 16\)，\(16 \equiv 1 \ (\text{mod} \ 5)\)，结果仍然是 \([1]_5\)。
- 计算 \([2]_5 \times [4]_5\)：
- \(2 \times 4 = 8\)，\(8 \equiv 3 \ (\text{mod} \ 5)\)，结果是 \([3]_5\)。
为了方便，我们通常直接用余数 \(0, 1, 2, ..., m-1\) 来代表整个同余类，并默认我们在进行模运算。所以上面 \(\mathbb{Z}/5\mathbb{Z}\) 的加法和乘法表可以简写为：
| + mod 5 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| × mod 5 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
第四步：模运算的奇妙性质与核心概念
在模运算的世界里，很多我们熟悉的算术规则依然成立（比如交换律、结合律），但也出现了一些新的、有趣的现象。
-
加法逆元（相反数）：在模 \(m\) 运算中，每个元素 \(a\) 都有一个唯一的加法逆元 \(b\)，使得 \(a + b \equiv 0 \ (\text{mod} \ m)\)。这个 \(b\) 就是 \(m - a\)（当 \(a \neq 0\) 时）。例如，在模 \(5\) 中，\(2\) 的加法逆元是 \(3\)，因为 \(2 + 3 = 5 \equiv 0\)。
-
乘法逆元（倒数）：这是模运算中最重要、也最有趣的概念之一。在普通算术里，\(a\) 的乘法逆元是 \(\frac{1}{a}\)，满足 \(a \times \frac{1}{a} = 1\)。在模 \(m\) 运算中，我们问：对于一个数 \(a\)，是否存在一个数 \(b\)，使得 \(a \times b \equiv 1 \ (\text{mod} \ m)\)？如果存在，\(b\) 就称为 \(a\) 模 \(m\) 的乘法逆元。
- 关键定理：\(a\) 在模 \(m\) 下有乘法逆元，当且仅当 \(a\) 和 \(m\) 互质（即 \(\gcd(a, m) = 1\)）。
- 例子：
- 在模 \(5\) 下，看乘法表对角线（结果是 \(1\) 的那些项）：
- \(1 \times 1 \equiv 1\)，所以 \(1\) 的逆元是 \(1\)。
- \(2 \times 3 \equiv 6 \equiv 1\)，所以 \(2\) 的逆元是 \(3\)，\(3\) 的逆元是 \(2\)。
- \(4 \times 4 \equiv 16 \equiv 1\)，所以 \(4\) 的逆元是 \(4\)。
- 所有非零元 \(1, 2, 3, 4\) 都有逆元，因为它们都和 \(5\) 互质。
- 在模 \(6\) 下：
- 找 \(2\) 的逆元？我们需要解 \(2b \equiv 1 \ (\text{mod} \ 6)\)。检查 \(b = 0,1,2,3,4,5\)，\(2 \times b\) 的结果是 \(0, 2, 4, 0, 2, 4\)，永远得不到 \(1\)。所以 \(2\) 在模 \(6\) 下没有乘法逆元，因为 \(\gcd(2, 6) = 2 \neq 1\)。
总结
模运算是一套建立在整数同余关系之上的完整算术系统。它的核心是将整数按除以模数 \(m\) 的余数分类，并在这些同余类（集合 \(\mathbb{Z}/m\mathbb{Z}\)）上定义加法和乘法。这套系统不仅保留了普通整数的许多优良性质，还引入了像乘法逆元这样依赖于互质关系的关键概念。模运算是现代密码学、计算机科学和数论许多高级概念的基石。