35-я Балканская математическая олимпиада. Белград, Сербия, 2018 год

Найдите все пары простых чисел $(p,q)$ таких, что число $11^p+17^p$ делится на $3p^{q-1}+1$.

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

$Ответ:$ $(3,3)$.

Сначала мы избавимся от нескольких крайних случаев:

Проверяя $p=2$ has не имеет решений

Проверяя $p=3$ имеет единственное решение $(3,3)$.

$Утверждение:$ Каждое простое число, делящий $11^p+17^p$, является либо $2$, либо $7$, либо $1 \pmod p$.

$Д-во:$ Рассмотрим простое число $r$, которое делит $11^p+17^p$. Очевидно, что $r \ne 17$. Очевидно, что $(-11/17)^p \equiv 1 \pmod r$, поэтому либо $-11/17 \equiv 1 \pmod r$ Значит, $r \mid 28$, или $-11/17$ имеет показатель $p$, в зависимости от этого

Таким образом, мы находим $3p^{q-1}+1$ произведение $2$, $7$, и $1 \pmod p$ простых чисел.

Теперь мы рассмотрим несколько новых случаев:

[*]Если $p \ne 7$ и $q \ne 2$, тогда $3p^{q-1}+1 \equiv 4 \pmod 8$, в то время как $\nu_7(11^p+17^p) = 1$. Поэтому мы должны иметь $$3p^{q-1} + 1 = 2^2 \cdot 7^{0\text{ или }1} \cdot \left( \text{$1 \bmod p$ простых чисел } \right).$$ Это означает, что либо $1 \equiv 4 \pmod p$ либо $1 \equiv 28 \pmod p$, а это дает нам $p = 3$.

[*]Если $p = 7$, тот же результат, за исключением того, что степень $7$ должно быть точно равно $0$ (несмотря на то что $\nu_7(11^p+17^p)=2$).

[*]Если $q=2$, тот же самый пример работает, за исключением того, что нам нужно дополнительное утверждение, что $11^p+17^p \not\equiv 0 \pmod 8$; следовательно $$3p + 1 = 2^{1\text{ или }2} \cdot 7^{0\text{ или }1} \cdot \left( \text{$1 \bmod p$ простых чисел } \right).$$ Следовательно, у нас есть один дополнительный случай $(p,q) = (13,2)$ проверяя несложно убедиться что оно не подходит.

Это дает полное доказательство того, что $(p,q) = (3,3)$ является единственным решением.

Пусть $r$ — нечетное простое число, делящее $3p^{q-1}+1$, следовательно, $r$ делит $11^p+17^p$. ( если $p$ нечетно, то мы имеем $3p^{q-1}+1 \equiv 4 \pmod 8$, и поскольку это число явно больше $4$, мы знаем, что оно должно иметь нечетный простой делитель, и если $p$ равен $2$, наше число нечетное, и поэтому наша гипотеза очевидна)

Если $p$ равен $2$, мы проверяем вручную.

У нас есть $11^p \equiv -17^p \pmod r$, поэтому $(\frac {11}{17})^{2p} \equiv 1 \pmod r$. Пусть порядок $(\frac {11}{17})$ равен $x$. Таким образом, $x$ делит и $r-1$, и $2p$, и, поскольку оно не может быть нечетным, оно должно быть либо $2$, либо $2p$. Если это $2$, мы получаем, что $r$ делит $168$, и, поскольку $r$ нечетно, а не $3$, оно должно быть $7$. Если $x$ равен $2p$, мы имеем $r \equiv 1 \pmod {2p}$. Учитывая это, получаем $3p^{q-1}+1=4^m7^ny$, где $(y,14)=1$ и $y\equiv 1 \pmod p$. По LTE мы получаем, что $n$ равно $2$, если $p=7$ (проверяем вручную), или $n\le 1$. Кроме того, $m=1$.

Взяв $\pmod p$, мы получим $1 \equiv 4,28 \pmod p$, то есть $0 \equiv 3, 27 \pmod p$. Таким образом, $p=3$ и, после некоторых рассуждений, $q=3$. Таким образом, единственное решение — $(3,3)$.

Редактировать:

Ой, забыл про $q=2$. Если существует простое число $r$, которое делит $3p+1$ и $r$ не равно $7$, действуем, как раньше. если $3p+1$ является степенью $2$, то ее показатель должен быть четным.

Таким образом, $3p=(2^x-1)(2^x+1)$, и поэтому $x$ равно $1$ или $2$, что означает, что $p$ равно либо $3$, либо $5$. Получаем противоречие в обоих случаях.

Если $7$ делит $3p+1$, то $3p+1=2^k7$. $11^p$ — это либо $3$, либо $1$ $\pmod 8$, а $17^p$ — это $1$ $\pmod p$. Таким образом, $k\le 2$, и мы проверяем случаи вручную