Остатки, свободные от квадратов

[Ktina]

Пожалуйста, проверьте решение. Слишком длинно и запутанно вышло.


Задача:
Простое число $p$ при делении на любое другое простое число $q$ даёт остаток, не делящийся ни на какой квадрат натурального числа, большего 1. Найти все такие простые $p$.
(Источник: Кубок Памяти Колмогорова)

Решение:
Числа 2, 3, 5, 7 и 13 удовлетворяют условию. Число 11 не удовлетворяет, так как даёт остаток 4 при делении на 7.

Рассмотрим все простые $p>13$.


Если $p-4$ делится на простое число, большее 3, то $p$ даёт остаток 4 при делении на это простое число, значит такое $p$ нам не годится.

Осталось рассмотреть все простые вида $p=3^n+4$


Если $p-8=3^n-4$ делится на простое $q>7$, то $p$ даёт остаток 8 при делении на $q$, то есть не годится.
Задача сводится к решению уравнения $3^n-4=5^m\cdot7^k$

Случай 1:
Если $m=0$, то имеем $3^n-4=7^k$, что невозможно по модулю 3.

Случай 2:
Пусть $m>0$
Поскольку $5^m\cdot7^k$ оканчивается на 5, наша степень тройки должна оканчиваться на 9, то есть показатель этой степени даёт остаток 2 по модулю 4.
Таким образом, имеем $(3^a+2)(3^a-2)=5^m\cdot 7^k$, причём $a$ нечётно, а значит, $3^a$ даёт остаток 3 при делении на 4.

То есть, мы имеем два числа, дающие остаток 1 при делении на 4, одно из которых равно $5^m$, а другое $7^k$.
Но тогда и $m$ и $k$ должны быть чётными, то есть перед нами разность квадратов, равная 4 -- противоречие.

Таким образом, ответ на задачу получается 2, 3, 5, 7, 13

[nnosipov]

Ktina в сообщении #688438 писал(а):

Слишком длинно и запутанно вышло.

Посмотрел у себя --- текст примерно такого же объема. Но, в принципе, ничего сложного, стандартные идеи. Так что у Вас, скорее всего, всё окей.

[Ktina]

nnosipov,
Уже нашла у себя грубейшую ошибку в случае 2.
Сейчас буду исправлять.

[nnosipov]

Ktina в сообщении #688447 писал(а):

Уже нашла у себя грубейшую ошибку в случае 2.

Кстати, действительно, у меня в конце вылезает девятка в остатке, а у Вас я её не заметил. Да мелочи всё это Исправите, и все дела.

[Ktina]

Случай 2:
Пусть $m>0$
Поскольку $5^m\cdot7^k$ оканчивается на 5, наша степень тройки должна оканчиваться на 9, то есть показатель этой степени даёт остаток 2 по модулю 4.
Таким образом, имеем $(3^a+2)(3^a-2)=5^m\cdot 7^k$, причём $a$ нечётно, а значит, $3^a$ даёт остаток 3 при делении на 4.

То есть, мы имеем два числа, дающие остаток 1 при делении на 4, одно из которых равно $5^m$, а другое $7^k$.
Тогда приходим к уравнению $49^a\pm 4=5^m$, которое имеет единственное решение $a=0, m=1$
Почему? Потому что $49^a$ оканчивается либо на 01 либо на 49. То есть, наше $5^m$ должно оканчиваться либо на 05, либо на 45, а это возможно только при $m=1$, что и даёт нам ответ $p=13$.

Таким образом, ответ на задачу получается 2, 3, 5, 7, 13

Теперь правильно?

-- 26.02.2013, 15:38 --

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

Ktina в сообщении #688447 писал(а):

Уже нашла у себя грубейшую ошибку в случае 2.

Кстати, действительно, у меня в конце вылезает девятка в остатке, а у Вас я её не заметил. Да мелочи всё это Исправите, и все дела.

Там ошибка не в этом.
$5^m$ всегда даёт 1 при делении на 4, а не только тогда, когда оно квадрат. Из-за этого второй случай рассыпается, как карточный домик.
Но я уже исправила. Надеюсь, теперь всё верно.

[nnosipov]

Ktina в сообщении #688451 писал(а):

Теперь правильно?

Не вижу ошибки. Но, честно говоря, длинно как-то, поэтому мог и проворонить. У меня немного покороче вышло.

[Ktina]

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

У меня немного покороче вышло.

Интригуете?

-- 26.02.2013, 15:59 --

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

Кстати, действительно, у меня в конце вылезает девятка в остатке, а у Вас я её не заметил.

Кстати, действительно, не поняла. Это Вы о чём?

[nnosipov]

Для $p=3^n+4$ при чётном $n$ я рассматривал $p-9$ (а при нечётном $n$ --- $p-8$).