$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } $$ 在上文中，我们已经定义了同余关系，现在的问题是我们是否可以像操作等式一样操作同余关系。事实上，我们可以将等式的替换规则(substitution rule)应用于同余关系中，但与等式的替换规则不同，对于任意的非零整数 \(k \in \Z\)，只有在 \(k\) 与 \(n\) 互素时，同余式 \(a ≡ b\ ( mod\ n )\) 与 \(k \cdot a ≡ k \cdot b\ (mod\ n) \) 相等。
设整数 \(a_1,a_2,b_1,b_2, k\in\Bbb{Z}\)。以下规则适用于同余规则：
- \(a_1 ≡ b_1\ (mod\ n) \Leftrightarrow a_1+k ≡ b_1+k\ (mod\ n) \)
- \(a_1 ≡ b_1\ (mod\ n) \Rightarrow k \cdot a_1 ≡ k \cdot b_1\ (mod\ n) \)
- \(gcd(k,n)=1\) 且 \(k \cdot a_1 ≡ k \cdot b_1\ (mod\ n) \Rightarrow a_1 ≡ b_1\ (mod\ n) \)
- \(k \cdot a_1 ≡ k \cdot b_1\ (mod\ k \cdot n) \Rightarrow a_1 ≡ b_1\ (mod\ n) \)
- \(a_1 ≡ b_1\ (mod\ n)\) 且 \(a_2 ≡ b_2\ (mod\ n) \Rightarrow a_1+a_2 ≡ b_1+b_2\ (mod\ n)\)
- \(a_1 ≡ b_1\ (mod\ n)\) 且 \(a_2 ≡ b_2\ (mod\ n) \Rightarrow a_1 \cdot a_2 ≡ b_1 \cdot b_2\ (mod\ n)\)
与传统整数计算不同的是。同余关系符合费马小定理(Fermat's Littile Theorem)。简单来说，在模运算中，每个数的素数幂次与该数本身同余。更加精确的表述为，设素数 \(p \in \Bbb{P}\) ，且整数 \(k \in \Bbb{Z}\) ，满足以下公式：
\[k^p ≡ k\ (mod\ p)\]
如果 \(k\) 与 \(p\) 互素，我们可以在上述同余式两边同除 \(k\) ，得到以下等式：
\[k^{p-1} \equiv 1\ (mod\ p)\]
下列Sage代码展示了费马小定理的示例，并强调了底数 \(k\) 与 \(p\) 的互素情况(\(k=64,p=137\))和不互素的情况(\(k=1918,p=137\))：
sage: ZZ(137).gcd(ZZ(64))
1
sage: ZZ(64) ^ ZZ(137) % ZZ(137) == ZZ(64) % ZZ(137)
True
sage: ZZ(64) ^ ZZ(137 - 1) % ZZ(137) == ZZ(1) % ZZ(137)
True
sage: ZZ(1918).gcd(ZZ(137))
137
sage: ZZ(1918) ^ ZZ(137) % ZZ(137) == ZZ(1918) % ZZ(137)
True
sage: ZZ(1918) ^ ZZ(137-1) % ZZ(137) == ZZ(1) % ZZ(137)
False
以下示例包含了本节介绍的大部分概念。
示例 9
为了更好理解同余，我们对以下同余方程进行求解：
\[7\cdot(2x+21) + 11 \equiv x - 102\ (mod\ 6)\]
因为同余式与等式的变换规则有或多或少的相似，我们可以安装与求解等式方程时类似的方法进行同余方程的求解。我们对同余方程的右侧进行化简：
\[7\cdot(2x+21) + 11 = 14x + 147 + 11 = 14x + 158\]
基于上述表达式，我们可以将同余方程写为：
\[14x + 158 \equiv x - 102\ (mod\ 6)\]
在接下来的步骤中，我们希望将当前等式转化为仅有包含 \(x\) 的项在左侧，其他项在右侧的形式。 变化过程如下：
\[ \begin{multline*} 14x + 158 \equiv x - 102\ (mod\ 6) \Leftrightarrow\\ 14x - x + 158 - 158 \equiv x -x - 102 - 158\ (mod\ 6) \Leftrightarrow \\ 13x \equiv -260\ (mod\ 6) \end{multline*} \]
如果同余方程只是一个正常的整数方程，我们可以通过两边同除 13 获得 \(x=-20\) 的结果。但是，在同余方程中，我们需要保证模数和我们需要除去的数为互素关系，这可以保证除法结果与原式等价。这意味这我们需要计算 \(gcd(13,6)\) 。由于 13 是素数且 6 不是 13 的因子，我们得到 \(gcd(13,6)=1\)，所以 13 和 6 为互素关系。因此，我们可以在同余方程两侧同除 13，如下:
\[13x \equiv -260\ (mod\ 6) \Leftrightarrow x \equiv -20\ (mod\ 6)\]
我们现在的任务是找到所有的整数 \(x\) 满足 \(x\) 与 \(-20\) 在模 \(6\) 的条件下同余。换言之，我们需要找到所有满足以下等式的 \(x\)：
\[x\ (mod\ 6) = -20\ (mod\ 6)\]
因为 \(-4 \times 6 + 4 = -20\)，我们知道 \(-20\ mod\ 6 = 4\)，所以 \(x=4\) 是同余方程的一个解。但是，\(22\) 是另一个答案，因为 \(22\ (mod\ 6)=4\)。还有一个答案是 \(-20\) 。事实上，满足此方程的解构成以下集合：
\[ \{\ldots, -8,-2, 4,10, 16,\ldots\} = \{4+k\cdot 6 ;|; k\in \Bbb{Z}\} \]
总结来说，我们证明了\(7\cdot(2x+21) + 11 \equiv x - 102\ (mod\ 6)\) 的解为 \(\{x = 4+k\cdot 6 ;|; k\in \Bbb{Z}\} \) 。我们从此解集内任取两个数，\(x=4\) 和 \(x=4+12 \times 6 = 76\) 使用Sage验证：
sage: (ZZ(7)* (ZZ(2)*ZZ(4) + ZZ(21)) + ZZ(11)) % ZZ(6) == (ZZ(4) - ZZ(102)) % ZZ(6)
True
sage: (ZZ(7)* (ZZ(2)*ZZ(76) + ZZ(21)) + ZZ(11)) % ZZ(6) == (ZZ(76) - ZZ(102)) % ZZ(6)
True
如果您到现在仍不熟悉模运算，并且移位模运算看起来如此复杂而气馁，您应记住两件事。第一，在模运算中计算同余并不比在您更熟悉的数学体系(如有理数体系)中的计算复杂，这只是一个习惯问题。其次，当我们在 3.3.4 节 引入同余类表示的概念，计算会变得更加清晰和易于处理。
练习 16. 已知在模 13 的情况下，计算以下同余方程的所有解 \(x \in \Bbb{Z}\) ：
\[\kongru{5x+4}{28+2x}{13}\]
练习 17. 已知在模 23 的情况下，计算以下同余方程的所有解 \(x \in \Z\) ：
\[\kongru{69x}{5}{23}\]
练习 18. 已知在模 23 的情况下，计算以下同余方程的所有解 \(x \in \Z\) ：
\[\kongru{69x}{46}{23}\]
练习 19. 设 \(a,b,k \in \Z \)，满足 \(\kongru{a}{b}{n}\) 。证明 \(\kongru{a^k}{b^k}{n}\)
练习 20. 设 \(a,n \in \Z \)，满足 \(a\) 和 \(n\) 互不互素。对于 \(b \in \Z \)，同余方程 \(\kongru{a \cdot x}{b}{n}\) 有解 \(x\)。请说明 \(b\) 需要满足的条件及求出方程的解集。