Областная олимпиада по математике, 2010 год, 11 класс

Докажите, что для любого натурального числа $k$ существует натуральное число $n$, имеющее ровно $k$ различных простых делителей, и такое, что $2^{n^2}+1$ делится нацело на $n^3$.

Комментарий/решение

Это задача решается аналогично как задача $IMO2000$:

https://artofproblemsolving.com/community/c6h57607p354115

А как строить рекурсию?

Что вы имеете в виду говоря «рекурсия»?

Там в решении берется $n_{k+1}=3pn_k$. Но в этом решении это не работает. А как нужно взять $n_{k+1}$ относительно $n_k$?

Достаточно взять $n_{k+1}=pn_{k}$, где $p$ простое число делящая $2^{n_{k}^2}+1$, но не делящая $2^{n_{k-1}^2}+1$. Я думаю что вы понимаете что найдётся такое $p$.