这是我在学习韦伊的《Number Theory For Beginners》的一个翻译。全文十三章，这里分十三篇文章给出！
定义4.1 整数$p > 1$称为素数, 如果它除了自己和1之外没有其它的正因子.
每一个大于1的整数至少有一个素因子, 也就是它的最小的大于1的因子. 如果$a$为整数, $p$是素数, 那么$p$或者整除$a$, 或者和$a$互素.
定理4.2 如果一个素数整除某些整数的乘积, 那么它必然整除至少其中一个因子.
否则, 它将和所有的因子互素, 于是根据定理3.4的推论3.6, 它和这些数的乘积也是互素的.
定理4.3 每一个大于1的整数可以表示为素数的乘积; 如果不考虑因子的顺序, 这个表示方式还是唯一的.
设$a > 1$; 令$p$为$a$的素因子. 如果$a = p$, 定理成立, 否则, $1 < \frac{a}{p} < a$; 如果定理中的第一个结论对于$\frac{a}{p}$成立, 那么对于$a$也成立. 对$a$使用归纳法, 即可得出结论成立.
第二个结论可以通过归纳法加以证明. 假设$a$可以以两种方式表示为素数的乘积, 即$a = pq \ldots r$和$a = p’q’ \ldots s’$; $p$整除$a$, 定理4.2表明$p$必整除素数$p’, q’, \ldots s’$之一, 假设为$p’$, 那么$p = p’$; 对$\frac{a}{p}$应用定理的第二部分, 我们可以证明除了顺序之外, $q’, \ldots, s’$和$q, \ldots, r$一样的. 根据归纳原理, 就可以证明第二部分结论.
下面给出第二个证明. 把$a$表示为素数的乘积, $a = pq \ldots r$; 令$P$为任一素数; $n$为$P$在$a$的因子$p, q, \ldots, r$中出现的次数. 即$a$是$P^n$的倍数; 另一方面, 由于$a \cdot P^{-n}$是不等于$P$的素数的乘积, 由定理4.2, 它不是$P$的倍数, 因而$a$不是$P^{n + 1}$的倍数. $n$可以唯一确定: $n$是满足$P^n$整除$a$的最大整数; 我们使用$n = \upsilon_{P}(a)$来表示. 于是, 任意的两种把$a$表示为素数乘积的方式中, 必然包含相同的素数, 以及相同的次数; 这再一次证明了我们的定理的第二个结论.
2是素数; 它是唯一的偶素数, 所有其它的素数都是奇数. 前十个素数为
\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29.\]
设$p_1 = 2, p_2, p_3, \ldots$是所有的素数, 以它们的自然顺序(递增)排列. 令$a$为任一$\ge$1的整数, 对每一个$i \ge 1$, 在把$a$表示为素数乘积的时候, $\alpha_i$为$a$的素因子中的$p_i$的次数(如果$p_i$不能整除$a$, 则令$\alpha_i = 0$). 于是我们有
\[a = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_r^{\alpha_r}\]
这里$r$足够大(也就是说$a$的所有的素因子都在$p_1, p_2, \ldots, p_r$之中).
定理4.4 存在无限多的素数.
事实上, 如果只有有限个素数$p, q, \ldots, r$, 那么$pq \ldots r + 1$的素因子显然不等于$p, q, \ldots, r$中的任意一个. (这是Euclid的证明, 其它的证明方法可以参考习题).
习题
1. $n$为大于等于1的整数, $p$是素数. 对于任意的有理数$x$, 我们用$[x]$表示小于或者等于$x$的最大整数, 证明使得$p^N$整除$n!$的最大整数$N$可以由下式给出
\[N = \big{[}\frac{n}{p}\big{]} + \big{[}\frac{n}{p^2}\big{]} + \big{[}\frac{n}{p^3}\big{]} + \cdots\]
证明：首先$[\frac{n}{m}]$表示的是不超过$n$的正整数中$m$的倍数的个数.
\[\frac{n}{m} – 1 < [\frac{n}{m}] \le \frac{n}{m},\]
如果我们用$A_k$表示$1$到$n$之间的$p^k$的倍数组成的集合,那么有$A_{k+1} \subset A_{k}$,如果用$|A_k|$表示集合中元素个数,那么$|A_k| = [n/p^k]$,并且有结论,能被$p^k$整除但不能被$p^{k+1}$整除的数的个数应该是$|A_k|-|A_{k+1}|$.这样$n!$中$p$的因子的个数(N)等于
\[\sum_{k=1}^{\infty}{k(|A_k| – |A_{k+1}|)},\]
注意到一定程度之后必有$[n/p^k]=0$,把上式展开即可得到结论.
2. 证明, $a, b, \ldots, c$为大于等于1的整数, 那么
\[\frac{(a + b + \cdots + c)!}{a!b! \cdots c!}\]
是整数. (提示: 使用习题4.1}, 证明每一个素数在分子中的次数不小于它在分母中的次数.)
证明：根据上一道题目,我们考察每一个素数$p$在分子分母中的次数,在分子中的次数为
\[\sum{[\frac{a+b+\cdots+c}{p^k}]},\]
在分母中的次数为
\[\begin{aligned}
&\sum{[\frac{a}{p^k}]} + \sum{[\frac{b}{p^k}]} + \cdots + \sum{[\frac{c}{p^k}]} \\
&\ = \sum{([\frac{a}{p^k}] + [\frac{b}{p^k}] + \cdots + [\frac{c}{p^k}])},
\end{aligned}\]
我们只要证明结论
\[[\frac{a+b}{m}] \ge [\frac{a}{m}] + [\frac{b}{m}]\]
即可.而它是成立的,因为
\[[\frac{a}{m}] \le \frac{a}{m}, \quad [\frac{b}{m}] \le \frac{b}{m}\]
于是$[\frac{a}{m}] + [\frac{a}{m}] \le \frac{a+b}{m}$,而$[\frac{a+b}{m}]$是不超过$\frac{a+b}{m}$的最大整数,所以前面的不等式成立.
3. $a$, $m$, $n$为正整数, $m \neq n$, 证明$a^{2^m} + 1$和$a^{2^n} + 1$的最大公因数或者是1, 当$a$为偶数时; 或者是2, 当$a$为奇数时(提示: 使用这样一个事实, 当$n > m$时, $a^{2^n} – 1$是$a^{2^m} + 1$的倍数). 并依据此推出存在无限多的素数.
证明：
这里需要一个结论:
\[(a,b) = (a – kb,b),\]
$m \neq n$,我们不妨设$m>n$,那么根据提示有
\[(a^{2^m}+1, a^{2^n}+1)=(a^{2^m}+1-(a^{2^m}-1), a^{2^n}+1)=(2, a^{2^n}+1),\]
当$a$为偶数的时候,$a^{2^n}+1$为奇数,最大公约数为1,否则为偶数,最大公约数等于2.
后一个结论可以这样来证明:我们直接取$a=2$,那么序列
\[\{2^{2^n}+1\}\]
任意两个数都是互素的.那么他们的素因子也是互不相同的,因此素数必然有无限多个.
4. 如果$a = p^{\alpha}q^{\beta} \cdots r^{\gamma}$, $p, q, \ldots, r$为不同的素数, $\alpha, \beta, \ldots, \gamma$是正整数, 证明$a$的不同的因子(包括$a$和1)的个数是
\[(\alpha + 1)(\beta + 1) \cdots (\gamma + 1),\]
它们的和为
\[\frac{p^{\alpha + 1} – 1}{p – 1} \cdot \frac{q^{\beta + 1} – 1}{q – 1} \cdots \frac{r^{\gamma + 1} – 1}{r – 1}.\]
证明：我们需要结论:$a$的每个因子由乘积给出
\[p^{\alpha_1}q^{\beta_1} \cdots r^{\gamma_1},\]
这里$0 \le \alpha_1 \le \alpha$,$0 \le \beta_1 \le \beta$,$0 \le \gamma_1 \le \gamma$.使用组合学的乘积原理可知不同的因子的个数就是
\[(\alpha + 1)(\beta + 1) \cdots (\gamma + 1).\]
它们的和等于
\[\begin{aligned}
&\ \sum_{\alpha_1,\beta_1,\gamma_1}{p^{\alpha_1}q^{\beta_1} \cdots r^{\gamma_1}} \\
&= \sum_{\beta_1,\gamma_1}{q^{\beta_1} \cdots r^{\gamma_1} \sum_{\alpha_1}{p^{\alpha_1}}} \\
&= \sum_{\alpha_1}{p^{\alpha_1}} \cdot \sum_{\beta_1}{q^{\beta_1}} \cdots \sum_{\gamma_1}{r^{\gamma_1}} \\
&= \frac{p^{\alpha + 1} – 1}{p – 1} \cdot \frac{q^{\beta + 1} – 1}{q – 1} \cdots \frac{r^{\gamma + 1} – 1}{r – 1}.
\end{aligned}\]
5. 证明, 如果$D$是$a$的不同的因子的个数, 这些因子的乘积为$a^{D/2}$.
证明：令$A = \{a_1,a_2,\cdots,a_D\}$为$a$的不同的因子的集合,只要注意到
\[B=\{\frac{a}{a_1},\frac{a}{a_2},\cdots,\frac{a}{a_D}\}\]
恰好也遍历了$a$的不同的因子,那么就有素因子乘积的平方等于
\[\prod{(a_i \cdot \frac{a}{a_i})} = a^D\]
结论成立.
6. $n, a, b, \ldots, c$为大于1的整数, 不大于$n$的具有形式$a^{\alpha}b^{\beta} \cdots c^{\gamma}$的不同的数的个数满足
\[\le (1 + \frac{\log{n}}{\log{a}})(1 + \frac{\log{n}}{\log{b}}) \cdots (1 + \frac{\log{n}}{\log{c}}).\]
使用这个结论, 以及
\[\lim_{n \rightarrow +\infty}{\frac{(\log{n})^r}{n}} = 0\]
对任意$r > 0$, 证明素数个数是无限的(提示: 假设它是有限的, $a, b, \ldots, c$为所有的不同的素数).
证明：具有上述形式的数的个数等于
\[(1 + \alpha)(1 + \beta)\cdots(1+\gamma),\]
注意到$a^{\alpha}\le n$,因此$\alpha < \log{n}/\log{a}$,因此不等式部分成立.
至于后面部分,假设素数只有有限个($k$个),它们就是$a,b,\cdots,c$,并且$a$是最小的,那么根据基本定理,每一个数都能够表示为上述形式,于是
\[n \le (1 + \frac{\log{n}}{\log{a}})(1 + \frac{\log{n}}{\log{b}}) \cdots (1 + \frac{\log{n}}{\log{c}}),\]
另一方面,
\[\begin{aligned}
&(1 + \frac{\log{n}}{\log{a}})(1 + \frac{\log{n}}{\log{b}}) \cdots (1 + \frac{\log{n}}{\log{c}}) < (1 + \frac{\log{n}}{\log{a}})^k \\
&=\sum_{i=0}^{k}{C_k^i(\frac{\log{n}}{\log{a}})^i}
\end{aligned}\]
于是
\[1 < \sum_{i=0}^{k}{\frac{C_k^i}{\log^i{a}} \cdot \frac{(\log{n})^i}{n}}\]
令$n \rightarrow$,而不等式右边是有限项,并且每一项趋于0,于是得到矛盾
\[1 \le 0.\]
7. $(a, b) = 1$, $a^2 – b^2$为完全平方数(参考习题3.3), 证明, 或者$a + b$和$a – b$都是完全平方数, 或者每一个都是一个完全平方数的二倍数(提示: 证明$a + b$和$a – b$的最大公约数是1或者2).
证明：首先有
\[(a+b,a-b) = (a+b-(a-b),a-b)=(2a,a-b)=(2a,b)=(2,b),\]
当$b$为偶数的时候最大公约数为2,否则为1.
其次我们有结论:如果$(m,n)=1$,那么如果$mn$是完全平方数,必有$m$和$n$都是完全平方数.
于是根据$(a+b,a-b)=1$和$(a+b,a-b)=2$分情形讨论,第一种情形对应的就是$a+b$和$a-b$都是完全平方数.至于后一情形,只要注意到$((a+b)/2,(a-b)/2)=1$,并且$(a^2-b^2)/4$仍旧是完全平方数即可.