n|2^n+1

[maxal]

Артамонов Ю.Н. писал(а):

Вольфрам писал(а):

If $p|2^n\pm 1$ with $p$ and $n$ relatively prime, then $p$ is a Wieferich prime iff $p^2$ also divides $2^n\pm 1$.

В виду того, что порядок 2 по модулю $p^2$ обязан делить $\varphi(p^2)=(p-1)p,$ то $p$ является Wieferich prime коль скоро порядок 2 по модулю $p^2$ меньше $p.$ Действительно, если порядок 2 по модулю $p^2$ меньше $p,$ то он не может содержать множителя $p,$ а поэтому будет делить $p-1,$ и поэтому $p^2$ делит $2^{p-1}-1.$
Отсюда все следует.

[икс и грек]

Найти все нечётные $n$ такие, что $n|3^n+1$.

[Руст]

Только $n=1$.
Если $n=pm$, где p максимальный простой делитель и $n|3^n+1$, то должно быть $m|3^m+1$.
Таким образом доходим до простого m. Но для нечётных простых это не выполняется.

[maxal]

Найдите все нечётные натуральные числа $n$, которые делят число $2^{n-1}+1$.

[Батороев]

maxal в сообщении #291424 писал(а):

Найдите все нечётные натуральные числа $n$, которые делят число $2^{n-1}+1$.

Простые числа сразу исключаются.

Для составных, вроде, проходят такие рассуждения:

Если $2^{n-1}\equiv (-1)\pmod n$,
то $2^{2(n-1)}\equiv 1 \pmod n$
или $4^{n-1}\equiv 1 \pmod n$.
Следовательно, решением являются числа, псевдопростые по основанию 4, но непсевдопростые по основанию 2.

У таких чисел $n=p_1\cdot p_2\cdot p_3...$

для нечетного числа простых множителей должно быть: $2^{n-1} \equiv (-1)\pmod p $ по основанию этих простых множителей, т.е. отношение $\frac {2(n-1)}{p-1}$ должно быть нечетным целым числом и $a^2\not \equiv 2\pmod p$ (где $a$ - любые числа, взаимнопростые с $n$),
для остальных простых множителей: $2^{n-1} \equiv 1\pmod p$.

В общем, суровые числа.

[maxal]

Батороев
Укажите хотя бы одно такое число $n>1$.

[Батороев]

По-видимому, таких чисел нет. Иначе в случае $n$ составного это противоречило бы тесту Миллера-Рабина.
Для простых это невозможно по Малой теореме Ферма.

[maxal]

Батороев в сообщении #291589 писал(а):

По-видимому, таких чисел нет. Иначе в случае $n$ составного это противоречило бы тесту Миллера-Рабина.

Как именно?

[age]

Интересная задача.
Если $n\ |\ 2^{n-1}+1$, то $n\ |\ 2^n+2$, т.к. $n$-нечетно.

Таких чисел нет. Более того $n\ |\ (a^{n-1}+1)$ таких чисел нет ни для каких $a$.

[maxal]

age в сообщении #291613 писал(а):

Таких чисел нет.

Докажите.

[age]

Если $n\ |\ (2^n+2)$, то
$(1+1)^n+2=\left(2+n+\dfrac{n(n-1)}{2}+...+\dfrac{n(n-1)}{2}+n+2\right)\div n$
Или
$\left(4+n\left(2+(n-1)+\dfrac{(n-1)(n-2)}{3}+\dfrac{(n-1)(n-2)(n-3)}{12}+...\right)\right)\div n$

Ввиду того, что каждое слагаемое в левой части содержит различные множители $n$, то их сумма (слагаемых) не может делиться на все множители одновременно (или $n$).

[maxal]

age в сообщении #291621 писал(а):

Ввиду того, что каждое слагаемое в левой части содержит различные множители $n$, то их сумма (слагаемых) не может делиться на все множители одновременно (или $n$).

Это неверное утверждение.
Например: $\left(6+15\cdot\left(1+\frac{1}{3}+\frac{1}{5}+\frac{1}{15}\left)\right)$ делится на 15, хотя и подходит под условия вашего утверждения.

[age]

Там в числителе будут факториалы, сумма которых даст $2^n$. Не знаю, в общем, надо еще думать. Интересная задача.

[RIP]

maxal в сообщении #291424 писал(а):

Найдите все нечётные натуральные числа $n$, которые делят число $2^{n-1}+1$.

Пусть $n>1$ и $2^\alpha||n-1$. Пусть $p|n$, $d=\operatorname{ord}_p2$. Тогда $d|(p-1,2(n-1)$, но $d\nmid n-1$. Пусть $2^\beta||d$. Тогда $\beta>\alpha$, поскольку иначе нечётное число $2^{-\beta}d$ делило бы чётное число $2^{1-\beta}(n-1)$, поэтому выполнялось бы $2^{-\beta}d|2^{-\beta}(n-1)$, т.е. $d|n-1$, что противоречит второму условию. Таким образом, что все простые делители числа $n$ сравнимы с 1 по модулю $2^{\alpha+1}$, поэтому и $n\equiv1\pmod{2^{\alpha+1}}$, что противоречит оперделению $\alpha$.
Собственно, двойку в условии можно заменить на любое целое число $a$. Доказательство проходит дословно с единственной заменой $d=\operatorname{ord}_pa$.

[maxal]

RIP
Ага, всё верно. Кстати, если искать $n$, которые делят $2(2^{n-1} + 1)=2^n + 2$, то таких уже очень много: A006517