Найдите все простые для которых p^q+q^2=2^p

[rightways]

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

$$p^q+q^2=2^p$$

[Dmitriy40]

Думаю таких нет. Проверил два диапазона: $p<10^4, q<10^4$ и $p<10^6, q<10^2$, ни одного решения не нашлось.

[ps16015]

Пусть $q\neq 3$ тогда:
$2^p\equiv \pm 1 (\text{mod } 3)\\ q^2\equiv 1 (\text{mod } 3)\\ p^q\equiv \pm 1 (\text{mod } 3)$
Поскольку $\pm 1+1 \neq \pm 1$, решений нет.

Теперь пусть $q=3$ тогда
$p^3+9=2^p $ но
$p>2 \implies p^3>2^p$
А $q=3, p=2$ не является решением.

Таким образом решений нет вообще.

[grizzly]

ps16015 в сообщении #1325507 писал(а):

Пусть $q\neq 3$ тогда:
$2^p\equiv \pm 1 (\text{mod } 3)$
$q^2\equiv 1 (\text{mod } 3)$
$p^q\equiv \pm 1 (\text{mod } 3)$
Поскольку $\pm 1+1 \neq \pm 1$, решений нет.

Слишком просто, чтобы быть правильным. Во-первых, $3^p=0 \bmod 3$, это мелочи. Хуже, что
$5^2+2^2=2^5 \bmod 3$ и это неисправимо, потому как $1+1=-1\bmod 3.$

[Dendr]

Тут ясно, что поскольку q по меньшей мере равно двум, то $p>3$, чтобы выполнялось $2^p>p^2$ - но тогда первое слагаемое нечетно, то есть должно быть $q>2$.

Просто проверим явно, что $q=3$ не подходит: $2^p-p^3=9$. Можно перебором, а можно заметить, что у функции в левой части этого уравнения при $p>0$ один минимум (нуль производной определяется точкой пересечения экспоненты и правой ветви параболы), при этом при $p=10$ она равна 24, а при $p=2, p=9$ - отрицательна. Так что минимум лежит где-то между 2 и 9, а при больших значениях функция монотонно возрастает, следовательно, при целых аргументах она не принимает значения 9.

Таким образом, $q>3$. То есть решения (если таковые имеются) записываются в виде $6n\pm1$.
Так как $p$ - нечетно, то $2^p=2\cdot4^k$, где $k$ - некоторое натуральное число. Но $4^k=4\pmod6$ (для любого $k$!). Следовательно, $2^p=2\pmod6$.
С другой стороны, $q^2=1\pmod6$, а $p^q=p\pmod6$.

Отсюда мы заключаем, что $p=1\pmod6$, т.е. возможное решение может иметь вид $p=6n+1; q=6m\pm1$.
В явном виде: $(6n+1)^{6m\pm1}+(6m\pm1)^2=2\cdot64^n$.
Итак, теперь равенство по модулю 6 (а, следовательно, 2 и 3) соблюдается автоматически, и надо только найти подходящую пару $(n,m)$. Но тут строгая математика пасует - или это я еще не набрел на нужное решение (основание модуля?).

_________________________________________________________

Уходя от целочисленной математики, можно заметить, что $2^p>p^q$, причем разность равна строго $q^2$, которая при росте аргументов много меньше других слагаемых, т.е. легко установить (анализируя аналогично второму абзацу этого сообщения), что область значений $p$ лежит рядом (с большей стороны) с решением уравнения $2^x=x^q$, что эквивалентно $\ln x/x=\ln2/q$.
Это уравнение трансцендентно, так что все это разве что облегчает поиск решений перебором: при выбранном $q$ есть смысл рассматривать очень ограниченный набор $p$: простые числа вида $6n+1$, большие решения указанного уравнения, причем только ближайшие.
Но насколько ближайшие? В первую очередь, обратим внимание, что мы используем здесь решение этого уравнения $x>2$. Но тогда $\ln x>\ln2$, а значит, $1/x<1/q \Rightarrow x>q$

