Простая (но олимпиадня!) задача с простыми числами

[nnosipov]

worm2 в сообщении #507830 писал(а):

Если $q=2$, то ...

Просто заметьте, что $p^2+1 \equiv 2 \pmod{4}$ при нечётном $p$.

[vivaldi]

Ну что, выкладывать Ксюшино решение, или до завтра подождать?
Вот TOTAL и Руст ещё не просматривали, авось они додумаются?
Повторяю, решение доступно даже пятикласснику, никаких диофантовых-шмиофантовых там не нужно.

(Оффтоп)

* Это НЕ искусственный подъём

[Руст]

vivaldi в сообщении #508099 писал(а):

Ну что, выкладывать Ксюшино решение, или до завтра подождать?
Вот TOTAL и Руст ещё не просматривали, авось они додумаются?
Повторяю, решение доступно даже пятикласснику, никаких диофантовых-шмиофантовых там не нужно.

(Оффтоп)

* Это НЕ искусственный подъём

Тут уже все решили. По а) надо заметить, что все четные числа скорее всего так представляется (есть такая гипотеза). Если нечетные, то лучше искать в виде $p^k$, где $p^{k-1}+2$ не простое. Проще всего брать $k=3,p>3$.

По б) на мой взгляд проще $3^k+8$. Тогда если $r$ нечетное, то $p=2$ и $2^q-8=3^k+r$. Слева число делится на 3 (при $q>2$), стало быть $r=3$.

[vivaldi]

У Ксюши доказывается, что среди чисел вида $210k+47$ встречается бесконечно много не представимых.
Несложно доказать, что если $210k+47$ представимо, то единственный вариант представления - это $7^p-2$, но числа вида $210k+47$ встречаются через каждые 210, а степени семёрки - всё реже и реже.

[nnosipov]

vivaldi в сообщении #508358 писал(а):

Несложно доказать, что если $210k+47$ представимо, то единственный вариант представления - это $7^p-2$

А почему невозможно равенство $210k+47=2^q-r$ с простыми $q$ и $r$?

[vivaldi]

nnosipov в сообщении #508368 писал(а):

vivaldi в сообщении #508358 писал(а):

Несложно доказать, что если $210k+47$ представимо, то единственный вариант представления - это $7^p-2$

А почему невозможно равенство $210k+47=2^q-r$ с простыми $q$ и $r$?

Если q=2, то 2^q-r$ слишком малО.
Если q>2 и r>3, то 2^q-r$ даёт остаток 1 или 3 при делении на 6.
Если q>2 и r=3, то 2^q$ делится на 5.
Если q>2 и r=2, то 2^q-r$ - чётное.

[nnosipov]

Теперь понятно.

[vivaldi]

nnosipov в сообщении #508381 писал(а):

Теперь понятно.

Так Ксюшино решение верно?

Вот museum с мехмата предложил похожее решение:

http://www.mathforum.ru/forum/read/1/44314/