设整数 $k \geqslant 3$，数列 $\left\{a_{n}\right\}$ 满足 $a_{k}=2 k$，且对所有的 $n>k$，有
$a_{n}=\left\{\begin{array}{ll}{a_{n-1}+1,} & {a_{n-1}与n互质} \\ {2 n,} & {a_{n-1}与n不互质}\end{array}\right.$
证明：数列 $\left\{a_{n}-a_{n-1}\right\}$ }中有无穷多项是质数．
$a_{n}=\left\{\begin{array}{ll}{a_{n-1}+1,} & {a_{n-1}与n互质} \\ {2 n,} & {a_{n-1}与n不互质}\end{array}\right.$
证明：数列 $\left\{a_{n}-a_{n-1}\right\}$ }中有无穷多项是质数．
【难度】
【出处】
2010第25届CMO试题
【标注】
【答案】
略
【解析】
假设 $a_{l}=2 l(l \geqslant k)$．再设 $p$ 为 $l-1$ 的最小质因子．则
$(l-1, i)=\left\{\begin{array}{ll}{1,} & {1 \leqslant i<p} \\ {p,} & {i=p}\end{array}\right.$
故 $(2 l+i-2, l+i-1)=\left\{\begin{array}{ll}{1,} & {1 \leqslant i<p} \\ {p,} & {i=p}\end{array}\right.$
由题设知 $a_{l+i-1}=\left\{\begin{array}{ll}{2 l+i-1,} & {1 \leqslant i<p} \\ {2 l+2 p-2,} & {i=p}\end{array}\right.$
则 $a_{l+p-1}-a_{l+p-2}=(2 l+2 p-2)-(2 l+p-2)=p$（质数）
故 $a_{l+p-1}=2(l+p-1)$．
由以上讨论知有无穷多个 $l \geqslant k$，使 $a_{l}=2l$ 且 $a_{l+p-1}-a_{l+p-2}=p$ 为 $l-1$ 的最小质因子．
$(l-1, i)=\left\{\begin{array}{ll}{1,} & {1 \leqslant i<p} \\ {p,} & {i=p}\end{array}\right.$
故 $(2 l+i-2, l+i-1)=\left\{\begin{array}{ll}{1,} & {1 \leqslant i<p} \\ {p,} & {i=p}\end{array}\right.$
由题设知 $a_{l+i-1}=\left\{\begin{array}{ll}{2 l+i-1,} & {1 \leqslant i<p} \\ {2 l+2 p-2,} & {i=p}\end{array}\right.$
则 $a_{l+p-1}-a_{l+p-2}=(2 l+2 p-2)-(2 l+p-2)=p$（质数）
故 $a_{l+p-1}=2(l+p-1)$．
由以上讨论知有无穷多个 $l \geqslant k$，使 $a_{l}=2l$ 且 $a_{l+p-1}-a_{l+p-2}=p$ 为 $l-1$ 的最小质因子．
答案
解析
备注
