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

定义5.1 交换群(Abel群)是指集合$G$, 以及$G$上的元素的二元运算, 满足以下公理(在这里把群的运算表示为$+$):

• (结合律). $(x + y) + z = x + (y + z)$, $\forall x, y, z \in G$.
• (交换律). $x + y = y + x$, $\forall x, y \in G$.
• $x, y \in G$, 方程$x + z = y$存在唯一解$z \in G$ (记$z = y – x$).
• 存在一个元素属于$G$, 称为中性元(记之为$0$), 满足$0 + x = x$, $\forall x \in G$.

举例来说, 整数集, 有理数集(以及实数集)在加法下构成交换群. 很多时候交换群的运算不一定是加法, 也就是可以不表示为$+$; 此时(III)中的$y – x$, (IV)中的$0$都应该作相应的修改. 如果这个运算以乘法表示, 那么在(III)中的$z$通常表示为$\frac{y}{x}$, 或者$y / x$, 或者$yx^{-1}$. 用1表示(IV)中的中性元. 非零的有理数在乘法下构成了一个交换群.

在本书中, 除了交换群之外, 不会出现其它的群; 因此“交换”一词通常就省略了. $G$的子集如果在同一个运算下仍旧构成一个群, 那么该子集就称为$G$的子群. 如果$G$表示为加法, $G$的子集是一个子群当且仅当它对加法和减法封闭, 甚至可以仅仅对减法封闭(参考定理2.2的证明). 定理2.2可以更加简洁地表述为$Z$的每一个子群具有形式$mZ$, $m \ge 0$.

下面给出有限群的例子.

定义5.2 $m$, $x$, $y$为整数, $m > 0$, 称$x$和$y$模$m$同余, 如果$x – y$是$m$的倍数; 可以表示为$x \equiv y (\mod m)$, 或更简洁表示为$x \equiv y(m)$.

第2章中的引理说明每一个整数必和$0, 1, \ldots, m – 1$之一, 而且只和其中的一个模$m$同余, 两个整数模$m$同余当且仅当它们除$m$的余数相同.

模$m$的同余关系具有下列性质:

• (自反性) $x \equiv x (\mod m)$;
• (传递性) 如果$x \equiv y$, $y \equiv z (\mod m)$, 则$x \equiv z (\mod m)$;
• (对称性) 若$x \equiv y (\mod m)$, 则$y \equiv x (\mod m)$.
• $x \equiv y$, $x’ \equiv y’ (\mod m)$, $x \pm x’ \equiv y \pm y’ (\mod m)$.
• $x \equiv y$, $x’ \equiv y’ (\mod m)$, $xx’ \equiv yy’ (\mod m)$.
• $d > 0$, 整除$m$, $x$和$y$;那么$x \equiv y (\mod m)$当且仅当$\frac{x}{d} \equiv \frac{y}{d} (\mod \frac{m}{d})$.

对于(E), 它是下面等式的推论

\[xx’ – yy’ = x(x’ – y’) + (x – y)y’;\]

其它结论的验证也是比较简单的.

性质(A), (B), (C)可以表述为: 模$m$同余关系是整数之间的一个等价关系.

定义5.3 整数模$m$的同余类是所有这样的整数的集合, 这些整数和某个给定的整数模$m$同余.

$x$为任一整数, 我们用$(x \mod m)$ (或更简单的$(x)$, 如果不会引起歧义的话)来表示与$x$模$m$同余的整数组成的同余类. 从(A)知$x$属于$(x \mod m)$; 它称为这个同余类的代表. 从(A), (B), (C)可知, 两个同余类$(x \mod m)$, $(y \mod m)$或者是相等的, 如果$x \equiv y (\mod m)$; 或者是不相交的(也就是说没有公共元素). 因而所有整数的集合被分成了$m$个不相交的同余类$(0 \mod m)$, $(1 \mod m)$, $\ldots$, ($m – 1 \mod m$).

我们使用如下方式定义同余类的加法:

\[(x \mod m) + (y \mod m) = (x + y \mod m);\]

这样做是允许的, 因为(D)表明等式右边仅仅依赖于左边的两个同余类, 而不依赖这些同余类的代表$x$, $y$的选择.

定理5.4 对任一整数$m > 0$, 模$m$的同余类在加法下构成一个$m$个元素的交换群.

这是显然的, 事实上, 对于给定的$x$, $y$, 方程

\[(x \mod m) + (z \mod m) = (y \mod m),\]

有唯一的解$(y – x \mod m)$, 而$(0 \mod m)$就是中性元.

习题

