习题三

1

2

设 $n>1$ 为整数，如果对于任何整数 $m$ ，或者 $n|m$ 或者 $(n,m)=1$ ，则 $n$ 必是素数.

Sol:
假设 $n$ 不是素数，则必存在 $2\leqslant k<n$ 且有 $k|n$ ，于是有 $(n,k)=k\not=1$ ，又题意知必有 $n|k$ ，又 $k|n$ ，所以 $n=k$ 矛盾，知 $n$ 为素数.

3

设整数 $n>2$ ，证明： $n$ 和 $n!$ 之间必有素数. 由此证明素数有无穷多.

Sol:
当 $n>2$ 时，有 $(n-1)!>1$ ，所以 $n<n!$ 恒成立.
有 $(n!-1,n!)=(1,n!)=1$ ，知相邻的两个数互素，
①当 $n!-1$ 是一个素数时，结论成立.
②当 $n!-1$ 不是素数时，必存在 $k|n!-1$ 且 $k$ 是素数，
又 $k>n$ 恒成立，(若 $k<n$ 则有， $(n!-1,n!)\geqslant k>1$ ，与题意矛盾).
由此可知存在一个素数 $k$ ，且有 $n<k<n!$ .
$n$ 和 $n!$ 之间必有素数成立
由此任取一个 $n_1>2$ ，则 $n_1$ 和 $n_1!$ 之间至少有一个素数，令 $n_2=n_1!>n_1$ ，
$n_2$ 与 $n_2!$ 之间也至少存在一个素数，由此不断循环下去可得无穷多个素数.

4

设整数 $n\geqslant2$ ，证明：存在连续 $n$ 个正整数，其中每一个都不是素数. (这表明，在正整数序列中，可以有任意长的一段区间中不包括素数.)

Sol:
取 $(n+1)!$ 可被 $2,3,4,\cdots,n+1$ 共 $n$ 个数整除，得到序列
$(n+1)!+2,(n+1)!+3,\cdots,(n+1)!+n+1$ 共 $n$ 个数，分别一定能被 $2,3,4,\cdots,n+1$ 整除， $n$ 可任意取大于2的整数，知正整数序列中可以有任意长的一段区间中不包括素数.

5

证明：
(i) 形如 $4n+3$ 的素数有无穷多个；
(ii) 形如 $6n+5$ 的素数有无穷多个.

Sol:
(i):
形如 $4n+3$ 的数也可用 $4n-1$ 表示
易知，除了 2 以外的所有素数都可以用 $4n\pm1$ 表示.
引理：对于任意用 $4n-1$ 表示的数，都至少有一个 $4k-1$ 形式的素数
证明：若全为 $4k+1$ 形式的素数，则有
$(4k_1+1)(4k_2+1)=16k_1k_2+4k_1+4k_2+1=4(4k_1k_2+k_1+k_2)+1$
新的数依旧是 $4k+1$ 形式的，进行 $m$ 次，也依旧是 $4k+1$ 的形式
所以只有 $4k-1$ 形式的数不可能全部素因子都是 $4k+1$ 形式的素数

证明：
反证法，
假设形如 $4k-1$ 的素数有 $m$ 个，则
当 $m$ 是奇数的时候，有 $(4k_1-1)(4k_2-1)\cdots(4k_m-1)=4k-1=A$
$N=A+4=4(k+1)-1$ 由引理可知， $N$ 必有 $4k-1$ 形的素因子，之前假设只有 $m$ 个形如 $4k-1$ 形式的素数，则有某个 $4k_i-1|N$
即 $4k_i-1|A+4$ ，即有 $4k_i-1|4$ ，显然矛盾.

当 $m$ 是偶数的时候，有 $(4k_1-1)(4k_2-1)\cdots(4k_m-1)=4k+1=A$
$N=A+2=4(k+1)-1$ 同上可知存在 $4k_j-1|2$ ，显然矛盾.
综上所知,形如 $4n+3$ 的素数有无穷多个.

(ii):
形如 $6k+5$ 的数也可以用 $6k-1$ 表示、
引理：对于任意用 $6n-1$ 表示的数，都至少有一个 $6k-1$ 形式的素数
证明：若全为 $6k+1$ 形式的素数，则有
$(6k_1+1)(6k_2+1)=36k_1k_2+6k_1+6k_2+1=6(6k_1k_2+k_1k_2)+1$
新的数依旧是 $6k+1$ 形式的，进行 $m$ 次，也依旧是 $6k+1$ 的形式
所以只有 $6k-1$ 形式的数不可能全部素因子都是 $6k+1$ 形式的素数

证明：
反证法，
假设形如 $6k-1$ 的素数有 $m$ 个，则
当 $m$ 是奇数的时候，有 $(6k_1-1)(6k_2-1)\cdots(6k_m-1)=6k-1=A$
$N=A+6=6(k+1)-1$ 由引理可知， $N$ 必有 $6k-1$ 形的素因子，之前假设只有 $m$ 个形如 $6k-1$ 形式的素数，则有某个 $6k_i-1|N$
即 $6k_i-1|A+6$ ，即有 $6k_i-1|6$ ，显然矛盾.

