n|2^n+1

[Руст]

1. Докажите, что если $n|(2^n+1)$, то или n=1 или n=3 или 9|n.
2. Докажите, что для любого натурального числа k, существует бесквадратное число m, имеющее ровно k (естественно различных) простых делителей, такое, что для n=3m выполняется $n|(2^n+1).$

[maxal]

Очень похоже на http://www.nsu.ru/phorum/read.php?f=29&i=5449&t=5449

Назовем хорошими такие $n$, что $n|(2^n+1)$, а их простые делители назовем особыми.

Заметим, что
1) Числа $n=1$ и $n=3$ хорошие, а $p=3$ особое.
2) Если особое простое $p$ делит хорошее число $n$, то число $ord_p(2)$ является четным, и $ord_p(2)/2$ также делит $n$ (здесь $ord_p(2)$ - мультипликативный порядок числа $2$ по модулю $p$).
3) Если число $p$ особое, то $ord_p(2)/2$ явлется произведением особых чисел. И, наоборот, если $ord_p(2)/2$ является произведением особых простых, то $p$ - также особое.

Так как $ord_p(2) < p$, то все особые числа можно последовательно, начиная с p=3, и проверяя для каждого следующего простого, является ли $ord_p(2)/2$ произведением особых простых. Вот несколько первых особых простых чисел:

$$3, 19, 163, 571, 1459, 8803, 9137, \dots$$

Теперь пусть $p$ - особое простое делящее некоторое хорошее число $n$. Тогда $ord_p(2)$ делит $2n$, что накладывает ограничения снизу на показатели меньших простых чисел в разложении $n$, каждое из этих простых тоже накладывает свои ограничения и т.д.
Получается, что для каждого особого $p$ существует некоторое число $m(p)$, такое что если $n$ делится на $m(p)$ и в разложении $n$ нет других простых кроме тех, что входят в разложение $m(p)$, то $n$ - хорошее.
Например, для $p=9137$ получаем $ord_{9137}(2)=2\cdot 571$, $ord_{571}(2)=2\cdot 3\cdot 19,$ $ord_{19}(2)=2\cdot 3^2,$ $ord_{3}(2)=2$ и поэтому $m(9137)=3^2\cdot 19\cdot 571\cdot 9137$.

По индукции несложно получить, что для любого особого $p>3$, $9|m(p)$.

Пункт 2 также доказывается по индукции. Число $m=3\cdot 19$ является искомым с 2-мя простыми делителями (заметим, что $19$ является делителем $2^9+1$). Пусть у нас есть бесквадратное $m$, являющееся произведенеие $k$ особых простых. Если $p$ - простой делитель числа $2^{3m}+1$, не делящий $m$, то число $p\cdot m$ - искомое, являющееся произведением $k+1$ простых. Существование такого $p$ легко следует, например, из теоремы Зигмунда ввиду того факта, что все простые делители $m$ являются делителями чисел $2^t+1$ с показателями $t<3m$.

[juna]

Найти все натуральные $a$ такие, что $a|2^{a+1}+1$.

[maxal]

А что у них есть какое-то простое описание?

Вот все такие a в пределах $10^7$ с факторизациями a и a+1:

