这是我在学习韦伊的《Number Theory For Beginners》的一个翻译。全文十三章，这里分十三篇文章给出！

设$m$为大于0的整数, 我们定义同余类的乘法如下

\[(x \mod m) \cdot (y \mod m) = (xy \mod m);\]

事实上, 第5章中的性质(E), 表明等式的右边仅仅依赖于左边的两个同余类, 而不依赖于它们的代表$x$, $y$的选择.

定义6.1 环是集合$R$以及集合上的两个二元运算, 加法(记为$+$)和乘法(记为$\cdot$或者$\times$), 并且满足下列公理:

• 在加法下, $R$为一个群.
• 乘法是结合的, 交换的, 以及对加法满足分配律: $(xy)z = x(yz)$, $xy = yx$, $x(y + z) = xy + xz$, $\forall x, y, z$.

如果$R$是一个环, 根据分配律

\[(x \cdot 0) + (xz) = x(0 + z) = xz,\]

依据加法群的性质, 有$x \cdot 0 = 0$. 类似的有$x \cdot (-y) = -xy$.

如果$R$中包含一个元素$e$满足对于任意$x$成立$ex = x$, 那么它是唯一的; 因为, 如果$f$也满足条件, 那么$ef = f$, $ef = fe = e$. 这样的元素称为单位元, 通常记为$1_R$或者$1$; 一个环称作是幺环如果它包含一个单位元.

整数集, 有理数集都是幺环.

定理6.2 对任意大于0的整数$m$, 模$m$的同余类在加法和乘法下, 构成一个$m$元的幺环.

很容易验证这个结论. 单位元就是同余类$(1 \mod m)$; 这个同余类我们将记为1, 用0来表示同余类$(0 \mod m)$; 我们有$1 \neq 0$, 除非$m = 1$. $m = 6$的情形表明在幺环中, 即使$x$和$y$都不为0, 也可能成立$xy = 0$ (分别取$x$, $y$为2的模6同余类和3的模6同余类); 在这种情况下$x$, $y$称为零因子. 环$Z$和$Q$中没有零因子.

如果$a$与$m$互素, $a’ = a + mt$, 那么$a’$和$m$的每一个公因子必然整除$a = a’ – mt$; 这表明同余类$(a \mod m)$中的所有整数都和$m$互素. 此时称这个同余类和$m$互素. 如果$(a \mod m)$, $(b \mod m)$都和$m$互素, 根据定理3.4的推论1表明$(ab \mod m)$也和$m$互素; 特别的, 模$m$的同余类环中这样的同余类不可能为零因子.

定理6.3 令$m$, $a$, $b$为整数, $m > 0$; $d = (a, m)$. 同余式$ax \equiv b (\mod m)$或者恰好有$d$个解模$m$, 或者没有解; 它有一个解当且仅当$b \equiv 0 (\mod d)$; 恰好有$\frac{m}{d}$个不同的$b$模$m$满足这个情况.

事实上, $x$为一个解当且仅当存在整数$y$使得$ax – b = my$, 即$b = ax – my$; 由定理2.2的推论1, 这个方程有解当且仅当$d$整除$b$, 即$b = dz$; 我们可以通过分别令$z$取$0, 1, \ldots, \frac{m}{d} – 1$而得到$b$的模$m$不同的值. 如果$x$为$ax \equiv b(\mod m)$的解, 那么$x’$也是方程的解当且仅当$a(x’ – x) \equiv 0 (\mod m)$; 由同余的性质(F), 它等价于$\frac{a}{d}(x’ – x) \equiv 0 (\mod \frac{m}{d})$, 于是根据定理3.4和定理3.2的推论有$x’ \equiv x (\mod \frac{m}{d})$. 这表明$ax’ \equiv b (\mod m)$的所有的解可以被表示为$x’ = x + \frac{m}{d}u$; 通过令$u$分别取$0, 1, \ldots, d – 1$可以得到模$m$的不同的解.

推论6.4

与$m$互素的模$m$同余类在乘法下构成一个群.

这一点可以在定理3.4的推论1, 定理6.3, 以及下面的事实获得: 同余类$(1 \mod m)$为模$m$同余类环的乘法的中性元.

