$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } \gdef\Zdiv#1#2{#1\ \text{div}\ #2} $$ 正如我们所致，整数可以进行加法、减法和乘法预算且运算结果仍属于整数，但是对于除法，并非如此：如\(3/2\) 就不是一个整数。为了更加抽象的角度解释这一问题，我们需要首先考虑乘法逆元的定义。当我们有一个定义有乘法的集合，并且该集合中有一个对乘法表现中性的元素(其他元素与之相乘后的结果不变)，那么我们使用以下方式定义乘法逆元(multiplicative inverses):
设 \(S\) 是可以进行 \(a \cdot b\) 乘法运算且 存在中性元素(neutral element) \(1 \in S\)的集合，对任何 \(a \in S\) 都存在 \(1 \cdot a = a\) c成立。那么对元素 \(a \in S\) 的乘法逆元 \(a^{-1}\) 定义如下:
\[ a \cdot a^{-1} = 1 \]
通俗来说，乘法逆元的定义是指它抵消了原来的元素，所以两者相乘结果为 \(1\) 。
具有乘法逆元的数特别令人感兴趣，因为它们可以定义两个数的除法。事实上，如果 \(a\) 是一个数且具有乘法逆元 \(a^{-1}\) 存在，那么我们可以定义除法为与逆元相乘：
\[ \frac{b}{a}:= b\cdot a^{-1} \]
示例 12
已知有理数集合，即 \(\Bbb{Q}\) 。对于此集合，中性元素为 \(1\) ，因为 \(1 \cdot a = a\) 对任何有理数都成立。比如\(1\cdot 4=4\)、 \(1\cdot \frac{1}{4}=\frac{1}{4}\) 和 \(1\cdot 0 =0\) 。
每个有理数 \(a\neq 0 \) 都存在乘法逆元 \(\frac{1}{a}\) 。比如，\(3\) 的乘法逆元是 \(\frac{1}{3}\)，因为 \(3\cdot \frac{1}{3}=1\)。 \(\frac{5}{7}\) 的乘法逆元是 \(\frac{7}{5}\)，因为 \(\frac{5}{7}\cdot \frac{7}{5}=1\) 。
示例 13
查看整数集合 \(\Bbb{Z}\) ，我们可以发现中性元素为数字 \(1\) 。除了数字 \(1\) 和 \(-1\) 外，没有其他整数具有乘法逆元，因为对于 \(a \cdot x = 1\) 方程在 \(a \neq 1\) 及 \(a \neq -1\) 集合内没有整数解。
乘法逆元定义有一个类似的加法的定义，称为加法逆元。在整数集合内，加法运算的中性元素为 \(0\) ，因为 \(a + 0 = a\) 对于任何整数 \(a \in \Bbb{Z}\) 均成立。加法逆元总是存在的，并且由负数 \(-a\) 给出，因为 \(a + (-a) = 0 \)。
此处注意
pull requests原仓库，原文有误
示例 14
查看 示例 11 给出的模 6 体系 \(\Bbb{Z}_6\) ，我们可以使用对应的乘法表找到乘法逆元。为此，我们需要查看每行元素并找到等于 1 的条目。如果此条目存在，这该行对应的元素存在乘法逆元，否则则不存在乘法逆元。
比如，在 \(\Bbb{Z}_6\) 中，\(5\) 的乘法逆元是 \(5\) 本身，因为 \(5 \cdot 5 = 1\) 。我们也可以发现 \(5\) 和 \(1\) 是 \(\Bbb{Z}_6\) 体系内仅有的存在乘法逆元的元素。
因为 \(5\) 存在乘法逆元，所以我们可以在 \(\Bbb{Z}_6\) 体系内进行除 5 操作。这是因为除法事实上可以被定义为与乘法逆元相乘：
\[ \frac{4}{5} = 4 \cdot 5^{-1} = 4 \cdot 5 = 2 \]
从上述例子中，我们观察到一个有趣的现象，即虽然 \(5\) 作为一个整数没有乘法逆元，但 \(5\) 在模 6 算术中存在乘法逆元。
这就提出了一个问题：在模算术体系内，哪些数字具有乘法逆元？答案是，在模 \(n\) 体系内，仅当 \(n\) 和 \(r\) 互质时，数字 \(r\) 存在乘法逆元。在这种情况下，\(gcd(n,r)=1\) ，由扩展欧几里得算法，我们可以得到 \(s\) 和 \(t\)，因此以下等式成立：
\[1 = s\cdot n + t \cdot r\]
对此等式两边同取模 \(n\)，则 \(s \cdot n\) 项消失，这说明 \(t\ \text{mod}\ n\) 是模 \(n\) 算术中 \(r\) 的乘法逆元。
示例 15
在上一个实例中，我们使用乘法表回顾了 \(\Bbb{Z}_6\) 中的乘法逆元。在现实世界中，因为模数都非常大，所以我们不可能写出乘法表。
我们尝试使用非查表的方式获得 \(2 \in \Bbb{Z}_6\) 的乘法逆元。我们观察到 \(2\) 和 \(6\) 不是互素的，因为它们存在最大公约数 \(2\) 。因此，对于 \(n=2\) 方程 \(1 = s\cdot n + t \cdot r\) 无法解出 \(s\) 和 \(t\) 。这意味着 \(2\) 在 \(\Bbb{Z}_6\) 中没有乘法逆元。
基于相同的原因， \(3\) 和 \(4\) 与 \(6\) 不互素，故也不存在乘法逆元。但是 \(5\) 是特殊的，因为 \(gcd(6,5)=1\)。为了计算 \(5\) 的乘法逆元，我们需要使用拓展欧几里得算法，计算如下：
\[ \begin{array}{c | c c l} k & r_k & s_k & t_k = \Zdiv{(r_k-s_k \cdot a)}{b} \\ \hline 0 & 6 & 1 & 0 \\ 1 & 5 & 0 & 1 \\ 2 & 1 & 1 & -1 \\ 3 & 0 & . & . \\ \end{array} \]
解得 \(s=1， t=-1\)，即 \(1 = 1\cdot 6 -1\cdot 5\) 。因此， \(-1\ \text{mod}\ 6 = 5\) 是 \(5\) 的乘法逆元。我们可以使用Sage验算：
sage: ZZ(6).xgcd(ZZ(5))
(1, 1, -1)
此时，细心的读者可能注意到模数是素数的情况是令人感兴趣的。在这种情况下，所有同余类都存在逆元，因为对于素数 \(n\) 和任何 \(r < n \)都有 \(gcd(r,n)=1)\) 成立。事实上，费马小定理也提供了一些方式在这种情况下用于计算乘法逆元，因为在素数模 \(p\) 和 \(r < p\) 条件下，我们得到：
\[
\begin{align*}
\kongru{r^p}{r}{p} & \Leftrightarrow \\
\kongru{r^{p-1} }{1}{p} & \Leftrightarrow \\
\kongru{r\cdot r^{p-2} }{1}{p}
\end{align*}
\]
这说明在素数模 \(p\) 体系中，同余类 \(r\) 的乘法逆元是 \(r^{p-2}\)
我们在 3.2.2 运算规则 中讨论了费马小定理，读者可返回查阅。
示例 16
为了发现素数模体系中的特殊性质，我们将重复 示例 11 中的过程，但在素数模 \(5\) 体系内。对于 \(p=5\) ，我们可以得到以下同余类：
\[ \begin{array}{ccc} 0: = \{\ldots, -5,0,5,10, \ldots \}\\ 1: = \{\ldots, -4,1,6,11, \ldots \}\\ 2: = \{\ldots, -3,2,7,12, \ldots \} \\ 3: = \{\ldots, -2,3,8,13, \ldots \}\\ 4: = \{\ldots, -1,4,9,14, \ldots \} \end{array} \]
根据上述同余类，我们可以得到如下加法和乘法表：
\[ \begin{array}{c | c c c c c} + & 0 & 1 & 2 & 3 & 4 \\\hline 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 \\ \end{array} \quad \quad \quad \quad \begin{array}{c | c c c c c} \cdot & 0 & 1 & 2 & 3 & 4 \\\hline 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 \\ \end{array} \]
我们可以发现 \(\Bbb{Z}_5\) 体系中的加法和乘法与 \(\Bbb{Z}_6\) 体系中有一些微小但重要的差异。特别是，我们发现在乘法表中，在任一同余类 \(r \neq 0\) 所在的行中都存在等于 1 的条目，因此这些数均具有乘法逆元。此外，若非零元素不参与运算，则乘积均不为 \(0\) 。
关于如何在乘法表内查找某个同余类是否存在乘法逆元的方法，我们亦在 示例 14 中进行了详细解释，读者可自行查阅。
基于 示例 15 中的结论，我们可以使用费马小定理对 \(\Bbb{Z}_5\) 中的元素计算乘法逆元。已知 \(3 \in \Bbb{Z}_5\) ，使用同余类计算 \(3^{5-2}=3^3=3\cdot 3\cdot 3= 4\cdot 3 = 2\) 。事实上，\(3^{-1}=2\)，因为 \(3 \cdot 2 = 1\) 在 \(\Bbb{Z}_5\) 中成立。
使用 Sage 在模 5 算术体系中进行检查：
sage: Z5 = Integers(5)
sage: Z5(3)**(5-2)
2
70sage: Z5(3)**(-1)
2
72sage: Z5(3)**(5-2) == Z5(3)**(-1)
True
示例 17
为了了解素数模体系和非素数模体系的主要区别之一，已知在 \(\Bbb{Z}_5\) 和 \(\Bbb{Z}_6\) 上定义的线性方程 \(a \cdot x + b = 0\)。因为任何非零元素在 \(\Bbb{Z}_5\) 中都存在乘法逆元，所以我们总可以在 \(\Bbb{Z}_5\) 中求解线性方程。但在 \(\Bbb{Z}_6\) 中，方程不一定有解。为证明这一点，已知方程 \(3x+3=0\) 在 \(\Bbb{Z}_5\) 中，我们有以下求解过程：
\[ \begin{align*} 3x+3 &= 0 & \text{\# add 2 and on both sides} \\ 3x+3+2 &= 2 & \text{\# addition-table: } 2+3 = 0 \\ 3x &= 2 & \text{\# divide by } 3 \text{ (which equals multiplication by 2)}\\ 2\cdot(3x) &= 2\cdot 2 & \text{\# multiplication-table: } 2\cdot 2=4 \\ x &= 4 & \end{align*} \]
在素数模体系中，我们得到了唯一解 \(x=4\) 。现在，我们考虑 \(\Bbb{Z}_6\) 中的求解过程：
\[ \begin{align*} 3x+3 &= 0 & \text{\# add 3 and on both sides} \\ 3x+3+3 &= 3 & \text{\# addition-table: } 3+3 = 0 \\ 3x &= 3 & \text{\# division not possible (no multiplicative inverse of 3 exists)} \end{align*} \]
由于 \(3\) 在 \(\Bbb{Z}_6\) 中没有乘法逆元，所以我们不能通过两边同除 \(3\) 以进行方程求解。事实上，当我们观察 \(\Bbb{Z}_6\) 的乘法表时，我们可以发现解集为 \(x \in \{1,3,5\}\) 。这些解都满足 \(3x + 3 = 0\) 。
练习 22. 考虑模数 \(n=24\) 。对于整数 \(7,1,0,805,-4255\) ，哪些数在模 24 体系内存在逆元？如果存在，请计算乘法逆元。
练习 23. 求出同余方程 \(\kongru{17(2x+5)-4}{2x+4}{5}\) 的解集。
练习 24. 求出同余方程 \(\kongru{17(2x+5)-4}{2x+4}{6}\) 的解集。