? for(a=2,10^7,if(Mod(2,a)^(a+1)==-1,print(a," ",factor(a)," ",factor(a+1))))
5 Mat([5, 1]) [2, 1; 3, 1]
65 [5, 1; 13, 1] [2, 1; 3, 1; 11, 1]
377 [13, 1; 29, 1] [2, 1; 3, 3; 7, 1]
1189 [29, 1; 41, 1] [2, 1; 5, 1; 7, 1; 17, 1]
1469 [13, 1; 113, 1] [2, 1; 3, 1; 5, 1; 7, 2]
25805 [5, 1; 13, 1; 397, 1] [2, 1; 3, 1; 11, 1; 17, 1; 23, 1]
58589 [41, 1; 1429, 1] [2, 1; 3, 3; 5, 1; 7, 1; 31, 1]
134945 [5, 1; 137, 1; 197, 1] [2, 1; 3, 4; 7, 2; 17, 1]
137345 [5, 1; 13, 1; 2113, 1] [2, 1; 3, 1; 11, 1; 2081, 1]
170585 [5, 1; 109, 1; 313, 1] [2, 1; 3, 8; 13, 1]
272609 [41, 1; 61, 1; 109, 1] [2, 1; 3, 2; 5, 1; 13, 1; 233, 1]
285389 [13, 1; 29, 1; 757, 1] [2, 1; 3, 3; 5, 1; 7, 1; 151, 1]
420209 [37, 1; 41, 1; 277, 1] [2, 1; 3, 2; 5, 1; 7, 1; 23, 1; 29, 1]
538733 [13, 1; 29, 1; 1429, 1] [2, 1; 3, 1; 7, 1; 101, 1; 127, 1]
592409 [41, 1; 14449, 1] [2, 1; 3, 1; 5, 1; 7, 2; 13, 1; 31, 1]
618449 [13, 1; 113, 1; 421, 1] [2, 1; 3, 1; 5, 2; 7, 1; 19, 1; 31, 1]
680705 [5, 1; 109, 1; 1249, 1] [2, 1; 3, 2; 13, 1; 2909, 1]
778805 [5, 1; 109, 1; 1429, 1] [2, 1; 3, 2; 7, 2; 883, 1]
1163065 [5, 1; 457, 1; 509, 1] [2, 1; 19, 1; 127, 1; 241, 1]
1520441 [13, 1; 29, 1; 37, 1; 109, 1] [2, 1; 3, 2; 7, 1; 11, 1; 1097, 1]
1700945 [5, 1; 109, 1; 3121, 1] [2, 1; 3, 3; 13, 1; 2423, 1]
2099201 [13, 1; 113, 1; 1429, 1] [2, 1; 3, 1; 7, 1; 151, 1; 331, 1]
2831009 [29, 1; 41, 1; 2381, 1] [2, 1; 3, 1; 5, 1; 7, 1; 13, 1; 17, 1; 61, 1]
4020029 [13, 1; 109, 1; 2837, 1] [2, 1; 3, 4; 5, 1; 7, 1; 709, 1]
4174169 [41, 1; 61, 1; 1669, 1] [2, 1; 3, 1; 5, 1; 7, 1; 11, 1; 13, 1; 139, 1]
4516109 [13, 1; 37, 1; 41, 1; 229, 1] [2, 1; 3, 2; 5, 1; 19, 2; 139, 1]
5059889 [61, 1; 109, 1; 761, 1] [2, 1; 3, 2; 5, 1; 11, 1; 19, 1; 269, 1]
5215769 [13, 1; 421, 1; 953, 1] [2, 1; 3, 2; 5, 1; 7, 1; 17, 1; 487, 1]
5447273 [13, 1; 29, 1; 14449, 1] [2, 1; 3, 1; 7, 1; 23, 1; 5639, 1]
5903549 [41, 1; 109, 1; 1321, 1] [2, 1; 3, 3; 5, 2; 4373, 1]
6924301 [29, 1; 113, 1; 2113, 1] [2, 1; 7, 1; 11, 1; 44963, 1]
7389161 [13, 1; 269, 1; 2113, 1] [2, 1; 3, 2; 11, 1; 67, 1; 557, 1]
8679553 [1613, 1; 5381, 1] [2, 1; 13, 1; 17, 1; 73, 1; 269, 1]

P.S. Кстати, мы тут уже разбирали похожую задачу о делимости n|2^n+1.

[RIP]

Подозреваю, что если бы простое описание существовало и было известно, то задача была бы не в этом разделе.

[maxal]

Единственное простое наблюдение: простое p может делить такое a, только если мультипликативный порядок 2 по модулю p кратен 4.
В пределах первой сотни это простые:
5, 13, 17, 29, 37, 41, 53, 61, 97
Из них мы уже видели в качестве делителей 5, 13, 29, 37, 41, 61.
Предлагаю решить такие задачки:
найти a, которое делится на 17;
найти a, которое делится на 53;
найти a, которое делится на 97.

[RIP]

И еще одна: Может ли $a$ делиться на квадрат некоторого простого?

[maxal]

RIP писал(а):

И еще одна: Может ли $a$ делиться на квадрат некоторого простого?

Если $p^2$ делит $a$, то $p$ обязано быть Wieferich prime.

[juna]

Можно подсократить расчеты, если заметить, что $2^{a+1-n\cdot \varphi (a)}+1\equiv {0} \mod a$.
Задача взята с mathlinks (там она не решена, только не помню ссылку, вечером попытаюсь отыскать).

Добавлено
Кстати, по-моему, Руст приводил там $a=5\cdot109\cdot 1093^2$, где 1093 - одно, из известных чисел Wieferich prime

[maxal]

http://www.mathlinks.ro/Forum/viewtopic.php?t=102925

[Руст]

Там я доказал, что все простые делители p удовлетворяют условию: T2(p)/4 нечётное число. Здесь T2(p) точный период для степеней 2 по модулю p. В частности все простые делители =1(mod 4). На более высокую степень могут делится, только если они простые числа Вивериха.
Можно доказать, что все простые числа p, удовлетворяющие этому условию являются делителем некоторого решения a.

[maxal]

Руст писал(а):

Можно доказать, что все простые числа p, удовлетворяющие этому условию являются делителем некоторого решения a.

Можно увидеть доказательство?

[juna]

maxal писал(а):

Если $p^2$ делит $a$, то $p$ обязано быть Wieferich prime.

В Вольфраме я это утверждение нашел, а как его доказать?

[maxal]

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

maxal писал(а):

Если $p^2$ делит $a$, то $p$ обязано быть Wieferich prime.

В Вольфраме я это утверждение нашел, а как его доказать?

Какое еще утверждение в Вольфраме? Там дается определение Wieferich prime.

[juna]

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

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