Если $2^x=x^q$, то чему равно $2^{x+1}-(x+1)^q$? Функция эта, очевидно, монотонно возрастает, поэтому как только мы превысим $q^2$, это будет означать, что дальше дальше решений уравнения не будет.
$2^{x+1}-(x+1)^q=2\cdot2^x-x^q-q\cdot x^{q-1}-O(x^{q-2})=x^q-q\cdot x^{q-1}-O(x^{q-2})=x^{q-1}\cdot(x-q)-O(x^{q-2})$
Так как мы установили, что $q\geqslant5$, а $x>q$, то $x^{q-1}\cdot(x-q)>x^{q-1}\geqslant x^4>q^4$. Таким образом, подходящее значение $p$ не может превышать $x+1$ (!). Иными словами - если при данном $q$ есть подходящее значение $p$, то оно равно округлению вверх решения уравнения $\ln x/x=\ln2/q$.

Например, для $q=5$ получаем $x\approx22.44$, то есть может подойти только $p=23$, но оно равно 5 по модулю 6, так что отпадает.
На самом деле решение уравнения $x^5+25=2^x$ отличается от решения $x^5=2^x$ на одну стотысячную, поэтому мои рассуждения совсем нестрогие, даже чересчур щедрые и относятся уже не к математике, а оптимизации программы-перебора.
Но можно сделать следующий вывод: если существует решение исходного уравнения, то решение уравнения $\ln x/x=\ln2/q$ должно быть "почти целым", причем обязательно округляться в большую сторону: $p>x, p-x<<1$ - это еще одна оптимизация перебора: достаточно довести дихотомию до момента, когда интервал поиска меньше единичного, а целое значение либо внутри него, либо вблизи правой границы. Это целое значение и есть кандидат на $p$ при данном $q$, его (и только его) надо подставлять для проверки.

_________________________________________________________

Проверка проверкой, но как доказать строго, пока не ясно.

[ps16015]

grizzly в сообщении #1325514 писал(а):

ps16015 в сообщении #1325507 писал(а):

Пусть $q\neq 3$ тогда:
$2^p\equiv \pm 1 (\text{mod } 3)$
$q^2\equiv 1 (\text{mod } 3)$
$p^q\equiv \pm 1 (\text{mod } 3)$
Поскольку $\pm 1+1 \neq \pm 1$, решений нет.

Слишком просто, чтобы быть правильным. Во-первых, $3^p=0 \bmod 3$, это мелочи. Хуже, что
$5^2+2^2=2^5 \bmod 3$ и это неисправимо, потому как $1+1=-1\bmod 3.$

Вы правы, там чушь написана. Жаль что нельзя удалять сообщения

-- 10.07.2018, 20:10 --

Попытка No2.
$p,q > 2$ Точку (2,2) проверяем в ручную.

Теперь рассмотрим два случая:

Первый: $p \leq q \implies p^q \geq 2^p \implies p^q+q^2>2^p$ тут решений нету.

Второй: $p > q \implies p=q+k$ и уравнение запишется следующим образом: $(q+k)^q + q^2=2^k\cdot 2^q \implies \left( \frac{q+k}{2}\right)^q+\frac{q^2}{2^q}=2^k$
Теперь, если $q\neq 3$ то $\frac{q^2}{2^q}<1$ и $2^k-1<\left(\frac{q+k}{2}\right)^q<2^k \implies 2(2^k-1)^{\frac{1}{q}}<p<2^{\frac{p}{q}}$
Пусть $n$ наибольшее целое число, такое что $n<2(2^k-1)^{\frac{1}{q}}$ докажем что из этого следует что $2^{\frac{p}{q}}<n+1$.
Док-во: $n<2(2^k-1)^{\frac{1}{q}} \implies n^q < 2^{q+k}-2^{q}=2^p-2^q \implies -n^q > 2^q - 2^p$
И $2^{\frac{p}{q}}<n+1 \implies 2^p<(n+1)^q$
Сложим два последних неравенства: $2^q-2^p+2^p<(n+1)^q-n^q$
Разложем через бином Ньютона $2^q$ и $(n+1)^q$: $1+q+\binom{q}{2}+\binom{q}{3}+...+1<qn^{q-1}+\binom{q}{2}n^{q-2}+...+1$ Слева $q+1$ слагаемое, справа $q$ и $\binom{q}{i}(n^{q-i}-1)\geq 0$ таким образом главное неравенство свелось к $qn^{q-1} >q+1}$ что очевидно верно.

Таким образом мы показали что между $2(2^k-1)^{\frac{1}{q}}$ и $2^{\frac{p}{q}}$ нет целых чисел, т.е. что $p$ не существует.

Осталось проверить $p>q=3$. Вроде бы это тоже сводится к неравенствам $2(2^k-1)^{\frac{1}{q}}<p<2^{\frac{p}{q}}$