定义6.5 对任意大于0的整数$m$, 与$m$互素的模$m$同余类的个数记为$\varphi(m)$, $\varphi$称为Euler函数.

于是, 我们有

\[\varphi(1) = \varphi(2) = 1, \varphi(3) = \varphi(4) = 2, \varphi(5) = 4, \text{等等}.\]

如果$m \ge 2$, $\varphi(m)$也可以定义为与$m$互素的并且小于等于$m – 1$的正整数的个数. 如果$p$是素数, $\varphi(p) = p – 1$.

定义6.6 一个域是这样的一个环, 它的非零元素在乘法下构成一个群.

有理数环$Q$是一个域; 整数环$Z$不是域. 域中不存在零因子; 例子$Z$表明反过来是不成立的.

定理6.7 对任意整数$m > 1$, 模$m$同余类环是一个域当且仅当$m$是一个素数.

如果$m$是素数, 除了$0$之外的所有的模$m$同余类都是和$m$互素的, 因而根据定理6.3的推论可知构成一个乘法群, 另一方面, 如果$m$不是素数, 它有一个因子$d$, $1 < d < m$; 从而$1 < \frac{m}{d} < m$, 因而同余类$(d \mod m)$, $(\frac{m}{d} \mod m)$不为0, 然而它们的乘积为0. 因此它们是零因子, 因而模$m$环不是一个域.

如果$p$是素数, 模$p$的同余类域将被记为$\mathbb{F}_p$; 它包含$p$个元素.

习题

1. 设$F(X)$是整系数多项式, 如果$x \equiv y (\mod m)$, 那么$F(x) \equiv F(y) (\mod m)$.

证明：利用$x_1 \equiv y_1 (\mod m)$,$x_2 \equiv y_2 (\mod m)$时有$x_1x_2 \equiv y_1y_2 (\mod m)$,以及归纳法即可证明.

这是上一节中的结论的简单应用.

2. 解同余方程组

\[5x – 7y \equiv 9 (\mod 12), 2x + 3y \equiv 10 (\mod 12);\]

证明解对于模12是唯一的.

和普通的线性方程组有点类似,只是需要注意模12.

3. 对所有的$a$和$b$模2, 解

\[x^2 + ax + b \equiv 0 (\mod 2).\]

首先注意到$x^2 \pm x \equiv 0$.

如果$a \equiv 1$,那么此时只有在$b \equiv 0$时有解(此时任意$x$都满足方程),其余时候无解.下面可以假设$a \equiv 0$.此时有

\[x^2 + ax + b \equiv x^2 + b = x^2+x -x+b \equiv x-b \equiv 0,\]

因此方程的解为$x \equiv b(\mod{2})$.

4. 解$x^2 – 3x + 3 \equiv 0 (\mod 7)$.

5. 设$m > 1$, 证明所有小于$m$的和$m$互素的正整数的算术平均值为$\frac{m}{2}$.

证明：只要注意到$a$和$m$互素的时候,$m-a$也与$m$互素,假设$a_1$,$\cdots$,$a_r$是所有满足条件的整数,那么$m-a_1$,$\cdots$,$m-a_r$同样是所有满足条件的整数,求和得到

\[\sum_{1}^{r}{a_i} = \frac{mr}{2},\]

于是所求的算术平均值是$m/2$.

6. 设$m$为奇数, 证明

\[1^m + 2^m + \cdots + (m – 1)^m \equiv 0 (\mod m).\]

证明：这只需要注意到$(m-k)^m \equiv (-k)^m = -k^m(\mod{m})$即可.两两分组.

7. $m$, $n$为大于0的整数, $(m, n) = 1$, 证明$\varphi(mn) = \varphi(m) \varphi(n)$ (提示: 使用习题5.6).

证明：需要使用前面证明过的结论:$(m,n)=1$,同余组$x \equiv a(\mod m)$和$x \equiv b(\mod n)$有解,并且在模$mn$下唯一.

有了这个结论,可以这样来证明:对于每一个与$m$互素的$a$和与$n$互素的$b$，都存在唯一的一个与$mn$互素的$x$,并且不同的$a$和$b$的组合,对应不同的$x$.反证即可,如果不同的$a$和$b$组合,对应到了同一个$x$,将会发生矛盾.即$m|(x-a_1)$,$m|(x-a_2)$,于是$m|(a_1-a_2)$,也就是$a_1 \equiv a_2(\mod{m})$.

