Почти числа Ферма

[Nikys]

Доказать, что существует бесконечное множество натуральных чисел $n$, что $2^{2^n+1} + 1$ делится на $n$, а $2^n + 1$ не делится на n.

[Sonic86]

$n$ нечетно.
(Сначала обнаруживаем, что $n=3^k$ удовлетворяют первому условию, но не удовлетворяет второму)
Докажем по индукции, что $n=m\cdot 3^k, k\geqslant 1, 2\not| m$ удовлетворяет 1-му условию.
Пусть существует $n:n\mid 2^{2^n+1}+1$, докажем, что $3n\mid 2^{2^{3n}+1}+1$. Видим, что $2^{2^{3n}+1}+1=2^{(2^n+1)(2^{2n}-2^n+1)}+1=2^{2^n+1}\sum\limits_{k=0}^{2^{2n}-2^n}(-1)^k2^{k(2^n+1)}.$ 1-й множитель делится на $n$ по предположению индукции, а 2-й - на $3$:
$\sum\limits_{k=0}^{2^{2n}-2^n}2^{k(2^n+1)}\equiv\sum\limits_{k=0}^{2^{2n}-2^n}(-1)^k(-1)^{k(2^n+1) \mod 2}\equiv\sum\limits_{k=0}^{2^{2n}-2^n}1\equiv 2^{2n}-2^n+1$ $\equiv 1+1+1\equiv 0\pmod 3.$
(В качестве $m$ подходят $19;163;571$. Можно ли их как-то охарактеризовать? )
Докажем, что при $m=571$ $n=m\cdot 3^k, k\geqslant 2$ удовлетворяет 2-му условию. Это следует из $(\forall k)2^{m3^k}\not\equiv -1\pmod m$. От противного: $571$ - простое, значит $2^{571\cdot 3^k}+1\equiv 0\pmod{571}\Leftrightarrow 2^{\cdot 3^k}+1\equiv 0\pmod{571}$. $2$ - образующая по модулю $571$, значит $\Leftrightarrow 3^k\equiv \frac{570}{2}\pmod{570}$. Это сравнение решения не имеет: правая часть и модуль делятся на $5$, а $3^k$ - нет.
(с числами $19;163$ так не получается, поскольку они имеют вид $1+2\cdot 3^t$)

[Nikys]

Цитата:

$n$ нечетно.

Нууу, да, иначе бы первое условие было невозможно...)
Кстати, довольно интересное и конкретное решение. Ещё можно применить теорему Эйлера вида $(2^{3^n}+1)(2^{3^n}-1) = 2^{2\cdot3^n} - 1 \equiv 0 \pmod {3^{n+1}}$ и, поскольку $2^{3^n} - 1 \equiv 1 \pmod 3$, то $2^{3^n} + 1 \equiv 0 \pmod {3^{n+1}}$.
Потом взять простой делитель $p_n > 3$ выражения $2^{2\cdot3^n} - 2^{3^n} + 1 $, показав, что он не делитель выражения $2^{3^n} + 1$ и создать числовую последовательность $a_n = 3^n p_n$, по которой уже и доказывать нужное.

[temp03]

Nikys
$2^n+1$ делится на $n$ тогда и только тогда, когда $n=3$.

[nnosipov]

temp03 в сообщении #546326 писал(а):

$2^n+1$ делится на $n$ тогда и только тогда, когда $n=3$.

Это неверно, таких $n$ бесконечно много.

[temp03]

Например?

[nnosipov]

Sonic86 в сообщении #546197 писал(а):

Сначала обнаруживаем, что $n=3^k$ удовлетворяют первому условию, но не удовлетворяет второму

[temp03]

Да.

[Nikys]

temp03
Например, n={1,3,9...}
Можете проверить:
$\frac {2^9 + 1}{9} = \frac {513}{9} = 57$
$\frac {2^{27}+1}{27} = \frac {134217729}{27} = 4971027$
Можете попроверять для других степеней тройки.

[Sonic86]

(Оффтоп)

Nikys в сообщении #546301 писал(а):

Цитата:

$n$ нечетно.

Нууу, да, иначе бы первое условие было невозможно...)

Я не утверждал, я просто сделал вывод и забыл написать, что я делаю вывод а не утверждаю