Let K be the set of all natural numbers formed by alternating digits 0 and 1, with both the first and last digits being 1. Find the number of prime numbers in K.

设集合K为所有由数字 0 和 1 相间组成、首位和末位均为 1 的自然数的全体，求集合K中素数的个数。

解答

步骤 1：确定集合K中数的形式

由题意，数字0、1 相间排列，首位、末位都是 1，因此这类数的位数必为奇数，具体形式：

• 1 位：1
• 3 位：101
• 5 位：10101
• 7 位：1010101
• ……

可写出通项公式：

\(N_n=\underbrace{1010\cdots1}_{2n-1\text{位}}=\frac{100^n-1}{99}\quad(n\ge1)\)

步骤 2：逐一分析素性

1. 1 位数：11 既不是素数，也不是合数。
2. 3 位数：101\(\sqrt{101}\approx10.05\)，只需检验小于 10 的素数\(2,3,5,7\)：

• 101是奇数，不能被2整除；
• 数字和\(1+0+1=2\)，不能被3整除；
• 末位为1，不能被5整除；
• \(101\div7=14\cdots\cdots3\)，不能被7整除。

因此\(\boldsymbol{101}\)是素数。

3. 位数≥5（即\(n\ge3\)）利用模 3 分析：\(100\equiv1\pmod{3}\)，故 \(100^n\equiv1^n=1\pmod{3}\)，得 \(100^n-1\equiv0\pmod{3}\)。因此 \(N_n=\frac{100^n-1}{99}\) 能被3整除，且 \(N_n>3\)，必为合数。

最终结论

集合K中仅有\(\boldsymbol{1}\)个素数（即101）。

第二个解法

1. 先写出数的通用代数形式

满足条件的数是0、1 相间，首尾为 1，必然是奇数位，可表示为等比数列求和： \(N=1+100+100^2+\dots+100^k=\frac{100^{k+1}-1}{99}=\boldsymbol{\frac{(10^{k+1}-1)(10^{k+1}+1)}{9\times11}}\)

2. 对 k 分奇偶因式分解判断合数

• \(k=0\)：数为\(\boldsymbol{1}\)，既不是素数也不是合数；
• \(k=1\)：数为\(\boldsymbol{101}\)，验证是素数；
• k为奇数且\(k\ge3\)：拆分出两个大于 1 的整数因子，为合数；
• k为偶数且\(k\ge2\)：同样拆分出两个大于 1 的整数因子，为合数。

3. 最终结论

K中只有1 个素数，即\(\boldsymbol{101}\)。

---

Let \(n\in\mathbb{N}^*\), prove the following conclusions:
(1) If \(2^n+1\) is a prime number, then there exists \(k\in\mathbb{N}\) such that \(n=2^k\).
(2) If \(2^n-1\) is a prime number, then n is a prime number.

设 \(n\in\mathbb{N}^*\)，证明下述结论：
(1) 若 \(2^n+1\) 为素数，则存在 \(k\in\mathbb{N}\)，使得 \(n=2^k\)；
(2) 若 \(2^n-1\) 为素数，则 n 为素数。

预备因式分解公式

1. 当 t 为大于 1 的奇数时：\(x^t+1=(x+1)(x^{t-1}-x^{t-2}+x^{t-3}-\dots-x+1)\)
2. 对任意整数 \(t>1\)：\(x^t-1=(x-1)(x^{t-1}+x^{t-2}+\dots+x+1)\)

---

证明

(1) 证明：若 \(2^n+1\) 为素数，则 \(n=2^k\)

反证法：假设 n不是 2 的整数次幂，

则 n 必含有大于 1 的奇数因子，设

\(n=2^k\cdot t,\quad t>1,\ t\text{ 为奇数}.\)

代入得： \(\begin{align*} 2^n+1&=(2^{2^k})^t+1\\ &=\boldsymbol{(2^{2^k}+1)}\cdot\left[(2^{2^k})^{t-1}-(2^{2^k})^{t-2}+\dots+1\right] \end{align*}\)