1. 如果$x_1, \ldots, x_m$为$m$个整数, 证明存在一个合适的非空子集, 使得这个子集中的元素的和是$m$的倍数 (提示: 考虑模$m$的由$0$, $x_1$, $x_1 + x_2$, $\ldots$, $x_1 + x_2 + \cdots + x_m$决定的不同的同余类).

证明：考虑$m$个数$y_1=x_1$, $y_2=x_1 + x_2$, $\ldots$, $y_m=x_1 + x_2 + \cdots + x_m$,如果这些数中有$m$的倍数,那么选择其中一个即可,否则,根据鸽笼原理,至少有两个数模$m$同余,不妨设为$y_i$,$y_j$,$1 \le i < j \le m$,于是数$x_i, \cdots,x_j$组成的集合满足条件.

2. 证明每一个完全平方数(参考III的习题3)和0, 1, 或者4之一模8同余.

证明：把整数按照模4同余进行讨论即可:

\begin{gather*}
(4m)^2 =16m^2 \equiv 0 \mod{8}\\
(4m+1)^2=16m^2+8m+1 \equiv 1 \mod{8} \\
(4m+2)^2=16m^2+16m+4 \equiv 4 \mod{8} \\
(4m+3)^2=16m^2+24m+9 \equiv 1 \mod{8}
\end{gather*}

结论成立.

3. 使用归纳法证明, 如果$n$是正整数, 那么

\[2^{2n + 1} \equiv 9n^2 – 3n + 2 (\mod 54).\]

证明：既然题目中已经说明使用归纳法,这里试试:

$n=1$时,$2^{2n+1}=2^3=8$,$9n^2 – 3n + 2=8$,显然有$2^{2n + 1} \equiv 9n^2 – 3n + 2 (\mod 54)$.

假设结论对于$n$成立,那么对于$n+1$来说,把$2^{2n+3}$分解并使用归纳假设有:

\[\begin{aligned}
2^{2n + 3} &= 2^{2n+1} \cdot 2^2 \equiv 4(9n^2 – 3n + 2) \\
&= 4(9n^2 – 3n + 2)-(9(n+1)^2 – 3(n+1) + 2) \\
&\ + (9(n+1)^2 – 3(n+1) + 2)\\
&= (9(n+1)^2 – 3(n+1) + 2) + (27n^2 -27n) \\
&= (9(n+1)^2 – 3(n+1) + 2) + 27n(n-1) \\
&\equiv (9(n+1)^2 – 3(n+1) + 2) \mod{54}
\end{aligned}\]

由此可知结论成立,这里使用了$2|n(n-1)$,并且$(27,2)=1$,因此必有$27n(n-1) \equiv 0 \mod{54}$.

4. 证明, 如果$x$, $y$, $z$是整数, $x^2 + y^2 = z^2$, 那么$xyz \equiv 0 (\mod 60)$.

证明：首先我们可以假设$(x,y,z)=1$.其次如果$x$,$y$为偶数,那么$z$必为偶数,因此按照我们的假设,$x$,$y$不可能都是偶数,第三,根据完全平方数模4的结果,我们可以证明$x$和$y$必然是一个为偶数,另一个为奇数.不妨设$x$为偶数,$y$为奇数,于是$z$也是奇数.如果$(x,y)=d>1$,必有$d|z$,因此在我们的假设下,必有$(x,y)=1$.

通过模8可以得到$x$必然被4整除,否则$x=4m+2$,此时和$y$为奇数进行讨论,$x^2+y^2\equiv5\mod{8}$,此时不可能是完全平方数.另一个思路,展开:

\begin{gather*}
x_1^2 + y_1^2 + y_1=z_1^2+z_1 \\
x_1^2=(z_1-y_1)(z_1+y_1+1)
\end{gather*}

而$z_1-y_1$和$z_1+y_1$有相同的奇偶性,因此$z_1-y_1$和$z_1+y_1+1$至少有一个偶数,于是$2|x_1^2$,$2|x_1$,因此$4|x$.于是必有$4|xyz$.

通过模3的讨论,我们证明$3|x$和$3|y$至少有一个成立.首先在于整数的完全平方数模3的余数只能是0和1.如果3无法整除$x$和$y$,那么$x^2+y^2\equiv2\mod{3}$,不可能.因此必有$3|xyz$.

通过模5的讨论,我们证明它必有$5|x$,$5|y$,$5|z$至少有一个成立,从而$5|xyz$.首先是整数的完全平方数模5的余数只能是0,1和4.如果$5|x$和$5|y$都不成立,那么$x^2$和$y^2$模5的余数只能是$1$和$4$,但是两者不能同余,如果同余,此时$x^2+y^2$模5的余数或者是2,或者是3,都不可能让$z$成为完全平方数,于是两者不同余,此时$5|(x^2+y^2)=z^2$,$5|z$

