Уравнение в простых числах из Japan TST 2016

[rightways]

Найдите все простые $p<q<r<s$ для которых

$$p^s-r^q=3.$$

[EtCetera]

По-видимому, ничего кроме $2^7 - 5^3=3$ нет.

[renatxat]

Это не из Japan TST 2016.

[Dmitriy40]

До $s<10^6$ других решений не нашёл.
Причём требования простоты и неравенств излишни, достаточно потребовать чтобы все числа были не менее 2, можно даже одинаковые, всё равно других решений нет (до $10^3$).

С другими разностями есть такие решения:
$3^3-5^2=2$
$2^3-2^2=4$
$3^2-2^2=5$
$2^5-3^3=5$
$2^4-3^2=7$
$2^5-5^2=7$
$2^7-11^2=7$
$2^{15}-181^2=7$
$312^2-46^3=8$
$6^2-3^3=9$
$5^2-2^4=9$
$15^2-6^3=9$
$253^2-40^3=9$
$3^3-2^4=11$
$6^2-5^2=11$
$56^2-5^5=11$
$15^3-58^2=11$
$2^4-2^2=12$
$7^2-6^2=13$
$17^3-70^2=13$
$2^6-7^2=15$
$5^2-3^2=16$
$2^5-2^4=16$
$3^4-2^6=17$
$23^2-2^9=17$
$282^2-43^3=17$
$375^2-52^3=17$
$3^3-3^2=18$
$3^5-15^2=18$
$12^2-5^3=19$
$10^2-3^4=19$
$7^3-18^2=19$
$6^2-2^4=20$
$6^3-14^2=20$
Только с разными простыми слева:
$5^3-11^2=4$
$47^2-13^3=12$
$19^2-7^3=18$
$83^2-19^3=30$
$37^2-11^3=38$
$13^2-5^3=44$
$7^3-17^2=54$
$3^5-13^2=74$
$5^3-7^2=76$

[Sonic86]

renatxat в сообщении #1506078 писал(а):

Это не из Japan TST 2016.

а откуда это?

(жалкие попытки, основанные на модулярном подходе)

Ясно, что $p=2$, а $q,r,s\equiv 1\pmod 2$, а из $q<r<s$ следует $r\geqslant 5$. Простым перебором значений $s$ получаем $s\geqslant 5$.
Если $r=5$, то получаем задачу, решенную в topic61711.html .
Пусть $r>5$.
Берем уравнение по $\mod 8$: $r^q\equiv -3 \Leftrightarrow r\equiv 5\pmod 8 \Rightarrow \frac{r-1}{4}$ - нечетно.
$s:=2s_1+1$.
По $\mod 3$: $2\cdot 4^{s_1}-r^q\equiv 3\pmod 3 \Leftrightarrow r^q\equiv -1\pmod 3 \Leftrightarrow r\equiv -1\pmod 3$.
По $\mod 5$: $2\cdot 4^{s_1}-r^q\equiv 3\pmod 5 \Leftrightarrow r^q\equiv -3+2(-1)^{s_1}\equiv -1;0\pmod 5$. Но $r\neq 5$ и $r$ - простое, значит $r\not\equiv0\pmod 5$, значит $s_1\equiv 0\pmod 2$ и $r^q\equiv -1\pmod 5$ $\Rightarrow r\equiv -1\pmod 5$ и $s\equiv 1\pmod 4$
По $\mod (r-1)$: $2\cdot 4^{s_1}\equiv 4 \pmod{r-1} \Leftrightarrow 2\cdot 4^{s_1-1}\equiv 1 \pmod{\frac{r-1}{4}} \Rightarrow$ $\left(\frac{2}{\frac{r-1}{4}}\right)=1 \Leftrightarrow \frac{r-1}{4}\equiv \pm 1\pmod 8 \Leftrightarrow r\equiv 1\pm 4\pmod {32}$. Но $r\equiv 5\pmod 8$, значит $r\equiv 5\pmod {32}$.
По $\mod {32}$: $-5^q\equiv 3\pmod {32}$, откуда $q\equiv 3\pmod{8}$
По $\mod 17$: $s=1+4s_2, q=3+8q_3$: $2\cdot 16^{s_2}-r^3r^8\equiv 3\pmod {17} \Leftrightarrow \pm r^3\equiv -3\pm 2\equiv -1;-5\pmod {17}$ $ \Leftrightarrow r\equiv \pm 1; \pm 11 \pmod{17}$.
Пока что мы получили пачку ограничений на $r$, которым, без учета простоты $r$ удовлетворяет $\frac{1}{3}\cdot\frac{1}{5}\cdot\frac{1}{32}\cdot\frac{4}{17} \approx 0.00052$ - довольно мало чисел. (было бы интересно увидеть минимальное простое $r$, которое им удовлетворяет, для опытов)
Дальше мы можем заниматься вот чем: пусть $p$ - простое, не удовлетворяющее ограничениям на $r$. Значит $r\neq p$, а в силу простоты $r\not\equiv 0\pmod p \Leftrightarrow 2^s\not\equiv 3\pmod p$. Например при $p=23$ мы получаем $s\not\equiv 8 \pmod{11}$. Поскольку $s$ стоит в показателе, на нее будут накладываться ограничения по модулям типа $\varphi(p)$, а поскольку сравнение $2^s\not\equiv 3\pmod p$ не очень тривиально, то можно надеятся на подбор конечного множества $p$ таких, что все решения $s\equiv s_p\pmod {\varphi(p)}$ покроют всевозможные значения $s$ (т.е. эффекта чисел Серпинского для генератора $2^s-3$, т.е. в случае, если $2^s-3$ порождает конечное множество простых чисел. Хотя скорее всего я ошибаюсь, но может быть так можно суметь подобрать более сильные ограничения на $s$. )

[Sonic86]

(и еще немного)

Возьмем уравнение по модулю $s$:
$2-r^q\equiv 3\pmod s \Leftrightarrow r^q\equiv -1\pmod s$. Если $q\nmid s-1$, то тогда $r\equiv -1\pmod s \Leftrightarrow s\mid r+1 \Rightarrow s\leqslant r+1$, что противоречит условию $q<r<s$. Значит $q\mid s-1$, т.е. $s=1+qk$. Подставляем:
$2\cdot 2^{kq}-r^q=3$. Можно обозначить $u=2^k$ и решать уравнение $2u^q-r^q=3$. Решения, если бы они были, следовало бы искать из наилучших приближений $\sqrt[q]{2}\approx \frac{r}{u}$. Но у меня на этом пути пока ничего не получилось.