反过来,由于当$(x,mn)=1$时,必有$(x,m)=1$和$(x,n)=1$.因此对于每一个与$mn$互素的$x$,必然对应与$m$互素的$a$和与$n$互素的$b$,显然一个$x$只能属于一个模$m$或者$n$的同余类.

有了上述一一对应,根据乘法原理应该有$\varphi(m)\varphi(n) = \varphi(mn)$.

8. 证明: $m > 1$, $p, q, \ldots, r$为$m$的所有的素因子, 那么有

\[\varphi(m) = m \big{(} 1 – \frac{1}{p} \big{)} \big{(} 1 – \frac{1}{q} \big{)} \cdots \big{(} 1 – \frac{1}{r} \big{)}.\]

证明：这将需要使用上一道题目的结论以及算术基本定理.首先要求出$p$为素数的时候,$\varphi(p^r)$的值,这里$r \ge 1$,我们发现除了$p$,$2p$,$\cdots$,$p^{r-1}p$和$p^r$不是互素之外,其余所有小于$p^r$的正整数都和$p^r$互素,因此$\varphi(p^r) = p^{r} – p^{r-1} = p^{r}(1 – 1/p)$.

根据算术基本定理有$m=p^{\alpha}q^{\beta}\cdots r^{\gamma}$,于是

\[\begin{aligned}
\varphi(m) &= \varphi(p^{\alpha}) \cdot \varphi(q^{\beta}) \cdots \varphi(r^{\gamma}) \\
&= p^{\alpha}(1 – \frac{1}{p}) \cdot q^{\beta}(1 – \frac{1}{q}) \cdots r^{\gamma}(1 – \frac{1}{r}) \\
&= m(1 – \frac{1}{p})(1 – \frac{1}{q})\cdots(1 – \frac{1}{r}).
\end{aligned}\]

获证.

9. $p$为任意素数, 利用二项式定理并对$n$使用归纳法证明: 对所有整数$n$成立$n^p \equiv n (\mod p)$.

证明：这里只是给出递推部分:

\[n^p = (n-1+1)^p \equiv (n-1)^p + 1 \equiv n-1+1=n.\]

10. $p$为任意素数, $n \ge 0$, 对$n$使用归纳法证明: 如果$a \equiv b (\mod p)$, 那么$a^{p^n} \equiv b^{p^n} (\mod p^{n + 1})$.

证明：这里只要注意到如果$A \equiv B$,必有

\[\sum_{0}^{p-1}{A^kB^{p-1-k}} \equiv 0\]

和展开式$A^p-B^p = (A-B)(\sum_{0}^{p-1}{A^kB^{p-1-k}})$即可.

11. $p$为奇素数, $x^2 \equiv y^2(\mod p)$, 证明$x$或者和$y$模$p$同余, 或者和$-y$模$p$同余, 但是两者不能同时成立, 除非$p$整除$x$和$y$; 因此$x^2 \equiv a (\mod p)$恰好对于$1, 2, \ldots, p – 1$中的一半的整数$a$存在解$x$.

证明：这里使用域的知识,当$p$为素数时,模$p$的同余类组成一个域,而$x^2 \equiv y^2(\mod{p})$等价于$(x-y)(x+y) \equiv 0(\mod{p})$,那么当$p$不整除$x$或者$y$时,只能有$x-y \equiv 0$或者$x+y \equiv 0$,如果两者同时成立,由于$p$是奇素数,将会得到$x \equiv 0$和$y \equiv 0$同时成立.

由此结论,把$a$分成三部分,一部分只有一个元素$a \equiv 0$,其余的两部分拥有相等的数量,也就是说对于$a$来说,如果$x^2 \equiv a$有解,$x^2 \equiv -a = p-a$必然无解.

12. 证明形如$x + y \sqrt{2}$ ($x$, $y$为整数)的数组成一个环; 如果$x$, $y$取遍所有的有理数, 它们组成一个域.

这个只是验证环和域的各个条件,这里不讨论了,注意到$0=0+0\sqrt{2}$和$1=1+0\sqrt{2}$即可.