综合上述的讨论,并注意到3,4,5两两互素,可知$3\cdot4\cdot5=60|xyz$.

5. $x_0, x_1, \ldots, x_n$是整数, 证明

\[x_0 + 10x_1 + \cdots + 10^nx_n \equiv x_0 + x_1 + \cdots + x_n (\mod 9).\]

证明：这个问题极为简单,原因在于$10^k \equiv 1 \mod{9}$,这是所谓弃九法的依据.使用这个方法就很容易判断一个整数能否被9整除.关于$10^k \equiv 1 \mod{9}$的证明,可以使用归纳法或者二项式定理完成,$10^k = (9 + 1)^k$.

6. 证明: 同余组$x \equiv a (\mod m)$, $x \equiv b (\mod n)$有一个解的充分必要条件是$a \equiv b (\mod d)$, 其中$d = (m, n)$. 如果$d = 1$, 证明这个解模$mn$唯一.

证明：如果同余组有解,那么有$m|(x-a)$,$n|(x-b)$,于是$x-a=ma_1$,$x-b=nb_1$,$a-b=nb_1-ma_1$,显然有$d|(a-b)$,也就是$a \equiv b \mod{d}$.

反之,如果$a \equiv b \mod{d}$,那么$d|(a-b)$,$a-b=kd$.另一方面,$d=(m,n)$,那么存在$u$,$v$使得$d=mu+nv$,于是$kmu+knv=a-b$,令$x=-kmu+a=knv+b$.显然$x$满足同余组.也就是同余组有解.

如果$d=1$,设$x_1$和$x_2$都是同余组的任意两个解,我们需要证明$x_1 \equiv x_2 \mod{mn}$.只要注意到此时有$x_1 \equiv x_2 \mod{m}$和$x_1 \equiv x_2 \mod{n}$.当$d=1$时,有$x_1 \equiv x_2 \mod{mn}$.它只是前面出现过的一个习题的另一种表示方式:如果$(m,n)=1$,$m|c$,$n|c$,必有$mn|c$.这里的$c=x_1-x_2$.

7. $n$是大于0的整数, 证明前面的$2n$个整数中的任意$n + 1$个整数包含两个数$x$, $y$, 使得$\frac{y}{x}$是2的幂 (提示: 对于任意给定的整数$x_0, x_1, \ldots, x_n$, 令$x_{i}^{‘}$为$x_i$的最大的奇因子, 证明它们之中至少有两个是相等).

证明：

首先应该注意前面$2n$个整数中只有$n$个奇数,其次,每一个整数都可以表示为$2^ka$的形式,这里$a$为奇数,那么对于任意的$n+1$个数$x_0, x_1, \ldots, x_n$来说,上述表达式的奇数部分最多只有$n$个,因此至少有两个的奇数部分相等,不妨假设$x_i$和$x_j$的奇数部分都是$a$,即$x_i=2^ka$,$x_j=2^la$,那么令$x$为两者之中较小的一个,$y$为较大的一个即可.

8. 对于任意的$x$, $y$是大于0的整数, 记$x \sim y$如果$\frac{y}{x}$为2的幂, 也就是为$2^n$, $n \in Z$; 证明这是一个等价关系, $x \sim y$当且仅当$x$的奇因子和$y$的奇因子是相同的.

证明：

等价关系主要是三个关系:自反性,对称性,传递性.

自反性:$\frac{x}{x} = 1 = 2^0$,因此$x \sim x$;

对称性:$x \sim y$意味着$\frac{y}{x} = 2^n$,于是$\frac{x}{y}=2^{-n}$,$-n \in Z$,因此$y \sim x$.

传递性:$x \sim y$,$y \sim z$,这意味着$\frac{y}{x}=2^n$,$\frac{z}{y}=2^m$,于是$\frac{z}{x} = \frac{z}{y}\cdot\frac{y}{x}=2^m\cdot2^n=2^{m+n}$,因此$x \sim z$.

如果$x$与$y$有相同的奇因子,那么最大的奇因子也是相同的,假设都是$a$,于是应该有$x=2^na$,$y=2^ma$,$\frac{y}{x}=2^{m-n}$,$x \sim y$.

反之,如果$x \sim y$,那么$y = 2^nx$,如果$n < 0$,我们考虑$x = 2^{-n}y$,两者没有实质性差别.于是如果奇数$a|x$,显然有$a|y$,反之如果$a|y$,那么由于$(a,2^n)=1$,于是$a|x$,因此他们的奇因子相同.