当 $m$ 是偶数的时候，有 $(6k_1-1)(6k_2-1)\cdots(6k_m-1)=6k+1=A$
$N=A+4=6(k+1)-1$ 同上可知存在 $6k_j-1|4$ ，显然矛盾.
综上所知,形如 $6k+5$ 的素数有无穷多个.

6

证明：如果 $p,p+2,p+4$ 都是素数，则 $p = 3$ .

Sol:
因为 $p,p+2,p+4$ 都是素数，易知 $p$ 一定为奇数，
若 $p>3$ ，则必有 $p=2n+1\;\;(n>1)$
有 $p=2n+1>3,\,p+2=3+2n>3,\,p+4=3+2n+2>3$
$(p,\,3)=(2n+1,\,3)$
$(p+2,\,3)=(2n,\,3)$
$(p+4,\,3)=(2n+2,\,3)$
易知 $2n,\,2n+1,\,2n+2$ 连续的三个正整数中，必然有一能被 $3$ 整除，
所以 $p,p+2,p+4$ 必有一能被 $3$ 整除，且 $p,p+2,p+4$ 都大于 $3$ ，知，必有一数为合数，与题意矛盾，所以 $p\not>3\Rightarrow 2<p\leqslant3$
当 $p=3$ 时，有 $p=3,\,p+2=5,\,p+4=7$ 都为素数，满足题意

综上所述， $p=3$ .

7

8

设整数 $10^{n-1}+10^{n-2}+\cdots+1\,(n>1)$ 是素数，则 $n$ 是素数；但反之不成立.

Sol:
反证法，当 $n$ 不为素数时，必有 $n=pm\;(p>1\,,\,m>1)$
有
$\begin{aligned} &10^{n-1}+10^{n-2}+\cdots+1\\ =&\dfrac{10^{n}-1}{10-1}=\dfrac{10^{pm}-1}{9}\\ =&\dfrac{(10^p-1)(10^{p(m-1)}+10^{{p(m-2)}+\cdots+1})}{9}\\ =&\dfrac{(10-1)(10^{p-1}+10^{p-2}+\cdots+1)(10^{p(m-1)}+10^{{p(m-2)}}+\cdots+1)}{9}\\ =&(10^{p-1}+10^{p-2}+\cdots+1)(10^{p(m-1)}+10^{{p(m-2)}}+\cdots+1) \end{aligned}$

知当 $n$ 为合数时， $10^{n-1}+10^{n-2}+\cdots+1\,(n>1)$ 不是素数

反之，当 $n$ 为素数时，如： $n=3$ 时，有 $10^2+10+1=111=3\times37$ ，所以该命题反之不成立.

9

(i) 设 $m$ 为正整数，证明：如 $2^m+1$ 为素数，则 $m$ 为2的方幂.
(ii) 对 $n\geqslant0$ ，记 $F_n=2^{2^n}+1$ ，这称为费马(Fermat)数. 证明：如 $m>n$ ，则 $F_n|(F_m-2)$ ;
(iii) 证明：如 $m\not =n$ ，则 $(F_m,\,F_n)=1$ . 由此证明素数有无穷多个.

Sol:
(i):
反证法：
若 $m$ 不是 $2$ 的方幂，则必有 $m=np\,,(n=2^r,\,p为大于1的奇数)$
记 $2^{2^r}=a$
则有 $2^m+1=(2^{2^r})^p+1=(a+1)(a^{p-1}-a^{p-2}+\cdots+1)$
与 $2^m+1$ 是素数矛盾.
所以若 $2^m+1$ 为素数，则 $m$ 为2的方幂.

Sol:
(ii):
设 $m=n+k$
有
$\begin{aligned} F_m-2=&(2^{2^m}-1)=(2^{2^{m-1}}-1)(2^{2^{m-1}}+1)\\ =&(2^{2^{m-2}}-1)(2^{2^{m-2}}+1)(2^{2^{m-1}}+1)\\ =&\cdots\\ =&(2^{2^n}-1)(2^{2^n}+1)\cdots(2^{2^{m-2}}+1)(2^{2^{m-1}}+1)\\ =&(2^{2^n}-1)F_{n}\cdot F_{n+1}\cdots F_{m-2}\cdot F_{m-1} \end{aligned}$
由此可知
$\displaystyle m>n 时,\,F_n|(F_m-2)$ 成立.

