这是我在学习韦伊的《Number Theory For Beginners》的一个翻译。全文十三章，这里分十三篇文章给出！
定义3.1 整数$a$, $b$, $\ldots$, $c$称作是互素的, 如果他们的最大公因数为1.
换句话说, 它们是互素的如果它们没有大于1的公因子.
如果整数$a$, $b$是互素的, 那么就称$a$对于$b$不可约, $b$对于$a$不可约, 而且, $a$的每一个因子对于$b$不可约, $b$的每一个因子对于$a$不可约.
定理3.2 整数$a, b, \ldots, c$是互素的当且仅当方程$ax + by + \cdots + cz = 1$存在整数解$x, y, \ldots, z$.
事实上, 如果$(a, b, \ldots, c) = 1$, 根据定理2.2的推论2.3, 方程有解. 反过来, 如果方程有解, 那么每一个$a, b, \ldots, c$的公因子$d > 0$必然整除1, 因而必然是1.
推论3.3 如果$d$是整数$a, b, \ldots, c$的最大公因数, 那么$\frac{a}{d}, \frac{b}{d}, \ldots, \frac{c}{d}$是互素的.
这一点立刻可以由这样一个事实得到: $d$可以表示为$ax_0 + by_0 + \cdots cz_0$.
定理3.4 如果$a$, $b$, $c$为整数, $a$和$b$互素, 并且可以整除$bc$, 那么$a$整除$c$.
既然$(a, b) = 1$, 我们有$ax + by = 1$. 于是有
\[c = c(ax + by) = a(cx) + (bc)y.\]
而$a$可以整除右边的每一项, 因而也整除$c$.
推论3.5 如果$a$, $b$, $c$为整数, $a$分别与$b$, $c$互素, 那么$a$与$bc$互素.
令$d$为$a$和$bc$的正的公因子, 它和$b$互素(因为它整除$a$), 根据定理3.4, $d$必然整除$c$, 而$(a, c) = 1$, $d$等于1.
推论3.6 如果一个整数和$a, b, \ldots, c$中的每一个整数互素, 那么它也和这些数的乘积互素.
这可以通过对乘积的因子个数进行归纳得到.
习题
1. 如果$(a, b) = 1$, $a$和$b$整除$c$, 证明$ab$整除$c$.
证明：从$(a, b) = 1$,存在整数$x$,$y$,满足$1 = ax + by$,于是$c = acx + bcy$,注意到$ab | ac$,$ab | bc$,因此$ab | c$.
另一个方法是: $a | c$,说明$c = aa_1$,根据$b | c$,可知$b|aa_1$, 而$(a,b)=1$,从而$b|a_1$, 因此$a_1=bb_1$,$c=aa_1=abb_1$,$ab|c$.
2. $m > 1$, $a$和$m$互素, 证明: $m$除$a, 2a, \ldots, (m – 1)a$得到的余数为$1, 2, \ldots, m – 1$的某个排序.
证明：注意到$a, 2a, \ldots, (m-1)a$一共有$m-1$个数, 我们只要证明这些数中的任意两个数的余数不相同, 并且不会出现余数为0的情形, 那么结论成立.
首先$m$不整除$ka$, 这里$1 \le k \le m-1$, 如果$m | ka$, 由于$(m, a) = 1$, 于是$m|k$, 这是不可能的.
其次, 如果$ka$和$la$除以$m$的余数相同, 这里$1 \le k < l \le m-1$, 那么就有$m | (l-k)a$, 根据第一步证明的, 这是不可能的.
3. 证明: $N > 0$为整数, $N$或者是完全平方数(即可以表示为$n^2$, 这里$n$为大于0的整数), 或者$\sqrt{N}$不是有理数 (提示: 利用习题2.8}).
证明：假设$N$不是完全平方数, 我们证明$\sqrt{N}$不是有理数.
假设$\sqrt{N}$是有理数, 于是存在$m, n > 0$, $(m, n) = 1$, $\sqrt{N} = m/n$, 两边平方, $N = m^2/n^2$,于是有
\[n^2N = m^2,\]
从$(m, n) = 1$可知$(m^2, n^2) = 1$, 于是$m|N$, $m^2|N$, 不妨设$N=m^2m_1$, 于是有
\begin{gather*}
n^2m^2m_1 = m^2 \\
n^2m_1 = 1
\end{gather*}
由此得到$n=1$, $m_1 = 1$, 这与$N$不是完全平方数矛盾.
4. 任何大于1的不是2的幂的整数可以表示为两个或者更多个连续整数的和.
证明：首先每一个数$N > 1$都可以表示为$N = 2^ma$的形式, 这里$m \ge 0$,$a$为奇数. 根据题设, 应该是$a \ge 3$, 我们假设他能够表示成d个连续整数$b, b+1, \cdots, b + d – 1$的和, 则
\[2^ma = \frac{(b+d)(b+d-1)}{2} – \frac{b(b-1)}{2} = \frac{d(2b-1+d)}{2},\]
转化一下:
\[d(2b-1 + d) = 2^{m+1}a\]
注意到$d$与$2b-1+d$必然是一个为奇数, 另一个为偶数, 如果$a < 2^{m+1} + 1$, 那么令$d = a$, 此时$2b-1+d = 2^{m+1}$, $b = \frac{2^{m+1}+1-a}{2}$, 否则令$d = 2^{m+1}$, $b = \frac{a + 1 – 2^{m+1}}{2}$. 容易验证这是成立的, 并且$a \ge 3$, $2^{m+1} \ge 2$. 因此数量个数至少为2.
5. $a$, $b$为正整数, $(a, b) = 1$, 证明每一个$\ge ab$的整数可以表示为$ax + by$的形式, $x$, $y$为正整数.
证明：从$(a, b) = 1$,存在$ax + by = 1$.问题在于找到方程$n = ax + by$的正整数解,这里$n \ge ab$, 华罗庚的《数论导引》中有一个更强的结论$n > ab – a – b$.
首先根据前面讨论, 方程必然有解. 不妨设$x_0, y_0$是其中一个解, 则方程的所有解可以表示成如下形式:
\[\left.\begin{cases}
x = x_0 + bt \\
y = y_0 – at
\end{cases}\right. t \in Z,\]
我们需要证明它有正整数解. 为此我们需要选择合适的$t \in Z$.
首先选择$t$使得, $0 \le y_0 – at < a$, 这是可能的, 这实际上是带余除法的一个应用, 我们说这个$t$能够使得$x = x_0 + bt > 0$,因为此时$0 \le by_0 – abt \le ab$
\[(x_0 + bt)a = ax_0 + abt > by_0 – ab + ax_0 = n – ab \ge ab – ab = 0\]
获证. 这里注意的是本书中$0$包含在正整数之中.
6. 利用习题3.5, 对$m$使用归纳法, 证明, 如果$a_1, a_2, \ldots, a_m$是正整数, $d = (a_1, a_2, \ldots, a_m)$, $d$的足够大的倍数可以表示为$a_1x_1 + a_2x_2 + \cdots + a_mx_m$的形式, 这里$x_i$都是正整数.
证明：对于$m=2$, 对$a_1/d$和$a_2/d$应用上一道题目, 则当$N \ge (a_1a_2)/d$时, $ax + by = N$存在正整数解. 至于$m+1$来说,
\[d= ((a_1, \cdots, a_m), a_{m+1})\]
令$d_1 = (a_1, \cdots, a_m)$, 对于足够大的$Kd_1$, 存在正整数$x_i$, 使得$a_1x_1 + \cdots + a_mx_m = Kd_1$, 对于足够大的$Md$, 存在正整数$y_1, y_2$使得, $d_1y_1 + a_{m+1}y_2 = Md$, 当$Nd \ge Kd_1 + Md$时, 我们来看看是否存在正整数解. 首先对于任意的$Nd$, 考虑$Nd-Kd_1 \ge Md$, 存在正整数$y_1, y_2$, 使得$d_1y_1 + a_{m+1}y_2 = Nd – Kd_1$, 而对于$(y_1 + K)d_1$来说, 存在正整数$x_i$, 使得$\sum{a_ix_i} = (y_1 + K)d_1$, 于是有$\sum{a_ix_i} = Nd$, 这里$x_{m+1} = y_2$. 获证. 对于这道题目, 只需要找到这个$Nd$, 它不一定是满足条件的最小整数.