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

引理2.1 设$d$, $a$ 为整数, $d > 0$. 则存在唯一的$d$的最大倍数$dq \le a$; 它具有特征为: $dq \le a < d(q + 1)$, 或者$a = dq + r$, $0 \le r < d$.

(在这个关系中, $r$称为$a$被$d$除的余数; $d$称为除数, $q$称为商).

证明：形如$a-dz$ ($z \in \mathbb{Z}$)的整数的集合包含正整数, 因为$z$可以取绝对值足够大的负数(例如, $z = -N$, $N$为足够大的正整数). 对于所有具有上述形式的正整数应用第1节的性质(6); 取它的最小元素$r$, 写为$a – dq$: 于是$0 \le r < d$; 否则$a – d(q + 1)$属于同一个集合并且$< r$.

定理2.2 设$M$为非空的整数集, 对减法封闭. 那么存在唯一的$m \ge 0$, 使得$M$由$m$的所有倍数组成: $M = \{mz\}_{z \in \mathbb{Z}} = m\mathbb{Z}$.

证明：如果$x \in M$, 根据假设, $0 = x – x \in M$, $-x = 0 – x \in M$. 如果$y \in M$, 那么$y + x = y – (-x) \in M$, 因此$M$对于加法也是封闭的. 如果$x \in M$, $nx \in M$, 其中$n$为任意一个正整数, 于是$(n+1)x = nx + x \in M$; 于是根据归纳法, 对任意$n \ge 0$有$nx \in M$, 从而对于所有的$n \in Z$也成立. 最后, 所有的$M$中的元素的整数系数的线性组合也是$M$中的元素; $M$的这个性质可以得出$M$在加法和减法下封闭, 它和我们的假设是等价的.

如果$M = \{0\}$, 定理是成立的, 取$m = 0$即可. 否则, $M$中大于0的元素组成的集合非空; 取$m$为其中的最小元素. $m$的所有倍数全部属于$M$. 任意$x \in M$, 根据引理有$x = my + r$, $0 \le r < m$; 于是$r = x – my$也是$M$的元素.根据$m$的定义, 应该有$r = 0$, $x = my$. 因此$M = m\mathbb{Z}$. 反过来, 既然$m$是$m\mathbb{Z}$中的最小的大于0的元素, 那么当给定$M$时, $m$也将被唯一确定.

推论2.3 设$a, b, \ldots, c$为有限个整数, 则存在唯一的整数$d \ge 0$, 使得所有$a, b, \ldots, c$的整数系数的线性组合$ax + by + \cdots + cz$组成的集合是由$d$的所有倍数组成的.

证明：应用定理2.2于上述集合即可.

推论2.4 使用推论2.3同样的假设和符号, 那么$d$是每一个整数$a, b, \ldots, c$的因子, 并且这些整数的公因子也是$d$的因子.

证明：注意整数$a, b, \ldots, c$本身也是它们的线性组合组成的集合的元素. 反过来, $a, b, \ldots, c$的公因子也是它们的每一个线性组合的因子, 特别的也是$d$的因子.

定义2.5 定理2.2的推论中定义的整数$d$称为$a, b, \ldots, c$的最大公因子; 表示为$(a, b, \ldots, c)$.

既然最大公因数$(a, b, \ldots, c)$属于$a, b, \ldots, c$的线性组合的集合 (它是大于0的元素中的最小者, 除非$a, b, \ldots, c$都为0), 它就应该可以表示为如下形式

\[(a, b, \cdots, c) = ax_0 + by_0 + \cdots + cz_0\]

其中$x_0, y_0, \ldots, z_0$都是整数.

习题

1. 证明$(a, b, c) = ((a, b), c) = (a, (b, c))$.

证明：注意本书中最大公约数的定义方式, 这里应该使用这个定义来证明. 注意到$a,b,c$有对称性, 由于$(a, b) = (b, a)$后面的两个式子没有本质差别, 这里只证明第一个等式.

设$d_1 = (a, b)$, 则存在$x_0, y_0$, 使得$d = ax_0 + by_0$. 我们证明集合$A = \{ax + by + cz\}$和集合$B = \{d_1w + cz\}$是相等的, 那么根据定义等式成立.

(1) $A \subset B$, $\forall d \in A$, 则$d = ax + by + cz$, 根据$d_1$的定义(推论2.3), 应该有$ax + by = wd_1 = w(ax_0 + by_0)$, 于是有$d = ax + by + cz = wd_1 + cz \in B$.

(2) $B \subset A$, $\forall d \in B$, 则$d = d_1w + cz = (ax_0 + by_0)w + cz = awx_0 + bwy_0 + cz \in A$.

2. 证明Fibonacci数列(1, 2, 3, 5, 8, 13, \ldots, 数列中的第二项之后的每一项都是他前面的两个项之和) 中任何连续的两个项的最大公因数为1.

证明：我们首先证明: $(a, b) = (a- b, b)$. 这只要注意到$ax + by = (a-b)x + b(x + y)$.

根据Fibonacci数列的定义有: $a_{n+2} = a_{n+1} + a_n$, $a_n = a_{n+2} – a_{n+1}$, 因此

\[\begin{aligned}
(a_{n+2}, a_{n+1}) &= (a_{n+2} – a_{n+1}, a_{n+1})\\
&= (a_n, a_{n+1}) = (a_{n+1}, a_n) \\
&= \cdots = (a_2, a_1) = 1
\end{aligned}\]

3. 如果$p$, $q$, $r$, $s$为整数, 满足$ps – qr = \pm 1$, 整数$a, b, a’, b’$满足

\[a’ = pa + qb, b’ = ra + sb,\]

证明$(a, b) = (a’, b’)$ (提示: 从最后的两个方程种解出$a$, $b$).

