同余与同余方程

同余定义

这是为您重写的证明，采用了极简的算式推导流。

这个定理非常实用，它打通了“余数世界”和“整除世界”的桥梁。我根据其核心性质，将其命名为**“同余差分律”**。

---

同余差分律 (同余定义的等价形式)

核心直觉：如果两个数 $a$ 和 $b$ 在圆环跑道上停在同一个位置（同余），那么它们跑过的路程之差，一定是跑道长度 $n$ 的整数倍。

$$a \equiv b \pmod n \iff n \mid (a - b)$$

1. 定义（带余除法）： 设 $a, b$ 被 $n$ 除，商为 $q, q'$，余数为 $r, r'$。

   $$a = nq + r$$
   $$b = nq' + r'$$

2. 做差（构建联系）： 两式相减：

   $$a - b = n(q - q') + (r - r')$$

3. 正向推导 ($\Rightarrow$)：

   • 若 $a \equiv b \pmod n$（即余数相同 $r = r'$）
   • $\Rightarrow r - r' = 0$
   • 代入差分式： $\Rightarrow a - b = n(q - q')$
   • 结论：$n \mid (a - b)$

4. 逆向推导 ($\Leftarrow$)：

   • 若 $n \mid (a - b)$
   • 观察差分式 $a - b = \underbrace{n(q - q')}_{\text{能被n整除}} + (r - r')$
   • $\Rightarrow n$ 必须整除剩余部分 $(r - r')$

   关键限制：

   • 余数差的绝对值必然小于除数：$-n < r - r' < n$
   • 在此范围内，能被 $n$ 整除的数只有一个：$0$。 $\therefore r - r' = 0 \Rightarrow r = r'$ 结论：$a \equiv b \pmod n$

---

逻辑：两数相减，正好把“多出来的余数”抵消掉，只剩下 $n$ 的整数倍。

根据上面的定义,很容易得到同余的性质

传递性的简易证明:

• 由 $a \equiv b \pmod n$ 和 $b \equiv c \pmod n$，可得 $n \mid (a - b)$ 和 $n \mid (b - c)$
• 由整除的性质，可得 $n \mid (a - b + b - c) = n \mid (a - c)$
• 由同余的定义，可得 $a \equiv c \pmod n$

同余的运算性质

这是为您准备的证明，采用极简算式推导流。

我们统一使用 同余差分律 作为解题万能钥匙： 定义：$A \equiv B \pmod n \iff n \mid (A - B)$。

设 $a - b = nk, \quad c - d = nm$。

---

1. 加减法

目标：$(a \pm c) \equiv (b \pm d) \pmod n$

1. 做差： $(a \pm c) - (b \pm d) = (a - b) \pm (c - d)$
2. 代入： $= nk \pm nm$ $= n(k \pm m)$
3. 结论： $n$ 整除差值 $\Rightarrow$ 成立。

---

2. 乘法

目标：$ac \equiv bd \pmod n$

1. 做差： $ac - bd$
2. 搭桥 (关键技巧：加一项减一项 $bc$)： $= ac - \mathbf{bc} + \mathbf{bc} - bd$ $= c(a - b) + b(c - d)$
3. 代入： $= c(nk) + b(nm)$ $= n(ck + bm)$
4. 结论： $n$ 整除差值 $\Rightarrow$ 成立。

---

3. 倍增

目标：$ka \equiv kb \pmod n$

1. 做差： $ka - kb$
2. 提取： $= k(a - b)$ $= k(nk)$
3. 结论： 结果仍是 $n$ 的倍数 $\Rightarrow$ 成立。

---

4. 幂运算

目标：$a^m \equiv b^m \pmod n$

1. 做差： $a^m - b^m$
2. 因式分解公式： $= (a - b)(a^{m-1} + a^{m-2}b + \dots + b^{m-1})$
3. 判定： $\because a \equiv b \Rightarrow n \mid (a - b)$ $\therefore n$ 必整除包含 $(a - b)$ 因子的整个乘积。
4. 结论： 成立。

---

5. 同余消去律

目标：若 $ab \equiv ac \pmod n$ 且 $(a, n) = 1$，则 $b \equiv c$。

1. 转化： $ab \equiv ac \Rightarrow n \mid (ab - ac)$ $\Rightarrow n \mid a(b - c)$
2. 引用互质消去律： $\because n \mid a(b - c)$ 且 $(n, a) = 1$ $\therefore n$ 无法“依附”于 $a$，必须整除 $(b - c)$。
3. 结论： $n \mid (b - c) \Rightarrow b \equiv c \pmod n$。

---

核心技巧：

• 加减法：直接做差。
• 乘法：搭桥法（加一项减一项）。
• 倍增：提取公因子。
• 幂运算：因式分解。
• 消去律：利用互质性质。

这些性质让同余运算像代数中的等式一样自由操作，是解题的强大工具。

这是一份基于你提供的关于**“剩余类及其运算”**（Residue Classes and Operations）的图片内容整理的学习总结。

这一章节标志着数论学习的一个重要飞跃：从研究单独的“数”，转向研究“数的集合”（类）。

6. 同余消去律 (通用版)

这个定理告诉我们：在同余式两边同时消去一个数时，模数也必须同时除以它们的最大公约数。

证明过程

设 $d = (c, n)$ 为 $c$ 和 $n$ 的最大公约数。

1. 转化 (同余转整除)：

   • $ca \equiv cb \pmod n$ $\iff n \mid c(a - b)$

2. 约分 (提取公约数 $d$)：

   • 将 $n$ 写为 $d \cdot \frac{n}{d}$，将 $c$ 写为 $d \cdot \frac{c}{d}$ $\iff d \cdot \frac{n}{d} \mid d \cdot \frac{c}{d} (a - b)$

3. 化简 (两边同除以 $d$)：

   • $\iff \frac{n}{d} \mid \frac{c}{d} (a - b)$

4. 引用 (互质消去律)：

   • $\because$ 除去最大公约数后，$(\frac{n}{d}, \frac{c}{d}) = 1$ (互质)
   • 根据互质消去律，$\frac{n}{d}$ 无法整除 $\frac{c}{d}$，必须整除后半部分
   • $\iff \frac{n}{d} \mid (a - b)$

5. 结论 (整除转同余)： $\iff a \equiv b \pmod{\frac{n}{d}}$ 即 $a \equiv b \pmod{\frac{n}{(c,n)}}$

证毕

直觉模型: 因为乘数 $c$ 里面含有模数 $n$ 的“基因”（公因子），所以在消去 $c$ 之后，模数 $n$ 必须把这部分“基因”也剔除掉，剩下的才是 $a$ 和 $b$ 真正的约束。

举个栗子 🌰

假设 模数 $n = 12$（你的目标是凑齐 12 的倍数）。 我们看方程：$6a \equiv 6b \pmod{12}$。 这里 $c = 6$。

• 目标：$6 \times (a-b)$ 必须是 $12$ 的倍数。
• 分析 $c$ (即 6)：
  • $6$ 里面已经包含了因子 $2$ 和 $3$。
  • $12$ 里面包含了因子 $2, 2, 3$。
  • 你看，$c$ 已经提供了 $12$ 所需的大部分因子，只缺一个 $2$ 了！
• 结果：
  • $(a-b)$ 只需要负责提供剩下的那个 $2$ 就可以了。
  • 所以，$a$ 和 $b$ 的差距只要是 $2$ 的倍数 就行，不需要是 $12$ 的倍数。
  • 这就是为什么模数从 $12$ 变成了 $2$ ($\frac{12}{(6,12)} = 2$)。

7. 同倍律

$$a \equiv b \pmod m \to ka \equiv kb \pmod km$$

---

剩余类及其运算

在此之前，我们学习了同余 $a \equiv b \pmod m$，这意味着 $a$ 和 $b$ 除以 $m$ 的余数相同。 现在，我们将所有**“同余的数”打包放进同一个袋子里，这个袋子就叫剩余类**。

• 定义：对于给定的模 $m$，我们可以根据余数是 $0, 1, 2, \dots, m-1$ 将所有的整数划分为 $m$ 个集合。
• 例子 (模 3)： 如果我们模 $3$，整数被分为 3 类：
  • 余 0 的类 ($\overline{0}$)：$\{\dots, -6, -3, 0, 3, 6, \dots\}$
  • 余 1 的类 ($\overline{1}$)：$\{\dots, -5, -2, 1, 4, 7, \dots\}$
  • 余 2 的类 ($\overline{2}$)：$\{\dots, -4, -1, 2, 5, 8, \dots\}$
• 符号：
  • 模 $m$ 的剩余类集合记作 $Z_m$。
  • 例如 $Z_3 = \{\overline{0}, \overline{1}, \overline{2}\}$。
  • 其中的每一个元素（如 $\overline{1}$）代表的不仅仅是数字 1，而是所有除以 3 余 1 的整数的集合。

---

有了这些“类”，我们就可以直接对它们进行加法和乘法运算。这不再是普通数字的运算，而是集合与集合之间的运算。

运算规则

• 加法：$\overline{a} + \overline{b} = \overline{a+b}$
• 乘法：$\overline{a} \times \overline{b} = \overline{a \times b}$

核心思想：你可以从类 $\overline{a}$ 中随便拿一个代表数，从类 $\overline{b}$ 中随便拿一个代表数，算完之后看结果属于哪个类。结果与你选哪个代表数无关（这叫运算的“良定义”）。

证明剩余类的运算与代表数的选择无关，可以通过同余的性质来证明。

• 加法： 设 $a \equiv a' \pmod m$，$b \equiv b' \pmod m$，则

  $$a + b \equiv a' + b' \pmod m$$
  因此，$\overline{a} + \overline{b} = \overline{a + b} = \overline{a' + b'} = \overline{a'} + \overline{b'}$。

• 乘法： 类似地，可以证明 $\overline{a} \times \overline{b} = \overline{a'} \times \overline{b'}$。

---

这里是为你重写的证明，完全采用了你要的“极简算式推导流”风格。

模 n 逆元存在充要条件

核心逻辑：将抽象的“模运算”降维成具体的“整系数方程”，利用 裴蜀定理 在“方程有解”与“互质”之间建立双向通道。

1. 转化：定义 $\to$ 方程

   • $[a]$ 有逆元 $\iff [a][x] = [1] \iff [ax] = [1]$
   • $\iff ax \equiv 1 \pmod n$
   • $\iff n \mid 1 - ax$
   • $\iff ny = 1 - ax \to ny + ax = 1$
   • $\iff \exists x, y \in \mathbb{Z}$，使得 $ax + ny = 1$

2. 必要性 ($\Rightarrow$)：方程 $\to$ 互质

   • 令 $d = (a, n)$
   • $\because d \mid a$ 且 $d \mid n \Rightarrow d \mid (ax + ny)$
   • 代入方程 $ax + ny = 1 \Rightarrow d \mid 1$
   • $\therefore (a, n) = 1$

3. 充分性 ($\Leftarrow$)：互质 $\to$ 方程 $\to$ 逆元

   • 若 $(a, n) = 1$
   • 引用：裴蜀定理 (即：若 $(a, n)=d \Rightarrow \exists x, y, ax+ny=d$)
   • $\Rightarrow \exists x, y$ 使得 $ax + ny = 1$
   • $\xrightarrow{\text{两边模 } n} ax \equiv 1 \pmod n$
   • $\therefore [x]$ 即为 $[a]$ 的逆元

证毕

---

这种把“模 $1$”转化成“等于 $1$ 加上 $n$ 的倍数” ($ax + ny = 1$) 的技巧，是解决同余问题的通用钥匙。

按照这个逻辑流，你觉得哪一步最关键，起到了“桥梁”的作用？

零因子

图片中展示了模 4 ($Z_4$) 和模 5 ($Z_5$) 的加法与乘法表，对比这两个表能发现非常重要的性质。

3.1 模 4 的运算 ($Z_4$)

• 集合：$\{\overline{0}, \overline{1}, \overline{2}, \overline{3}\}$
• 特殊的现象： 在乘法表中，我们发现：
  $$\overline{2} \times \overline{2} = \overline{4} = \overline{0}$$
  这意味着：两个非零的数相乘，结果竟然变成了 0！
  • 这种现象在普通算术中是不存在的，但在模运算（特别是模合数）中很常见。这些非零但乘积为零的数被称为“零因子”。

3.2 模 5 的运算 ($Z_5$)

• 集合：$\{\overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4}\}$
• 性质： 由于 5 是素数，观察其乘法表可以发现：
  • 没有出现“两个非零数相乘等于 0”的情况。
  • 这使得 $Z_5$ 的结构比 $Z_4$ 更“完美”，性质更接近我们熟悉的实数运算。

---

总结与升华

• 抽象化：剩余类把无穷多的整数简化成了有限个“对象” ($0$ 到 $m-1$)。
• 运算封闭：在 $Z_m$ 里怎么算（加或乘），结果永远还在 $Z_m$ 里，跑不出去。
• 素数的特殊性：对比模 4 和模 5 的运算表暗示了：模是素数时，运算性质通常比模是合数时更优良（没有零因子）。

费马小定理

这是模运算中关于素数的一个神奇性质。

证明

核心逻辑：构造两组数，一组是“原版”，一组是“放大版（乘 $a$）”。利用模运算的“重排”性质建立乘积等式，最后像解方程一样消去阶乘。

1. 构造：取 $1$ 到 $p-1$ 的整数集 $S$

   • $S = \{1, 2, \dots, p-1\}$
   • 将 $S$ 中各项同乘 $a$ 得到 $S'$
   • $S' = \{a, 2a, \dots, (p-1)a\}$

2. 性质：同余重排

   • 互不相同：若 $i\cdot a \equiv j\cdot a \pmod p$，根据同余消去律（因为 $(a,p)=1$），必有 $i \equiv j$。
     • 这里用到了$p \to q \iff \neg q \to \neg p$
   • 非零：因为 $p$ 是素数且 $a$ 不是 $p$ 的倍数，所以 $k \cdot a$ 模 $p$ 不可能为 0。
   • 结论：$S'$ 中的元素模 $p$ 之后，刚好就是 $S$ 中的元素（只是顺序打乱了）。

3. 做积：两集合元素连乘，积必同余

   • $\prod (S') \equiv \prod (S) \pmod p$
   • $\Rightarrow a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod p$

4. 提取：整理算式

   • 左边提取 $p-1$ 个 $a$，并将数字部分合并为阶乘：
   • $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$

5. 消去：同余消去律

   • $\because p$ 是素数 $\Rightarrow ((p-1)!, p) = 1$ (阶乘与 $p$ 互质)
   • 两边消去公因子 $(p-1)!$
   • $\therefore a^{p-1} \equiv 1 \pmod p$

证毕

---

欧拉函数

为了把费马小定理推广到任意整数（不仅仅是素数），我们需要先定义一个计数工具：欧拉函数 $\phi(n)$。

计算公式

若 $n$ 的标准分解式为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，则：

$$\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right)$$

例子

• $\phi(10)$：与 10 互质的数有 $1, 3, 7, 9$，共 4 个。所以 $\phi(10)=4$。
• $\phi(p)$：如果 $p$ 是素数，除了它自己，比它小的都跟它互质，所以 $\phi(p) = p-1$。

---

欧拉定理

这是费马小定理的威力加强版（通用版）。

它的证明逻辑实际上是费马小定理证明的“完全推广版”。如果你看懂了刚才费马小定理的证明，这个证明的核心思路是一模一样的，只是把“$1$ 到 $p-1$”换成了“与 $n$ 互质的数”。

---

定理描述： 设 $n$ 为正整数，若整数 $a$ 与 $n$ 互质（即 $(a, n) = 1$），则：

$$a^{\phi(n)} \equiv 1 \pmod n$$

其中 $\phi(n)$ 是欧拉函数，表示 $1$ 到 $n$ 中与 $n$ 互质的数的个数。

---

详细证明过程

第一步：构建“缩系”集合 (Reduced Residue System)

我们需要找到 $1$ 到 $n$ 之间所有与 $n$ 互质的整数。 设这些数为 $r_1, r_2, \dots, r_{\phi(n)}$。 我们将这个集合记为 $R$：

$$R = \{r_1, r_2, \dots, r_{\phi(n)}\}$$

• 性质：集合里共有 $\phi(n)$ 个数，且每一个都满足 $(r_i, n) = 1$。

第二步：构造变换集合 将集合 $R$ 中的每一个数都乘以 $a$，得到一个新的集合 $R'$：

$$R' = \{ar_1, ar_2, \dots, ar_{\phi(n)}\}$$

第三步：证明两个集合“模 $n$ 同构” 我们需要证明 $R'$ 中的元素在模 $n$ 意义下，仅仅是 $R$ 中元素的重新排列。这需要验证两点：

1. 互质性保持： 因为 $(a, n) = 1$ 且 $(r_i, n) = 1$，根据数论性质，它们的乘积也与 $n$ 互质。 所以，$ar_i$ 模 $n$ 后的余数仍然在 $R$ 集合中。

2. 互不相同： 假设 $R'$ 中有两个元素模 $n$ 相同：

   $$ar_i \equiv ar_j \pmod n$$
   因为 $(a, n) = 1$，根据同余消去律，我们可以消去 $a$：
   $$r_i \equiv r_j \pmod n$$
   但在原集合 $R$ 中，$r_i$ 和 $r_j$ 是原本就不同的两个数。 结论：$R'$ 中的 $\phi(n)$ 个元素在模 $n$ 意义下互不相同。

推论：集合 $R'$ 的所有元素模 $n$ 后的结果，刚好就是集合 $R$ 的所有元素（顺序可能打乱）。

第四步：建立乘积等式 既然两个集合模 $n$ 后包含相同的数字，那么它们所有元素的乘积也一定模 $n$ 同余。

$$\text{乘积}(R') \equiv \text{乘积}(R) \pmod n$$

代入具体的元素：

$$(ar_1) \cdot (ar_2) \cdots (ar_{\phi(n)}) \equiv r_1 \cdot r_2 \cdots r_{\phi(n)} \pmod n$$

第五步：提取与消去

1. 提取 $a$： 等式左边共有 $\phi(n)$ 个 $a$，我们将它们提取出来：

   $$a^{\phi(n)} \cdot (r_1 r_2 \cdots r_{\phi(n)}) \equiv (r_1 r_2 \cdots r_{\phi(n)}) \pmod n$$

2. 令公共部分为 $P$： 设 $P = r_1 r_2 \cdots r_{\phi(n)}$。 等式变为：

   $$a^{\phi(n)} \cdot P \equiv P \pmod n$$

3. 执行消去： 我们要消去两边的 $P$。能消去的前提是 $(P, n) = 1$。

   • 因为 $R$ 集合中的每一个 $r_i$ 都与 $n$ 互质。
   • 所以它们的乘积 $P$ 也必然与 $n$ 互质。

   根据同余消去律，两边同时消去 $P$，得到：

   $$a^{\phi(n)} \equiv 1 \pmod n$$

证毕。

---

💡 核心逻辑链

1. 找齐所有与 $n$ 互质的数。
2. 全部乘 $a$。
3. 发现这堆新数模 $n$ 后其实还是原来那堆数。
4. 把两堆数乘起来划等号。
5. 消掉公共的大尾巴，剩下的就是 $a^{\phi(n)} \equiv 1$。

两个定理的关系

费马小定理只是欧拉定理的一个特例。

• 欧拉定理说：周期是 $\phi(n)$。
• 当 $n$ 是素数 $p$ 时：$\phi(p) = p-1$。
• 代入公式就变成了费马小定理：$a^{p-1} \equiv 1 \pmod p$。

🚀 实际应用：降幂大法

这两个定理最强大的用处是简化超级大的指数。 计算 $a^b \pmod n$ 时，我们可以把指数 $b$ 对 $\phi(n)$ 取模，从而把巨大的 $b$ 变小。

公式：

$$a^b \equiv a^{b \pmod{\phi(n)}} \pmod n$$

---

总结

• 费马小定理：素数的特殊性质，周期是 $p-1$。
• 欧拉定理：任意整数的通用性质，周期是 $\phi(n)$。
• 欧拉函数：计算互质数的个数，是两个定理的关键工具。

这两个定理不仅是数论的精华，也是现代密码学的数学基础。它们揭示了**“指数循环”**的规律，让我们能够在模运算中安全地处理大数。

一次同余方程

---

证明过程

1. 转化 (同余 $\to$ 等式)

   • 根据同余定义，方程 $ax \equiv b \pmod n$ 等价于存在整数 $y$，使得：
   • $n \mid (ax - b) \Rightarrow ax - ny = b$
   • 这将问题转化为二元一次不定方程（裴蜀等式形式）。

2. 必要性 ($\Rightarrow$)：若有解，则 $d \mid b$, 设 $d = (a, n)$，即 $a, n$ 的最大公约数。

   1. 整除性质：
      • $\because d \mid a \Rightarrow d \mid ax$
      • $\because d \mid n \Rightarrow d \mid ny$
   2. 线性组合：
      • $\therefore d \mid (ax - ny)$
   3. 代入：
      • $\because ax - ny = b$
      • $\therefore d \mid b$
   4. 结论：如果方程有解，那么 $b$ 必须是 $(a, n)$ 的倍数。

3. 充分性 ($\Leftarrow$)：若 $d \mid b$，则有解

   1. 引用裴蜀定理：
      • 对于 $d = (a, n)$，一定存在整数 $s, t$ 使得：
      • $as + nt = d$
   2. 扩大倍数：
      • 因为已知 $d \mid b$，设 $b = k \cdot d$。
      • 将上式两边同乘 $k$：
      • $a(sk) + n(tk) = k \cdot d = b$
   3. 构造解：
      • 令 $x = sk$，上式变为：
      • $ax + n(tk) = b \Rightarrow ax - b = n(-tk)$
      • 即 $n \mid (ax - b)$
      • $\therefore x = sk$ 是方程的一个解。

---

总结

$$ax \equiv b \pmod n \text{ 有解} \iff (a, n) \mid b$$