Республиканская олимпиада по математике, 2017 год, 11 класс

Докажите, что существуют бесконечно много составных натуральных чисел $n$, для которых число ${{2}^{\frac{n-1}{2}}}+1$ делится на $n$. ( Ануарбеков Т. )

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

Комментарии от администратора Комментарии от администратора №1.     b>Решение №1. Докажем, что все числа вида $n=\frac{{{4}^{p}}+1}{5}$, где $p > 5$ простое число удовлетворяют условию задачи ($n$ — целое, так как ${{4}^{p}}+1\equiv {{\left( -1 \right)}^{p}}+1\equiv 0 \pmod 5)$.
Сначала докажем, что $n$ — составное. Действительно, пусть $a={{2}^{\frac{p-1}{2}}} > 5$. Тогда $n=\frac{4{{a}^{4}}+1}{5}=\frac{\left( 2{{a}^{2}}-2a+1 \right)\left( 2{{a}^{2}}+2a+1 \right)}{5}-$составное, так как $2{{a}^{2}}+2a+1 > 2{{a}^{2}}-2a+1 > 5$. По малой теореме Ферма ${{4}^{p-1}}-1\vdots p$, значит $\frac{n-1}{2}=2\frac{{{4}^{p-1}}-1}{5}=2pk$, где $k$ — нечетное число. Тогда ${{2}^{\frac{n-1}{2}}}+1={{2}^{2pk}}+1\vdots {{2}^{2p}}+1\vdots \frac{{{2}^{2p}}+1}{5}=n$, что и требовалось доказать.

Комментарии от администратора Комментарии от администратора №2.     Решение №2. Рассмотрим последовательность: ${{a}_{1}}=17 \cdot 257$ и ${{a}_{n+1}}={{2}^{{{a}_{n}}}}-1$ при всех $n\ge 1$. Индукцией легко доказать, что ${{a}_{n}}-$составное и ${{2}^{{{a}_{n}}-1}}-1\vdots 3{{a}_{n}}$. Тогда все числа вида $\frac{{{2}^{{{a}_{n}}}}+1}{3}$ — удовлетворяют условию задачи.

любое простое $n$ вида $8a+3$

докажите что таких простых бесконечно

составное же нужно