1. 第十二章 素数

   1. 习题12.1
   2. 习题12.2
   3. 习题12.3
   4. 习题12.4
   5. 习题12.5
   6. 习题12.6

2. 第十三章 素数的计数

   1. 习题13.1
   2. 习题13.2
   3. 习题13.3
   4. 习题13.4
   5. 习题13.5
   6. 习题13.6
   7. 代码-定积分

3. 其他

第十二章 素数

习题12.1

从单个素数 $5$ 构成的列表开始，使用欧几里得证明的有无穷多个素数的思想，创建一个素数表，直到考虑的数太大，不易分解为止。（读者应该能够分解小于 $1000$ 的任何数。）

$$\begin{gathered} 5+1=2\times 3 \\ 2\times 5+1=11 \\ 2\times 5\times 11+1=111=3\times 37 \\ 2\times 3\times 5\times 11+1=331 \end{gathered}$$

习题12.2

(a) 证明存在无穷多个模 $6$ 余 $5$ 的素数。（提示：使用 $A=6p_1{p}_2\cdots p_r+5$​.）

(b) 试用同样的思想（用 $A=5p_1{p}_2\cdots p_r+4$）证明存在无穷多个模 $5$ 余 $4$ 的素数。为什么会出错呢？特别的，如果由 $\{19\}$ 开始，是制作更长的表，会发生什么情况呢？

(a) $p_1=5$，假设只存在有限多个素数模 $6$ 余 $5$ ，记为 $p_1,p_2,\cdots ,p_r$.令 $A=6p_1{p}_2\cdots p_r+5$，因只存在有限多个模 $6$ 余 $5$ 的素数，故 $A$ 不是素数。观察表格（偶素数只有2，故无需考虑偶数，当 $p\equiv 3(mod6)(p>3)$ 显然是合数）

$$\begin{array}{ccc}m& 1& 5\\ 1& 1& 5\\ 5& 5& 1\end{array}$$

故 $A$ 中必存在模 $6$ 余 $5$ 的质因子，又显然 $p_i\nmid A,1\le i\le r$，得出矛盾。故而存在无限个模 $6$ 余 $5$ 的素数。

(b)

$$\begin{array}{ccccc}m& 1& 2& 3& 4\\ 1& 1& 2& 3& 4\\ 2& 2& 4& 1& 4\\ 3& 3& 1& 4& 2\\ 4& 4& 3& 2& 1\end{array}$$

由表格可知，若合数 $A\equiv 4(mod5)$ ，$A$ 中未必就得有模 $5$ 余 $4$ 的素因子。

习题12.3

设 $p$ 是奇素数，将

写成最简分数 $A_p/B_p$.

• (a) 求 $A_p(modp)$ 的值，证明你的答案是正确的。
• (b) 给出 $A_p(mod{p}^2)$ 值的猜想。
• (c) 证明 (b) 中的猜想是正确的。（这是相当难的）

(a) 因 $p$ 是奇素数，故将数据分为 $(i,p-i)1\le i<m,m=\frac{p+1}{2}$ 两两一组，则有 $\sum _{i=1}^{\frac{p-1}{2}}(\frac{1}{i}+\frac{1}{p-i})=\sum _{i=1}^{\frac{p-1}{2}}\frac{p}{i(p-i)}$

因 $i\nmid p,1\le i\le p-1$，故而 $p\mid A_p$

(b) 猜想：$A_p\equiv 0(mod{p}^2),p>3$​

(c) 由欧拉定理可知，$a^{p-1}\equiv 1(modp)$ 对任何 $a\in \{1,2,\cdots ,p-1\}$ 都成立。即 $1,2,\cdots ,p-1$ 是多项式方程 $x^{p-1}\equiv 1(modp),p-1$ 个不同的根。由此我们有 $x^{p-1}\equiv (x-1)(x-2)\cdots (x-p+1)+1\equiv 1(modp)$.

令 $f(x)=(x-1)(x-2)\cdots (x-p+1)=x^{p-1}+A_1{x}^{p-2}+\cdots +A_{p-2}x+A_{p-1}\equiv 0(modp)$.其中 $A_{p-2}=-(p-1)!(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{p-1}),A_{p-1}=(p-1)!$

又 $A_{p-1}\equiv -1(modp),x^{p-1}\equiv 1(modp)$，则 $g(x)=A_1{x}^{p-2}+\cdots +A_{p-2}x\equiv 0(modp)$，有 $p-1$ 个解，与模 $p$ 多项式定理矛盾，则必然有 $A_i\equiv 0(modp)$ 对于 $1\le i<p-1$ 都成立。即 $p\mid A_i$ 。

