10.6. Petya chose a natural number $a>1$ and wrote down fifteen numbers $1+a, 1+a^{2}, 1+a^{3}, \ldots, 1+a^{15}$ on the board. Then he erased several numbers so that any two remaining numbers are coprime. What is the maximum number of numbers that could remain on the board?

(O. Podlipsky)
# Answer. 4 numbers.

Solution. First, we will show that there cannot be more than four such numbers. Note that if $k$ is odd, then the number $1+a^{n k}=1^{k}+\left(a^{n}\right)^{k}$ is divisible by $1+a^{n}$. Next, each of the numbers $1,2, \ldots, 15$ has one of the forms $k, 2 k, 4 k, 8 k$, where $k$ is odd. Thus, each of the numbers $1+a, 1+a^{2}, 1+a^{3}, \ldots, 1+a^{15}$ is divisible by either $1+a$, or $1+a^{2}$, or $1+a^{4}$, or $1+a^{8}$. Therefore, if we take at least five numbers, then among them there will be two that are divisible by the same number greater than 1; hence, they will not be coprime. Thus, there cannot be more than four remaining numbers.

It remains to show that four numbers could remain. Indeed, if $a=2$, then we can leave the numbers $1+2=3$, $1+2^{2}=5$, $1+2^{4}=17$, and $1+2^{8}=257$. All of them are pairwise coprime.

Remark. It can be shown that for any even $a$, the numbers $1+a, 1+a^{2}, 1+a^{4}, 1+a^{8}$ will be pairwise coprime.