证明：

我们对$ps – qr = 1$进行讨论, 至于$-1$的情形类似.

首先我们可以从上述两个等式求出$a$, $b$的表达式:

\[\begin{aligned}
a &= sa’ – qb’\\
b &= -ra’ + pb’
\end{aligned}\]

由此, 我们可以证明$A = \{ax + by\} = \{a’x + b’y\} = B$. 一方面:

\[\begin{aligned}
ax + by &= (sa’ – qb’)x + (-ra’ + pb’)y \\
&= a'(sx-ry) + b'(-qx + py)
\end{aligned}
\]

另一方面

\[\begin{aligned}
a’x + b’y &= (pa + qb)x + (ra + sb)y \\
&= a(px+ry) + b(qx + sy)
\end{aligned}\]

$A = B$, 因而$(a, b) = (a’, b’)$.

4. $a$, $b$为大于0的整数, 令$a_0 = a$, $a_1 = b$; 当$n \ge 1$时, $a_{n+1}$使用如下方式定义$a_{n-1} = a_nq_n + a_{n+1}$, $0 \le a_{n+1} < a_n$, $a_n > 0$.证明存在$N \ge 1$使得$a_{N + 1} = 0$, 并且$a_N = (a, b)$.

证明：只要注意到$a_0 > a_1 > a_2 > \cdots > a_n > \cdots$, 可知最多经过$a$次即可达到$a_n = 0$, 令$N = n-1$即可. 难点在于后面的结论: $a_N = (a, b)$. 这一点我们只要证明$(a_{n-1}, a_n) = (a_n, a_{n+1})$即可. 这样的话

\[(a, b) = (a_0, a_1) = (a_1, a_2) = \cdots = (a_N, a_{N+1}) = (a_N, 0) = a_N.\]

为了方便, 改变一下记号: $a =qb + r$, 然后需要证明$(a, b) = (b, r)$. 设$A = \{ax + by\}$, $B = \{bx + ry\}$.

\begin{gather*}
ax + by = (qb + r)x + by = b(qx + y) + rx \in B \\
bx + ry = bx + (a – qb)y = ay + b(x – qy) \in A
\end{gather*}

5. 使用习题4中的符号, 证明$a_n$可以表示为$ax + by$, $x$, $y$为整数, $0 \le n \le N$.

证明：使用归纳法即可. $a_0 = a \cdot 1 + b \cdot 0$, $a_1 = a \cdot 0 + b \cdot 1$, 对于$a_0 = a_1q_1 + a_2$,

\[a_2 = a_0 – a_1q_1 = a + b\cdot(-q_1).\]

假若对于小于等于$n$的$a_k$能够由$a$和$b$表示出来, $a_k = ax_k + by_k$, 那么对于$a_{n+1}$.

\[\begin{aligned}
a_{n+1} &= a_{n-1} – a_nq_n \\
&= ax_{n-1} + by_{n-1} – q_n(ax_n + by_n) \\
&= a(x_{n-1} – q_nx_n) + b(y_{n-1} – q_ny_n)
\end{aligned}
\]

$x_{n+1} = x_{n-1} – q_nx_n$, $y_{n+1} = y_{n-1} – q_ny_n$, 结论成立.

6. 使用习题4, 5的方法给出下列情形中的$(a, b)$, 以及求解$ax + by = (a, b)$:

1. a = 56, b = 35;
2. a = 309, b = 186;
3. a = 1024, b = 729.

1. $7 = (a, b) = 56 \cdot 2 – 35 \cdot 3$;
2. $3 = (a, b) = 309 \cdot (-3) + 186 \cdot 5$;
3. $1 = (a, b) = 729 \cdot 361 – 1024 \cdot 257$.

7. $a, b, \ldots, c, m$为整数, $m > 0$, 证明

\[(ma, mb, \ldots, mc) = m \cdot (a, b, \ldots, c).\]

证明：令$d = (a, b, \ldots, c)$, 则$d | a$, $d | b$, $\cdots$, $d | c$, 于是$md | ma$, $md | mb$, $\cdots$, $md | mc$, $md$是它们的公因子, 于是$md | (ma, mb, \cdots, mc)$.

$d=ax + by + \cdots + cz$, 于是$md = max + mby + \cdots + mcz$, 于是$(ma, mb, \cdots, mc) | md$.

有了上面两个整除关系可以知道$(ma, mb, \cdots, mc) = md = m(a, b, \cdots, c)$.

8. 证明每一个有理数可以表示为$\frac{m}{n}$, $(m, n) = 1$, $n > 0$, 并且这种表示方式是唯一的.

证明：所谓有理数, 是指整数的比例, 于是我们只需要证明$d = (a, b)$时, $(a/d, b/d) = 1$, 并且$m_1/n_1 = m_2 /n_2$,并且$m_i, n_i$满足题设条件时, 必有$m_1 = m_2$, $n_1 = n_2$.

利用上一题的结论$(a/d, b/d) \cdot d = (a, b) = d$, 于是$(a/d, b/d) = 1$. 至于后面部分, 我们有$m_1n_2 = m_2n_1$. 我们证明结论$d | ab$, $(a, d) = 1$, 则必有$d | b$. 证明比较简单, $(a, d) = 1$可以得出: $ax + dy = 1$, 于是$abx + dby = b$, 因此$d | b$. $m_1 | m_2n_1$, $(m_1, n_1) = 1$可知$m_1 | m_2$, 不妨设$m_2 = km_1$, 于是有$n_2 = kn_1$, 注意$n_1 > 0$, $n_2 > 0$, 因此$k > 0$, 如果$k > 1$, 那么$(m_2, n_2) = (km_1, kn_1) = k > 1$, 这与我们的假设矛盾, 因此结论成立.