其中两个因子都大于 1，因此 \(2^n+1\) 是合数，与题设矛盾。

故 n 只能是 2 的整数次幂，即 \(\boldsymbol{n=2^k}\)。

注：\(2^{2^k}+1\) 称为费马数。

---

(2) 证明：若 \(2^n-1\) 为素数，则 n 为素数

反证法：假设 n 是合数，则可分解为

\(n=ab,\quad a,b>1,\ a,b\in\mathbb{N}^*.\)

代入得： \(\begin{align*} 2^n-1&=2^{ab}-1=(2^a)^b-1\\ &=\boldsymbol{(2^a-1)}\cdot\left(2^{a(b-1)}+2^{a(b-2)}+\dots+1\right) \end{align*}\)

其中两个因子都大于 1，因此 \(2^n-1\) 是合数，与题设矛盾。

故 n 必为素数。

注：\(2^p-1\)（p 为素数）称为梅森数。

---

核心结论总结

1. \(2^n+1\) 为素数 \(\implies n\) 是 2 的幂（费马素数的必要条件）；
2. \(2^n-1\) 为素数 \(\implies n\) 是素数（梅森素数的必要条件）。

第二种解法

两个命题均采用反证法 + 因式分解公式证明，逻辑完全对称：

(1) 证明：若 \(2^n+1\) 为素数，则 \(n=2^k\)

1. 反证假设：若 n 不是 2 的整数次幂，则 n 一定含有奇素因子 p；
2. 因式分解：利用奇数次幂和公式\(2^n+1=\left(2^{\frac{n}{p}}\right)^p+1=\left(2^{\frac{n}{p}}+1\right)\cdot(\text{另一大于1的整数})\)
3. 推出矛盾：\(2^n+1\) 可拆为两个大于 1 的因数，是合数，与条件矛盾；
4. 结论：故 n 只能是 2 的整数次幂，即 \(n=2^k\)。

(2) 证明：若 \(2^n-1\) 为素数，则 n 为素数

1. 反证假设：若 n 不是素数，则 n 是合数，可写为 \(n=p\cdot q\ (1<p,q<n)\)；
2. 因式分解：利用幂差公式\(2^n-1=(2^p)^q-1=(2^p-1)\cdot(\text{另一大于1的整数})\)
3. 推出矛盾：\(2^n-1\) 可拆为两个大于 1 的因数，是合数，与条件矛盾；
4. 结论：故 n 必为素数。

---

核心套路

• \(2^n+1\)：指数含奇数因子 → 可因式分解 → 必为合数；
• \(2^n-1\)：指数为合数 → 可因式分解 → 必为合数。

---

Given the polynomial \(P(n)=n^3-n^2-5n+2\), find all integers n such that \((P(n))^2\) is the square of a prime number.

已知多项式 \(P(n)=n^3-n^2-5n+2\)，求所有整数 n，使得 \((P(n))^2\) 是一个素数的平方。

解答

步骤 1：转化条件

设素数为 p，由题意 \((P(n))^2=p^2\)，因此

\(\boldsymbol{P(n)=\pm p}\)

即 \(|P(n)|\) 必须是素数（素数是大于 1 的正整数，仅能被 1 和自身整除）。

步骤 2：因式分解多项式

试有理根得 \(n=-2\) 是 \(P(n)=0\) 的根，因此因式分解： \(\begin{align*} P(n)&=n^3-n^2-5n+2\\ &=\boldsymbol{(n+2)(n^2-3n+1)} \end{align*}\)

因此

\(|P(n)|=|n+2|\cdot|n^2-3n+1|\)

步骤 3：利用素数性质分类讨论

\(|P(n)|\) 是素数，说明两个整数因子恰好一个绝对值为 1，另一个绝对值为素数。

