Математикадан облыстық олимпиада, 2009-2010 оқу жылы, 11 сынып

Кез келген $k$ натурал саны үшін $2^{n^2}+1$ саны $n^3$ санына қалдықсыз бөлінетіндей және дәл $k$ әр түрлі бөлгіші болатындай $n$ натурал саны табылатынын дәлелдеңіздер.

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

Это задача решается аналогично как задача $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$.