又 $f(p)=(p-1)!=p^{p-1}+A_1{p}^{p-2}+\cdots +A_{p-2}p+A_{p-1}$，得 $p^{p-1}+A_1{p}^{p-2}+\cdots +A_{p-2}p=0$.

可知：$\frac{A_{p-2}}{p}=-\frac{A_{p-3}}{p}\cdot p-\frac{A_{p-4}}{p}\cdot p^2+\cdots +p^{p-3}$，即 $p\mid \frac{A_{p-2}}{p}，p>3$，也即 $p^2\mid A_{p-2}，p>3$​

第二种方法：

取 (a) 中的证明结论，$\frac{A_p}{B_p}=\sum _{i=1}^{p-1}\frac{1}{i}=\frac{p}{2}\sum _{i=1}^{p-1}\frac{1}{i(p-i)}$，若需证明 $p^2\mid A_p$，则等价证明分子部分 $\sum _{i=1}^{p-1}\frac{1}{i(p-i)}\equiv \sum _{i=1}^{p-1}\frac{1}{-i^2}\equiv 0(modp)$. 因$p\nmid (p-1)!$，可在等式两边同时乘以 $((p-1)!{)}^2$，可得 $((p-1)!{)}^2\sum _{i=1}^{p-1}\frac{1}{-i^2}\equiv -((p-1)!{)}^2\sum _{i=1}^{p-1}(i^{\prime }{)}^2=-((p-1)!{)}^2\sum _{i=1}^{p-1}{i}^2=-((p-1)!{)}^2\frac{(p-1)p(2p-1)}{6}(modp)$, $i^{\prime }为i$ 的逆元，由习题9.2可知，$i^{\prime }$ 互不相同。根据等式可知，$p>3时，p\mid \sum _{i=1}^{p-1}\frac{1}{i(p-i)}$ 的分子。

习题12.4

设 $m$ 是正整数， $a_1,a_2,\cdots ,a_{\varphi (m)}$ 是 $1$ 与 $m$ 之间且与 $m$ 互素的整数，记

的最简分数为 $A_m/B_m$

• (a) 求 $A_m(modm)$ 的值。证明你的猜想是正确的。
• (b) 计算几个 $A_m(mod{m}^2)$ 的值，试着寻找模式并证明那些模式在一般情况下成立，特别的，何时有 $A_m\equiv 0(mod{m}^2)$ ?

可能需要用到以下结论：