情况 1：\(|n+2|=1\)

• \(n+2=1 \implies \boldsymbol{n=-1}\)此时 \(n^2-3n+1=5\)，\(|P(n)|=1\times5=5\)（素数），符合条件。
• \(n+2=-1 \implies \boldsymbol{n=-3}\)此时 \(n^2-3n+1=19\)，\(|P(n)|=1\times19=19\)（素数），符合条件。

情况 2：\(|n^2-3n+1|=1\)

分两种子方程：

1. \(n^2-3n+1=1 \implies n(n-3)=0\)
   • \(\boldsymbol{n=0}\)：\(|n+2|=2\)，\(|P(n)|=2\times1=2\)（素数），符合条件；
   • \(\boldsymbol{n=3}\)：\(|n+2|=5\)，\(|P(n)|=5\times1=5\)（素数），符合条件。
2. \(n^2-3n+1=-1 \implies (n-1)(n-2)=0\)
   • \(\boldsymbol{n=1}\)：\(|n+2|=3\)，\(|P(n)|=3\times|-1|=3\)（素数），符合条件；
   • \(n=2\)：\(|n+2|=4\)，\(|P(n)|=4\times|-1|=4\)（合数），舍去。

最终结果

满足条件的整数为：\(\boldsymbol{-3,-1,0,1,3}\)

---

Let \(a,b,c,d,e,f\) be positive integers, and let \(S=a+b+c+d+e+f\). If S is a common divisor of \(abc+def\) and \(ab+bc+ca-de-ef-fd\), prove that S is a composite number.

设 \(a,b,c,d,e,f\) 均为正整数，记 \(S=a+b+c+d+e+f\)。若 S 是 \(abc+def\) 与 \(ab+bc+ca-de-ef-fd\) 的公因数，求证：S 是一个合数。

解答

步骤 1：模条件转化

记 \(P=a+b+c\)，\(Q=d+e+f\)，则 \(S=P+Q\)，因此在模 S 意义下有

\(Q\equiv -P \pmod S.\)

由公因数条件：

1. \(S\mid abc+def \implies \boldsymbol{def\equiv -abc\pmod S}\)；
2. \(S\mid (ab+bc+ca)-(de+ef+fd) \implies \boldsymbol{de+ef+fd\equiv ab+bc+ca\pmod S}\)。

步骤 2：构造三次多项式

对数组 \(\{a,b,c\}\)，三次因式分解：

\((t-a)(t-b)(t-c)=t^3-Pt^2+(ab+bc+ca)t-abc.\)

对数组 \(\{d,e,f\}\)，同理：

\((t-d)(t-e)(t-f)=t^3-Qt^2+(de+ef+fd)t-def.\)

将模 S 的等价条件代入第二个多项式，得： \(\begin{align*} (t-d)(t-e)(t-f)&\equiv t^3+Pt^2+(ab+bc+ca)t+abc\\ &=-\left[(-t)^3-P(-t)^2+(ab+bc+ca)(-t)-abc\right]\\ &=-\,(-t-a)(-t-b)(-t-c) \pmod S. \end{align*}\)

步骤 3：导出整除关系

取 \(t=d\)，左边 \((d-d)(d-e)(d-f)=0\)，因此

\(0\equiv -\left(-d-a\right)(-d-b)(-d-c) \pmod S,\)

即

\(\boldsymbol{(a+d)(b+d)(c+d)\equiv0\pmod S}.\)

步骤 4：反证法证明 S 为合数

假设 S 是素数，则素数整除乘积，必整除其中一个因子，不妨设 \(S\mid a+d\)。

但 \(a,b,c,d,e,f\) 都是正整数，故

\(a+d < a+b+c+d+e+f=S,\)

即 \(a+d\) 是小于 S 的正整数，素数 S 不可能整除比自身更小的正整数，矛盾。

因此假设不成立，S 必为合数。

证毕。