$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } \gdef\Zmod#1#2{#1\ \text{mod}\ #2} $$ 正如我们在上文中的各种示例见到的那样，计算同余式麻烦的，且解集通常较大。因此，找到一些方法简化模运算是有必要的。
当我们识别出某集合内的数进行模运算具有相同的余数，该集合被称为在模 \(n\) 体系中的同余类(remainder class 或 residue class)。使用同余类可以有效简化模运算。
根据带余除法的性质可以得到对于每个模 \(n\) 都有 \(n\) 个不同的同余类，对于整数的加法和乘法可以投影为同余类上的一种新的加法和乘法。
通俗的说，新的加法和乘法是通过取第一个同余类的任一元素与第二个同余类的一些元素进行正常的加法或乘法，然后判断产生的结果属于哪一个同余类。下面的例子使上述的抽象描述更加具体。
示例 11
选择模数 \(n=6\) ，此体系存在 6 个同余类。当我们使用余数标识每一个同余类，我们得到以下表示:
\[ \begin{array}{ccc} 0: = \{\ldots, -6,0,6,12, \ldots \}\\ 1: = \{\ldots, -5,1,7,13, \ldots \}\\ 2: = \{\ldots, -4,2,8,14, \ldots \} \\ 3: = \{\ldots, -3,3,9,15, \ldots \}\\ 4: = \{\ldots, -2,4,10,16, \ldots \}\\ 5: = \{\ldots, -1,5,11,17, \ldots \} \end{array} \]
假如我们需要计算 \(2+5\) 在模 6 体系内的结果，我们可以找到\(2\) 和 \(5\) 对应同余类的元素，此处我们选择 \(14\) 和 \(-1\)。对其进行正常的加法，结果为 \(14+(-1)=13\)。查找此结果对应的同余类为 \(1\)。
因此，我们得到 \(2+5=1\) 在模 6 体系内，另一种更加易读的使用同余式表示方式为 \(\kongru{2+5}{1}{6}\)
推而广之，模运算中的加法和乘法可以转化为同余类上的代表元素正常的加法和乘法。下表总结了模 6 体系内所有同余类的加法和乘法:
\[ \begin{array}{c | c c c c c c} + & 0 & 1 & 2 & 3 & 4 & 5\\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0\\ 2 & 2 & 3 & 4 & 5 & 0 & 1\\ 3 & 3 & 4 & 5 & 0 & 1 & 2\\ 4 & 4 & 5 & 0 & 1 & 2 & 3\\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \end{array} \quad \quad \quad \quad \begin{array}{c | c c c c c c} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3 & 4 & 5\\ 2 & 0 & 2 & 4 & 0 & 2 & 4\\ 3 & 0 & 3 & 0 & 3 & 0 & 3\\ 4 & 0 & 4 & 2 & 0 & 4 & 2\\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{array} \]
这样，我们定义了一个新的算数体系。在此体系内仅包含 6 个数字且有子集的加法和乘法定义。我们将此算数体系称为模 6 算术(modular 6 arithmetic)，并将其关联类型(associated type)记为 \(\Z_6\) 。
要了解为什么使用同余类进行模运算是有效的且可以大幅简化同余计算，让我们重新回到 示例 9 的同余方程:
\[ \kongru{7\cdot(2x+21) + 11}{x-102}{6} \]
如 示例 9 所示，同余式的运算与正常算术不同：比如，进行除法需要检查模数和被除数是否互素，并且解通常不是唯一的。
我们可以将上述同余方程通过投影到同余类(projecting onto the remainder classes)转化到 \(\Z_6\) 体系内：由于 \(\Zmod{7}{6}= 1\)、\(\Zmod{21}{6}= 3\)、\(\Zmod{11}{6}= 5\) 和 \(\Zmod{102}{6}= 0\)，我们得到下式：
$$ \begin{align*} \kongru{7\cdot(2x+21) + 11}{x-102}{6} \text{ over } \Z \\ \Leftrightarrow & 1\cdot (2x+3) + 5 = x \text{ over } \Z_6 \end{align*} $$
我们可以利用上文给出的加法和乘法表进行方程求解，就像我们求解正常方程一样：
$$ \begin{align*} 1\cdot (2x+3) + 5 &= x & \text{ }\\ 2x+3 + 5 &= x & \text{\# addition table:} 3+5 = 2 \\ 2x+2 &= x & \text{\# add 4 and $-x$ on both sides} \\ 2x+2 +4 -x &= x + 4 -x & \text{\# addition table: } 2+4 = 0 \\ x &= 4 & \end{align*} $$
正如我们所见，尽管使用同余类进行加法和乘法的规则有些陌生，但使用这种方式解决同余方程与解决正常的等式方程的过程极其类似。
我们可以使用 sage 对模 6 体系内的运算进行验证:
sage: Z6 = Integers(6)
sage: Z6(2) + Z6(5)
1
sage: Z6(7) * (Z6(2) * Z6(4) + Z6(21)) + Z6(11) == Z6(4) - Z6(102)
True
备注 2
本备注主要涉及 k位模数(k-bit modulus) 问题。
在密码学论文中，我们经常可以读到类似“[...] 使用了 4096 位模数”([. . .] using a 4096-bit modulus) 。这意味着加密系统使用的模运算的模数在二进制表示中长度位 4096 位。相反，数字 6 的二进制表示为 110，因此在 示例 11中，我们描述的是 3位模数系统。
练习 13. 将 \(\Z_{13}\) 定义为类似 示例 11 的模 13 算术体系。然后将上述同余方程在 \(\Z_{13}\) 体系内重新求解。