$$\{\begin{array}{llcccccccccccccccccccccc}\varphi (m)总是偶数& & & & & & & & & & & & & & & & & & & & & & & \\ (a_i,m)=1时，(m-a_i,m)=1也成立& & & & & & & & & & & & & & & & & & & & & & & \\ a_i^{\prime },a_2^{\prime },\cdots ,a_{\varphi (m)}^{\prime }互不相同,即逆元互不相同& & & & & & & & & & & & & & & & & & & & & & & \\ a_1{a}_2\cdots a_{\varphi (m)}\equiv \pm 1(modm)& & & & & & & & & & & & & & & & & & & & & & & \end{array}$$

(a) 将 $(a_i,m-a_i)$ 分为一组，得到 $\frac{1}{a_i}+\frac{1}{m-a_i}=\frac{m}{a_i(m-a_i)}$，即可得 $m\mid A_m$。

(b) 当 $a_1^2+a_2^2+\cdots +a_{\varphi (m)}^2\equiv 0(modm)$时 $A_m\equiv 0(mod{m}^2)$。可能有更强的模式。

习题12.5

回顾一下数 $n$ 的阶乘 $n!$，它等于乘积

• (a) 求每个整数 $1!,2!,3!,...,10!$ 的 $2$ 的最高次幂。
• (b) 用公式表示整除 $n!$ 的 $2$ 的最高次幂的计算法则。用该法计算整除 $100!$ 与 $1000!$ 的 $2$ 的最高次幂。
• (c) 证明 (b) 中的法则是正确的。
• (d) 重复 (a)，(b) 与 (c)，求整除 $n!$的 $3$ 的最高次幂。
• (e) 试用公式表示整除 $n!$ 的素数 $p$ 的最高次幂的一般法则。用该法则求整除 $1000!$ 的 $7$ 的最高次幂和整除 $5000!$ 的 $11$ 的最高次幂。
• (f) 用 (e) 的法则或其他方法，证明如果 $p$ 是素数，$p^m$ 整除 $n!$， 则 $m<n/(p-1)$.（这个不等式在高等数论的许多领域都很重要）

$m=\sum _{i=1}^{i\le {\log }_{p}n}\lfloor \frac{n}{p^i}\rfloor \le n\times \sum _{i=1}^{i\le {\log }_{p}n}\frac{1}{p^i}=n\times \frac{1-(\frac{1}{p}{)}^{{\log }_{p}n}}{p(1-\frac{1}{p})}<\frac{n}{p-1}，{\log }_{p}n$下取整，

讨论 $p^i$，$\lfloor \frac{n}{p^i}\rfloor$ 为 $[1,n]$ 中能被 $p^i$ 整除的数的个数，则 $n!$ 至少能被 $p^{i\lfloor \frac{n}{p^i}\rfloor }$ 整除，而当 $j=1,2,3,\cdots ,i-1$ 时已经统计过 $p$ 的 $1,2,3,\cdots ,i-1$ 次幂，故需从中去除这部分得到 $p^i$ 的贡献，即 $i\lfloor \frac{n}{p^i}\rfloor -(i-1)\lfloor \frac{n}{p^i}\rfloor =\lfloor \frac{n}{p^i}\rfloor$。

习题12.6

(a) 求满足 $p\equiv 1338(mod1115)$ 的素数 $p$，存在无穷多个这样的素数吗？

(b) 求满足 $p\equiv 1438(mod1115)$ 的素数 $p$，存在无穷多个这样的素数吗？

(a) $(1338,1115)=223$，$1338-1115=223$，不存在无限多个

(b) $(1438,1115)=1$，故存在。$1438+3\times 1115=4783$是质数，本书结尾质数表。

狄利克雷定理。

第十三章 素数的计数

习题13.1

(a) 用计数函数 $F(x)=\#\{正整数n\le x:n\equiv 2(mod5)\}$ 解释为什么陈述“五分之一的整数是模五余二” 有意义。

(b) 用计数函数 $S(x)=\#\{小于x的平方数\}$​ 解释为什么陈述 “大多数整数不是平方数” 有意义。

求 $x$ 的简单函数，使得当 $x$ 很大时它近似等于 $S(x)$.

$\underset{x\to \infty }{\lim }\frac{F(x)}{x}=\underset{x\to \infty }{\lim }\frac{\frac{x}{5}}{x}=\frac{1}{5}$，$\underset{x\to \infty }{\lim }\frac{S(x)}{x}=\underset{x\to \infty }{\lim }\frac{\sqrt{x}}{x}=\underset{x\to \infty }{\lim }\frac{1}{\sqrt{x}}=0$

习题13.2

(a) 验证 $70$ 与 $100$ 之间的每个偶数可表成两个素数之和。

(b) 有多少种不同方法可将 $70$ 表成两个素数之和 $70=p+q(p\le q)$ 呢？对于 $90$ 的相同问题呢？对于 $98$ 的相同问题呢？

制作 $n\times n$​ 的素数表格，可快速查询结果。

$$\begin{array}{cccccccccc}70& (29,41)& (23,47)& (17,53)& (11,59)& (3,67)& & & & \\ 72& (31,41)& (29,43)& (19,53)& (13,59)& (11,61)& (5,67)& & & \\ 74& (37,37)& (31,43)& (13,61)& (7,67)& (3,71)& & & & \\ 76& (29,47)& (23,53)& (17,59)& (5,71)& (3,73)& & & & \\ 78& (37,41)& (31,47)& (19,59)& (17,61)& (11,67)& (7,71)& (5,73)& & \\ 80& (37,43)& (19,61)& (13,67)& (7,73)& & & & & \\ 82& (41,41)& (29,53)& (23,59)& (11,71)& (3,79)& & & & \\ 84& (41,43)& (37,47)& (31,53)& (23,61)& (17,67)& (13,71)& (11,73)& (5,79)& \\ 86& (43,43)& (19,67)& (13,73)& (7,79)& (3,83)& & & & \\ 88& (41,47)& (29,59)& (17,71)& (5,83)& & & & & \\ 90& (43,47)& (37,53)& (31,59)& (29,61)& (23,67)& (19,71)& (17,73)& (11,79)& (7,83)\\ 92& (31,61)& (19,73)& (13,79)& (3,89)& & & & & \\ 94& (47,47)& (41,53)& (23,71)& (11,83)& (5,89)& & & & \\ 96& (43,53)& (37,59)& (29,67)& (23,73)& (17,79)& (13,83)& (7,89)& & \\ 98& (37,61)& (31,67)& (19,79)& & & & & & \\ 100& (47,53)& (41,59)& (29,71)& (17,83)& (11,89)& (3,97)& & & \end{array}$$

虽找不出什么规律，但数字越大，表示法越不唯一。

习题13.3

数 $n!$ 是 $1$ 到 $n$ 的所有整数的乘积。例如，$4!=1\cdot 2\cdot 3\cdot 4=24,7!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7=5040$. 如果 $n\ge 2$，证明所有整数

都是合数。

$n!+i=1\cdot 2\cdots \cdot (i-1)\cdot i\cdot (i+1)\cdots n+i=i\times (1\cdot 2\cdots \cdot (i-1)\cdot (i+1)\cdots n+1)$

习题13.4

(a) 你认为存在无穷多个形如 $N^2+2$​ 的素数吗？

(b) 你认为存在无穷多个形如 $N^2-2$ 的素数吗？

(c) 你认为存在无穷多个形如 $N^2+3N+2$ 的素数吗？

(d) 你认为存在无穷多个形如 $N^2+2N+2$ 的素数吗？

$N^2+3N+2=(N+1)(N+2)$，不存在

$N^2+2N+2=(N+1{)}^2+1$，存在

习题13.5

素数定理说明小于 $x$ 的素数个数近似等于 $x/\ln x$.这道习题要求解释为什么某些称述看起来是合理的。不必写下正规的数学证明，而是用尽可能令人信服的语言加以解释，为什么素数定理使得下述每个称述合情合理。

(a) 如果随机得取一个 $1$ 到 $x$ 的整数，则取到素数的概率大约是 $1/\ln x$。

(b) 如果随机地取 $1$ 到 $x$ 的两个整数，则取到两个数都是素数的概率大约是 $1/(\ln x{)}^2$.

(c) $1$ 与 $x$ 之间的孪生素数的个数近似等于$x/(\ln x{)}^2$，（注意，这里解释了关于孪生素数奇数函数 $T(x)$ 所猜测的极限公式。）

(a) $\frac{x/\ln x}{x}=\frac{1}{\ln x}$

(b) $\frac{x/\ln x(x/\ln x-1)}{x(x-1)}=\frac{x(x-\ln x)}{x(x-1)(\ln x{)}^2}\approx \frac{1}{(\ln x{)}^2}$​

(c) 素数概率大约是 $1/\ln x$，先取一个素数 $x$，剩下的整数是素数的概率仍近似等于 $1/\ln x$。即每个整数都等可能的是素数，即 $x$ 的相邻数是素数的概率也是 $1/\ln x$。因此取到孪生素数的概率大约为 $1/(\ln x{)}^2$。

习题13.6

（这道习题适用于具备微积分只是的读者。）素数定理说明当 $x$ 很大时，素数计数函数 $\pi (x)$ 近似等于 $x/\ln x$ .结果表明 $\pi (x)$ 更接近于定积分 ${\int }_2^{x}dt/\ln t$.

(a) 证明

这意味着当 $x$ 很大时，${\int }_2^{x}dt/\ln t$ 与 $x/\ln x$ 近似相等。（提示：利用洛必达法则和微积分第二基本定理。）

(b) 可以证明

利用这个级数计算 ${\int }_2^{x}dt/\ln t$ 在 $x=10,100,1000,10^4,10^6,10^9$ 时的数值。比较所得到的 $\pi (x)$ 的值与第 $13$ 章的表给出的 $x/\ln x$ 的值，哪一个更接近 $\pi (x)$，是积分 ${\int }_2^{x}dt/\ln t$ 还是函数 $x/\ln x$ 呢？（解答该问题可以使用便携式计算器。但你也许更喜欢使用计算机或可编程计算器。）

(c) 对 (b) 中的级数求微分，证明导数实际上等于 $1/\ln t$.（提示：利用 $e^x$ 的级数。）

(a)

$$\begin{gathered} \frac{x}{\ln x}\underrightarrow{x=e^t}\frac{e^t}{t}=\frac{1}{t}\cdot (1+t+\frac{t^2}{2!}+\frac{t^3}{3!}+\frac{t^4}{4!}+\cdots )=\frac{1}{t}+1+\frac{t}{2!}+\frac{t^2}{3!}+\frac{t^3}{4!}+\cdots \\ \underrightarrow{t=\ln x}\frac{1}{\ln x}+1+\frac{\ln x}{2!}+\frac{{\ln }^{2}x}{3!}+\frac{{\ln }^{3}x}{4!}+\cdots \\ {\int }_2^{x}dt/\ln t-x/\ln x=c-1-\frac{1}{\ln x}+\ln \ln x+\frac{\ln x}{1\cdot 2!}+\frac{{\ln }^{2}x}{2\cdot 3!}+\frac{{\ln }^{3}x}{3\cdot 4!}+\cdots \\ \underset{x\to \infty }{\lim }\frac{{\int }_2^{x}dt/\ln t-x/\ln x}{x/\ln x}\underrightarrow{洛必达法则}\underset{x\to \infty }{\lim }\frac{({\int }_2^{x}dt/\ln t-x/\ln x{)}^{\prime }}{(x/\ln x{)}^{\prime }} \\ =\underset{x\to \infty }{\lim }\frac{(1/x{\ln }^{2}x)\cdot (e^{\ln x}-1-\ln x)}{1/\ln x}\le \underset{x\to \infty }{\lim }\frac{1}{\ln x}=0 \end{gathered}$$

(b)

$$\begin{gathered} {\int }_2^x\frac{dt}{\ln t}\underrightarrow{t=e^t}{\int }_{\ln 2}^{\ln x}\frac{d{e}^t}{\ln e^t}={\int }_{\ln 2}^{\ln x}\frac{e^{t}dt}{t}={\int }_{\ln 2}^{\ln x}(\frac{1}{t}+1+\frac{t}{2!}+\frac{t^2}{3!}+\frac{t^3}{4!}+\cdots ) \\ =c+\ln \ln x+\ln x+\frac{{\ln }^{2}x}{2\cdot 2!}+\frac{{\ln }^{3}x}{3\cdot 3!}+\cdots \\ c=-\ln \ln 2-\ln 2-\frac{{\ln }^{2}2}{2\cdot 2!}-\frac{{\ln }^{3}2}{3\cdot 3!}-\cdots \approx -0.467948 \end{gathered}$$

$$\begin{array}{lcccccc}x& 10& 100& 1000& 10^4& 10^6& 10^9\\ \pi (x)& 4& 25& 168& 1229& 78498& 50847534\\ x/\ln x& 4.34& 21.71& 144.76& 1085.74& 72382.41& 48254942.43\\ \pi (x)/(x/\ln x)& 0.921& 1.151& 1.161& 1.132& 1.084& 1.054\\ {\int }_2^{x}dt/\ln t& 5.12& 29.08& 176.56& 1245.09& 78626.50& 50849233.91\\ \pi (x)/({\int }_2^{x}dt/\ln t)& 0.781& 0.860& 0.951& 0.987& 0.998& 1.000\end{array}$$

(c)

$$\begin{gathered} (\ln \ln t+\ln t+\frac{{\ln }^{2}t}{2\cdot 2!}+\frac{{\ln }^{3}t}{3\cdot 3!}+\frac{{\ln }^{4}t}{4\cdot 4!}+\cdots {)}^{\prime }=\frac{1}{t\ln t}+\frac{1}{t}+\frac{2\ln t}{2t\cdot 2!}+\frac{3{\ln }^{2}t}{3t\cdot 3!}+\cdots \\ =\frac{1}{t}\cdot (\frac{1}{\ln t}+1+\frac{\ln t}{2!}+\frac{{\ln }^{2}t}{3!}+\cdots )=\frac{1}{t}\cdot \frac{1}{\ln t}\cdot (1+\frac{\ln t}{1!}+\frac{{\ln }^{2}t}{2!}+\frac{{\ln }^{3}t}{3!}+\cdots ) \\ =\frac{1}{t\ln t}\cdot e^{\ln t}=\frac{1}{\ln t} \end{gathered}$$

代码-定积分

/**
 * @param e 误差
 * @return 习题13.6中的定积分
 */
public double f(int x, double e){
    int u = -((int) Math.log(e)) + 5;
    BigDecimal y = BigDecimal.valueOf(Math.log(x));
    BigDecimal t = BigDecimal.ONE;
    BigDecimal s = BigDecimal.valueOf(Math.log(y.doubleValue()));
    BigDecimal f = BigDecimal.ONE;
    for (BigDecimal i = BigDecimal.ONE; ; i = i.add(BigDecimal.ONE)) {
        f = f.multiply(i);
        t = t.multiply(y);
        BigDecimal _t = t.divide(f.multiply(i), u, RoundingMode.HALF_UP);
        s = s.add(_t);
        if(_t.doubleValue() < e) break;
    }
    return s.doubleValue();
}

其他

1. 数论概论$\cdot$第一部分
2. 数论概论$\cdot$第二部分
3. 数论概论$\cdot$第三部分
4. 数论概论$\cdot$第四部分
5. 数论概论$\cdot$第五部分