Sol:
(iii):
不妨设 $m>n$
由(ii)有
$\displaystyle F_m-2=F_{m-1}F_{m-2}\cdots F(1)\cdot F(0)\cdot(2-1)$
$\displaystyle\therefore(F_{m},\,F_{n})=(F_{m-1}F_{m-2}\cdots F(1)\cdot F(0)+2,\,F(n))=(2,\,F_n)$
又易知 $F_n$ 为奇数，
$\therefore (2,\,F_n)=1$
$\therefore (F_m,\,F_n)=1$
假设只有有限 $m$ 个素数，则取 $m+1$ 个费马数，
易知任意两两费马数都互质，且任意一个费马数都至少有一个质因数，不妨设 $F_{m_k}$ 存在一个 $m_k$ 质因数，且剩下 $m$ 个费马数中，都不存在这个质因数，对于其他 $m$ 个费马数都至少存在一个对于其他 $m$ 个费马数为一的质因数，
所以知 $m+1$ 个费马数中至少存在 $m+1$ 个不同的素数. 与题设矛盾，所以素数有无穷多个.

10

11

12

13

14

15

16

17

证明：
(i) $(a,[\,b, c\,])=[\,(\,a,b\,),(\,a,c\,)\,]$ ；
(ii) $[\,a,(\,b,c\,)\,]=(\,[\,a,b\,],[\,a,c\,]).$

Sol:
易知有
$[\,b,\,c\,]=\dfrac{bc}{(b,c\,)}$
$[\,(\,a,b\,),(\,a,c\,)\,]=\dfrac{(a,b)*(a,c)}{(a,b,c)}$
$(a,[\,b, c\,])=(a,\dfrac{bc}{(b,c\,)})=\dfrac{(a,bc)}{(a,(b,c))}=\dfrac{(a,b)*(a,c)}{(a,b,c)}$
由上面三个等式知
$(a,[\,b, c\,])=[\,(\,a,b\,),(\,a,c\,)\,]$ . 成立.

Sol2:
由唯一分解定理知：
$\displaystyle a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$
$\displaystyle b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_n^{\beta_n}$
$\displaystyle c=p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_n^{\gamma_n}$
$(a,[\,b, c\,])=p_1^{r_1}p_2^{r_2}\cdots p_n^{r_n},\quad r_i=\min\{\alpha_i,\max\{\beta_i,\gamma_i \} \}$
$[(a,b),(a,c)]=p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n},\quad m_i=\max\{\min\{\alpha_i,\beta_i\},\min\{\alpha_i,\gamma_i \} \}$
这时候我们来判断一下关系，对于任意的 $i$
$\begin{aligned} &\alpha_i\geqslant\beta_i\geqslant\gamma_i,&r_i=\beta_i=m_i\\ &\alpha_i\geqslant\gamma_i\geqslant\beta_i,&r_i=\gamma_i=m_i\\ &\beta_i\geqslant\alpha_i\geqslant\gamma_i,&r_i=\alpha_i=m_i\\ &\beta_i\geqslant\gamma_i\geqslant\alpha_i,&r_i=\gamma_i=m_i\\ &\gamma_i\geqslant\alpha_i\geqslant\beta_i,&r_i=\alpha_i=m_i\\ &\gamma_i\geqslant\beta_i\geqslant\alpha_i,&r_i=\beta_i=m_i\\ \end{aligned}$
知对任意的 $\alpha_i,\beta_i,\gamma_i$ 关系，都有 $r_i=m_i$
知 $(a,[b,c])=[(a,b),(a,c)]$ 成立

(ii)
Sol:
由唯一分解定理知：
$\displaystyle a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$
$\displaystyle b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_n^{\beta_n}$
$\displaystyle c=p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_n^{\gamma_n}$
$[\,a,(\,b,c\,)\,]=p_1^{r_1}p_2^{r_2}\cdots p_n^{r_n},\quad r_i=\max\{\alpha_i,\min\{\beta_i,\gamma_i \} \}$
$(\,[\,a,b\,],[\,a,c\,])=p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n},\quad m_i=\min\{\max\{\alpha_i,\beta_i\},\max\{\alpha_i,\gamma_i\}\}$
这时候我们来判断一下关系，对于任意的 $i$
$\begin{aligned} &\alpha_i\geqslant\beta_i\geqslant\gamma_i,&r_i=\alpha_i=m_i\\ &\alpha_i\geqslant\gamma_i\geqslant\beta_i,&r_i=\alpha_i=m_i\\ &\beta_i\geqslant\alpha_i\geqslant\gamma_i,&r_i=\alpha_i=m_i\\ &\beta_i\geqslant\gamma_i\geqslant\alpha_i,&r_i=\gamma_i=m_i\\ &\gamma_i\geqslant\alpha_i\geqslant\beta_i,&r_i=\alpha_i=m_i\\ &\gamma_i\geqslant\beta_i\geqslant\alpha_i,&r_i=\beta_i=m_i\\ \end{aligned}$
知对任意的 $\alpha_i,\beta_i,\gamma_i$ 关系，都有 $r_i=m_i$
知 $[\,a,(\,b,c\,)\,]=(\,[\,a,b\,],[\,a,c\,])$ 成立.

18

19

习题四
 整数与多项式-【目录】

习题三

习题三

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

推荐阅读更多精彩内容