数列的构造与论证

一列正整数$a_1,a_2,\cdots,a_n,\cdots$满足每个数都能整除之后的数，即$a_n\mid a_{n+1}$，则它们模$30$的余数最多可能有多少种不同的取值？

---

正确答案是$21$．

分析与解　将集合$\{1,2,\cdots,30\}$划分为元素质因数分解后不包含$2,3,5$的组成集合$A_0$；包含$2$但不包含$3,5$的组成集合$A_2$；包含$3$但不包含$2,5$的组成集合$A_3$；包含$5$但不包含$2,3$的组成集合$A_5$；包含$2,3$但不包含$5$的组成集合$A_{2,3}$；包含$3,5$但不包含$2$的组成集合$A_{3,5}$；包含$2,5$但不包含$3$的组成集合$A_{2,5}$；包含$2,3,5$的组成集合$A_{2,3,5}$，如下表．

$$\begin{matrix} name &type & set & card \\ \hline A_0&x & 1,7,11,13,17,19,23,29 & 8 \\ A_2&2^k\cdot x & 2,4,8,14,16,22,26,28 & 8\\ A_3&3^k\cdot x & 3,9,21,27 & 4\\ A_5&5^k\cdot x & 5,25 & 2\\ A_{2,3}&2^{k_1}\cdot 3^{k_2}\cdot x & 6,12,18,24 &4\\ A_{3,5}&3^{k_1}\cdot 5^{k_2}\cdot x & 15 & 1\\ A_{2,5}&2^{k_1}\cdot 5^{k_2}\cdot x & 10,20 & 2\\ A_{2,3,5}&2\cdot 3\cdot 5 & 30 & 1\\ \hline \end{matrix}$$ 容易知道，如果余数数列出现了$A_2$中的数，就不可能再出现$A_0$中的数；类似的，如果余数数列中出现了$A_{2,3}$中的数，就不可能出现$A_2,A_3$中的数．因此最多取值数为 $${\rm Card}(A_0)+{\rm Card}(A_2)+{\rm Card}(A_{2,3})+{\rm Card}(A_{2,3,5})=8+8+4+1=21.$$ 具体的构造可行性可以利用裴蜀定理证明．

注　可以构造$a_n=\displaystyle \prod_{i=1}^nx_i$，其中$i=1,2,\cdots,$．而其中

$$x_n:1,7,7,7,11,7,7,7,2,7,7,7,11,7,7,7,3,7,7,7,5,\cdots$$ 对应的余数数列为 $$\underbrace{1,7,19,13,23,11,17,29}_{A_0},\underbrace{28,16,22,4,14,8,26,2}_{A_2},\underbrace{6,12,24,18}_{A_{2,3}},0,\cdots$$