Олимпиада имени Леонарда Эйлера 2016-2017 учебный год, II тур заключительного этапа

Дано нечётное натуральное число $a$, большее 100. На доску выписали все натуральные числа вида $\frac{a-{{n}^{2}}}{4}$, где $n$ — натуральное число. Оказалось, что при $n\le \sqrt{a/5}$ все они простые. Докажите, что и каждое из остальных выписанных на доску натуральных чисел простое или равно единице. ( А. Храбров )

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

Если $a$ при делении на $4$ дает остаток $3$, на доске вообще нет целых чисел , потому что квадраты при делении на $4$ могут давать только остатки $0$ или $1$.В этом случае утверждение задачи ,очевидно, верно.Дальше считаем , что $a$ дает при делении на $4$ остаток $1$. Тогда , полагая $n=1$ , получаем $a = 4p+1$ , где $p = \frac{a-1}{4} -$ простое.Заметим , что число $\frac{a-n^2}{4}$ является целым тогда и только тогда ,когда $n$ нечётно. Поскольку при нечётном $n$ разность $p -\frac{a-n^2}{4} = \frac{n^2-1}{4}$ чётна , все целые числа вида $\frac{a-n^2}{4}$ нечётны.

Пусть для некоторого $a$ условие задачи выполнено , а утверждение - нет.

Рассмотрим наименьшее такое $n$ , что число $b = \frac{a-n^2}{4}-$ составное.Обозначим через $u$ его наименьший простой делитель .Так как $n > \sqrt{a/5}$,выполнено неравенство $b = \frac{a-n^2}{4} < a/5$ . Поэтому $u<\sqrt{a/5}<n,$ откуда $-n<n-2u<n.$Значит , $(n-2u)^2<n^2$,причём $n-2u$ не равно $0$ , так как $n$ нечётно.Легко видеть , что число $\frac{a-(n-2u)^2}{4}$ натуральное, делится на $u$ и больше $b$, то есть оно не простое и не единица следовательно , число $|n-2u|$ ,меньшее, чем $n$ , также порождает составное натуральное число, что противоречит минимальности $n$.

Условие задачи выполнено, например ,для $a=173.$