Проверьте кто-нибудь, пожалуйста(имею ввиду решение, а не случай $q=3$)

[ps16015]

ps16015 в сообщении #1325706 писал(а):

grizzly в сообщении #1325514 писал(а):

ps16015 в сообщении #1325507 писал(а):

Пусть $q\neq 3$ тогда:
$2^p\equiv \pm 1 (\text{mod } 3)$
$q^2\equiv 1 (\text{mod } 3)$
$p^q\equiv \pm 1 (\text{mod } 3)$
Поскольку $\pm 1+1 \neq \pm 1$, решений нет.

Слишком просто, чтобы быть правильным. Во-первых, $3^p=0 \bmod 3$, это мелочи. Хуже, что
$5^2+2^2=2^5 \bmod 3$ и это неисправимо, потому как $1+1=-1\bmod 3.$

Вы правы, там чушь написана. Жаль что нельзя удалять сообщения

-- 10.07.2018, 20:10 --

Попытка No2.
$p,q > 2$ Точку (2,2) проверяем в ручную.

Теперь рассмотрим два случая:

Первый: $p \leq q \implies p^q \geq 2^p \implies p^q+q^2>2^p$ тут решений нету.

Второй: $p > q \implies p=q+k$ и уравнение запишется следующим образом: $(q+k)^q + q^2=2^k\cdot 2^q \implies \left( \frac{q+k}{2}\right)^q+\frac{q^2}{2^q}=2^k$
Теперь, если $q\neq 3$ то $\frac{q^2}{2^q}<1$ и $2^k-1<\left(\frac{q+k}{2}\right)^q<2^k \implies 2(2^k-1)^{\frac{1}{q}}<p<2^{\frac{p}{q}}$
Пусть $n$ наибольшее целое число, такое что $n<2(2^k-1)^{\frac{1}{q}}$ докажем что из этого следует что $2^{\frac{p}{q}}<n+1$.
Док-во: $n<2(2^k-1)^{\frac{1}{q}} \implies n^q < 2^{q+k}-2^{q}=2^p-2^q \implies -n^q > 2^q - 2^p$
И $2^{\frac{p}{q}}<n+1 \implies 2^p<(n+1)^q$
Сложим два последних неравенства: $2^q-2^p+2^p<(n+1)^q-n^q$
Разложем через бином Ньютона $2^q$ и $(n+1)^q$: $1+q+\binom{q}{2}+\binom{q}{3}+...+1<qn^{q-1}+\binom{q}{2}n^{q-2}+...+1$ Слева $q+1$ слагаемое, справа $q$ и $\binom{q}{i}(n^{q-i}-1)\geq 0$ таким образом главное неравенство свелось к $qn^{q-1} >q+1}$ что очевидно верно.

Таким образом мы показали что между $2(2^k-1)^{\frac{1}{q}}$ и $2^{\frac{p}{q}}$ нет целых чисел, т.е. что $p$ не существует.

Осталось проверить $p>q=3$. Вроде бы это тоже сводится к неравенствам $2(2^k-1)^{\frac{1}{q}}<p<2^{\frac{p}{q}}$

Проверьте кто-нибудь, пожалуйста(имею ввиду решение, а не случай $q=3$)

Нет, и тут чушь. Логическая ошибка в "Док-во": $(10>0) + (1>2) \implies (11>2)$

[ps16015]

Если неравенство $n^{\frac{n}{\log_2n}}-n^{\left \lfloor \frac{n}{\log_2n} \right \rfloor}>\left \lfloor \frac{n}{\log_2n} \right \rfloor^2$ верно для $n=2k+1$ то решений у данного уравнения не будет т.к. $n^{\left \lfloor \frac{n}{\log_2n} \right \rfloor+1}>2^n=n^{\frac{n}{\log_2n}}>n^{\left \lfloor \frac{n}{\log_2n} \right \rfloor}+\left \lfloor \frac{n}{\log_2n} \right \rfloor^2$;
Оно эквивалентно

$n\ln(2)-\left \lfloor \frac{n\ln(2)}{\ln(n)} \right \rfloor\ln n>\ln\left(\frac{1}{n}+\frac{\left \lfloor \frac{n\ln(2)}{\ln(n)} \right \rfloor^2}{n^{\left \lfloor \frac{n\ln(2)}{\ln(n)} \right \rfloor+1}} \right)$