Интересная задача, делимость

[rightways]

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

[Sonic86]

Неинтересно: $pq+1$ четно, а - - -
А вот при $q=2$ уже есть решения.

[nnosipov]

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

Неинтересно: $pq+1$ четно, а - - -

Не понял.

Я также не понимаю, зачем нужно, чтобы $q$ было простым --- достаточно, чтобы $q$ было нечётным. Допустим, что что $p^p \equiv 1 \pmod{pq+1}$. Тогда порядок числа $p$ по модулю $pq+1$ равен $p$. В частности, $\varphi(pq+1)$ делится на $p$. Значит, для некоторого нечётного простого делителя $r$ числа $pq+1$ будем иметь $r=pk+1<pq+1$. Но тогда число

$$ \frac{pq+1}{pk+1}=pq_1+1 $$

также делит $pq+1$, при этом $q_1$ является нечётным и $q_1<q$. Ясно, что $p^p \equiv 1 \pmod{pq_1+1}$. Осталось заметить, что делимость $p^p-1$ на $p+1$ невозможна.

[Sonic86]

(я ошибся)

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

Не понял.

Да, оказывается, я ошибся.
Я рассуждал так:
$p^p-1=(p-1)\Phi_p(p)$
$p-1<pq+1$, так что $pq+1\mid \Phi_p(p)$ (это ошибочное рассуждение).
Однако $\Phi_p(p)$ нечетно, а $pq+1$ четно

[Руст]

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

(я ошибся)

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

Не понял.

Да, оказывается, я ошибся.
Я рассуждал так:
$p^p-1=(p-1)\Phi_p(p)$
$p-1<pq+1$, так что $pq+1\mid \Phi_p(p)$ (это ошибочное рассуждение).
Однако $\Phi_p(p)$ нечетно, а $pq+1$ четно

Это не ошибочное, только немного не точное.
Отсюда следует, что $pq+1=dD$, где $d|p-1, D|\Phi_p(p)\to D=(1+2k_1p)(1+2k_2p)...=1\mod 2p$.
Так как $pq+1=1\mod p\to d=1\to 2|q$.

[nnosipov]

Да, простые делители $\Phi_p(p)$ нечётны и поэтому должны быть $\equiv 1 \pmod{2p}$. Это решает вопрос.

[Руст]

Можно еще уточнить. Если $p=3\mod 4$, то q делится на 4.