2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Найдите все простые для которых p^q+q^2=2^p
Сообщение19.05.2018, 11:39 


24/12/13
351
Найдите все простые числа $p$ и $q$ для которых
$$p^q+q^2=2^p$$

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение07.07.2018, 13:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение09.07.2018, 19:06 


09/07/18
9
Пусть $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$ не является решением.

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

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение09.07.2018, 19:47 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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.$

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение10.07.2018, 11:18 


02/04/18
240
Тут ясно, что поскольку 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$, его (и только его) надо подставлять для проверки.
_________________________________________________________

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

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение10.07.2018, 18:18 


09/07/18
9
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.$

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

-- 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$)

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение10.07.2018, 19:30 


09/07/18
9
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.$

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

-- 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)$

 Профиль  
                  
 
 Re: Найдите все простые для которых p^q+q^2=2^p
Сообщение18.07.2018, 15:27 


09/07/18
9
Если неравенство $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)$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group