Простая задача

[nnosipov]

Докажите, что если $q$ --- нечётное простое число и $3^q-1$ делится на $q^2+q+1$, то число $q^2+q+1$ --- простое.

[Sonic86]

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

Докажите, что если $q$ --- нечётное простое число и $3^q-1$ делится на $q^2+q+1$, то число $q^2+q+1$ --- простое.

Наверное, я соль задачи не понял:
$q^2+q+1|3^q-1 \Rightarrow 3|q$ (иначе $3|3^q-1$).
$q$ - простое и $3|q \Rightarrow q=3 \Rightarrow q^2+q+1=13 \in P$.

-- Вт июл 19, 2011 18:49:09 --

А если $q$ - произвольное нечетное число?

-- Вт июл 19, 2011 18:58:33 --

Например, $q=27$ подходит.

[nnosipov]

Sonic86 в сообщении #469692 писал(а):

Наверное, я соль задачи не понял:$q^2+q+1|3^q-1 \Rightarrow 3|q$ (иначе $3|3^q-1$).

А я это не понял. Можно подробнее?

[Equinoxe]

Sonic86, не могу понять Ваш первый вывод
Да, $q=1 \pmod 3$ не может быть, это очевидно, но почему не может быть $q=2 \pmod 3$?
Тогда получаем $n=2 \pmod 3$, где $n = \frac {3^q-1}{q^2+q+1}$

[maxal]

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

Докажите, что если $q$ --- нечётное простое число и $3^q-1$ делится на $q^2+q+1$, то число $q^2+q+1$ --- простое.

Пусть $p$ - простое число делящее $q^2+q+1$. Тогда $p$ также делит $3^q-1$. Так как $q$ - простое, то $q$ делит $p-1$.
Таким образом задача сводится к уже разбиравшейся: $p$ делит $q^3-1$ и $q$ делит $p-1$.
topic47908.html

[nnosipov]

maxal в сообщении #469712 писал(а):

Пусть $p$ - простое число делящее $q^2+q+1$. Тогда $p$ также делит $3^q-1$. Так как $q$ - простое, то $q$ делит $p-1$.
Таким образом задача сводится к уже разбиравшейся: $p$ делит $q^3-1$ и $q$ делит $p-1$.
topic47908.html

И в самом деле, а я как-то не заметил. Выходит, я зря эту задачу предложил. Так что пардон.

[Sonic86]

Equinoxe в сообщении #469711 писал(а):

Sonic86, не могу понять Ваш первый вывод
Да, $q=1 \pmod 3$ не может быть, это очевидно, но почему не может быть $q=2 \pmod 3$?
Тогда получаем $n=2 \pmod 3$, где $n = \frac {3^q-1}{q^2+q+1}$

Да, действительно, наврал
И все-таки, как решать при произвольном $q$?

[maxal]

Sonic86 в сообщении #469770 писал(а):

И все-таки, как решать при произвольном $q$?

При произвольном $q$ задача неверна. Контрпример: $q=19683$.

[Sonic86]

maxal в сообщении #469771 писал(а):

Sonic86 в сообщении #469770 писал(а):

И все-таки, как решать при произвольном $q$?

При произвольном $q$ задача неверна. Контрпример: $q=19683$.

Я имел ввиду найти все нечетные $q:q^2+q+1|3^q-1$. Мы уже нашли $q=3;27;19683$, что, видимо, довольно интересно (т.е. при $q=3^{3^k}$ утверждение верно).

[maxal]

Sonic86 в сообщении #469780 писал(а):

Я имел ввиду найти все нечетные $q:q^2+q+1|3^q-1$. Мы уже нашли $q=3;27;19683$, что, видимо, довольно интересно (т.е. при $q=3^{3^k}$ утверждение верно).

$q=3,27$ неинтересны, так как для них $q^2+q+1$ является простым. Для $q=19683$ оно является составным.