2^n + 1 = p q^2

[maxal]

Докажите, что если $2^n+1=pq^2,$ где целое число $n>10$, а число $p$ - простое, то $q=1$.

P.S. предыстория.

P.S.#2 Нижняя грань для $n$ поднята до $n>10$.

[worm2]

Или я чего-то не понимаю, или $2^{10}+1=41\cdot5^2$.

[juna]

Можно было бы поднять до $n>10$.
$\forall k:2^{10(2k+1)}+1\equiv 0 \mod 41\cdot 5^2$
Похоже есть еще только одно число, которое доставляет квадрат в разложении
$\forall k:2^{3(2k+1)}+1\equiv 0 \mod 3^2$
Если для первого утверждение maxalа очевидно (таких $p$ просто нет), то для второго - как это доказать - я не знаю.
Более того, интересно было бы доказать или опровергнуть, что других чисел, кроме, 3, 5, доставляющих квадрат нет.

[maxal]

Ага, маленький контр-пример это тоже хорошо. Тогда возникает вопрос о конечности числа решений. И в частности, о справедливости рассматриваемого утверждения для $n>16$ (именно такая нижняя грань была указана для $n$ в исходной теме).

[juna]

Maxal, я так понимаю, у Вас нет решения?
Тогда почему олимпиадный раздел?

[maxal]

Полного решения нет, есть отдельные идеи, но я думаю, что задача вполне решаемая. И для олимпиадного раздела она больше всего подходит, впрочем если кто-то докажет, что эта задача сложная - перенесем в корень.

[maxal]

juna писал(а):

Более того, интересно было бы доказать или опровергнуть, что других чисел, кроме, 3, 5, доставляющих квадрат нет.

Таких простых очень много на самом деле. Вот такие простые $p<100$ и ополовиненные мультипликативные порядки $2$ по модулю $p^2$:

3 3
5 10
11 55
13 78
17 68
19 171
29 406
37 666
41 410
43 301
53 1378
59 1711
61 1830
67 2211
83 3403
97 2328

Например, для $p=11$:

$$2^{55(2k+1)}+1\equiv 0\pmod{11^2}$$

См. также последовательность A014662 в OEIS.

[juna]

Да, действительно, если $2^{2k}\equiv 1 \mod p$, то $(2^k-1)^2(2^k+1)^2\equiv 0 \mod p^2$, т.е. $2^k\equiv -1 \mod p^2$.
Выскажу еще некоторые простые факты (которые меня ни к чему не привели) по исходной задаче:
1. если $n\equiv 0 \mod 2$, то $p\equiv 1 \mod 4$, $q=n_1^2+m_1^2$, $q^2=n_2^2+m_2^2$
2. любое число $2^n$ при $n>2$ представимо в форме $7y^2+x^2$
3. и совсем просто: если $n\equiv 1 \mod 2$, то либо $2^{n-1}-2^{n-2}+..+1=q^2$, либо $2^{n-1}-2^{n-2}+..+1=3^{2k+1}q^2p$

[maxal]

juna писал(а):

Да, действительно, если $2^{2k}\equiv 1 \mod p$, то $(2^k-1)^2(2^k+1)^2\equiv 0 \mod p^2$, т.е. $2^k\equiv -1 \mod p^2$.

Это неверное рассуждение. Согласно ему, из $2^2\equiv 1\pmod 3$ следует, что $2^1\equiv -1\pmod{3^2}$ - нонсенс.

[juna]

Да. Порядок получается $\frac{p(p-1)}{2}$

[maxal]

Это скорее полупорядок (то есть половина порядка), но и то не всегда. Например, для $p=17$, порядок $2$ по модулю $p^2$ равен $\frac{p(p-1)}{2}=136$, а полупорядок соответственно $\frac{p(p-1)}{4}=68.$

[Коровьев]

Таких чисел бесконечно много. Доказывается почти элементарно с помощью теоремы
Если
$a\equiv b(modp)$
$p$ - простое, то
$a^p\equiv b^p(modp^2)$
/$a^{p-1}+a^{p-1}b+...+ab^{p-1}+b^{p-1}\equiv pa^{p-1}\equiv 0(modp)$/
Далее из теории чисел
Существует такое $t$, что
$2^t+1\equiv 0(modp)$
/Если $2$ не является квадратичным вычетом по модулю $p$, то можно взять $t=\frac{p-1}{2}$, в противном случае $t$, есть делитель $\frac{p-1}{2}$. /
тогда
$2^t^p+1\equiv 0(modp^2)$

[maxal]

Коровьев писал(а):

Далее из теории чисел
Существует такое $t$, что
$2^t+1\equiv 0(modp)$

Это неверно. Такого $t$ не существует уже хотя бы для $p=7$.

Добавлено спустя 5 минут 16 секунд:

Но доказать бесконечность количества таких простых действительно легко, например, воспользовавшись теоремой Зигмонди.

[Коровьев]

maxal писал(а):

Коровьев писал(а):

Далее из теории чисел
Существует такое $t$, что
$2^t+1\equiv 0(modp)$

Это неверно. Такого $t$ не существует уже хотя бы для $p=7$.

Добавлено спустя 5 минут 16 секунд:

Но доказать бесконечность количества таких простых действительно легко, например, воспользовавшись теоремой Зигмонди.

Да, ошибка
Правильно так
Если $2$ не является квадратичным вычетом по модулю $p$, то существует такое $t$, что

А это выполняется для всех простых чисел вида $p=8k\pm 3$
$2$ является квадратичным вычетом для всех $p=8k\pm 1$
И ещё.
В любой арифметической прогрессии $an+b$ и $(a,b)=1$ содержится бесконечно много простых чисел/Дирихле/.

[juna]

Не знаю как с Зигмонди, а рассуждение Коровьева проходит и получается, что если $p=8k\pm 3$, то $2^{\frac{p(p-1)}{2}}+1\equiv 0\mod p^2$.
Для $p=8k+1$ если $2^{\frac{p-1}{4}}\equiv -1 \mod p$, то $2^{\frac{p(p-1)}{4}}+1\equiv 0 \mod p^2$
Можно возвращаться к исходной задаче.