Задачи о разложении чисел на простые сомножители

[temp03]

1. Доказать, что в ряду $p_n=2^n-1, n=1..1000$ $p_n$ содержат все простые множители от $1$ до $1000$.
2. Доказать, что $2^n+1$ не делится на $7, 31, 71$ ни для каких $n$.

[Руст]

Задачи очевидные. Только в первом не точность - простое 2 не входит в виде сомножителя ни для одного $p_n$.
2. Очевидно, чтобы $p \not |2^n+1$ необходимо [math]$(\frac 2p )=1$ для чисел $p=-1\ьщв 8$ этого и достаточно.
Интересно, существуют ли простые вида $p=1\mod 8$ не делящие числа вида $2^n+1$, я не проверял.

[maxal]

Руст в сообщении #233952 писал(а):

Интересно, существуют ли простые вида $p=1\mod 8$ не делящие числа вида $2^n+1$, я не проверял.

Существуют и много:
73, 89, 233, 337, 601, 881, 937, 1289, 1433, 1609, 1721, 1801, 1913, ...

[Руст]

По всей видимости примерно каждое четвертое (по вероятности каждое шестое) простое вида $p=1\mod 8$ имеет нечётный порядок для числа 2.

[temp03]

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

[Коровьев]

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

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

Сказанул, так сказанул?! Посложнее. Контропример нашли, когда появились ЭВМ (не путать с компьюттерами. те ЭВМ к нашим компьютерам, как конторские счёты к тем ЭВМ )
$(2^{1092}-1)$ делится на $1093^2$
Среди простых меньше $p<200183$ есть только ещё одно простое $p=3511$ с этим свойством.
/Сошлюсь на "Боревич,Шаферевич. Теория чисел". стр.298./

[temp03]

Коровьев
Да. Круто. Значит, все-таки есть.
Но кажется я все-таки ошибся. Чтобы $(x^n+2y^n)\div n^2$ достаточно $(2^{n-1}-1)\div n^2$. Но не необходимо.

[Droog_Andrey]

http://mathworld.wolfram.com/WieferichPrime.html

[temp03]

Мне удалось частично факторизовать число $2^{1092}-1$. Оно выглядит так:
$2^{1092}-1=3^2\cdot7\cdot13^2\cdot29\cdot43\cdot53\cdot79\cdot113\cdot127\cdot157\cdot313\cdot911\cdot1093^2\cdot1249\cdot1613\cdot2731\cdot3121\cdot4733\cdot8191\cdot25829691707\cdot23140471537\cdot1210483\cdot112901153\cdot224771\cdot556338525912325157\cdot8861085190774909\cdot22366891\cdot121369\cdot21841\cdot...$

Я бы факторизовал его полностью, но Mathcad такие числа не берет.

[maxal]

Многие числа вида $b^n \pm 1$ для маленьких $b$ уже факторизованы в рамках проекта Cunningham. $2^{1092}-1$ в их числе. Полностью факторизация выглядит так:

[3, 2; 5, 1; 7, 2; 13, 2; 29, 1; 43, 1; 53, 1; 79, 1; 113, 1; 127, 1; 157, 1; 313, 1; 337, 1; 547, 1; 911, 1; 1093, 2; 1249, 1; 1429, 1; 1613, 1; 2731, 1; 3121, 1; 4733, 1; 5419, 1; 8191, 1; 14449, 1; 21841, 1; 121369, 1; 224771, 1; 503413, 1; 1210483, 1; 1948129, 1; 22366891, 1; 108749551, 1; 112901153, 1; 23140471537, 1; 25829691707, 1; 105310750819, 1; 467811806281, 1; 4093204977277417, 1; 8861085190774909, 1; 556338525912325157, 1; 86977595801949844993, 1; 275700717951546566946854497, 1; 292653113147157205779127526827, 1; 3194753987813988499397428643895659569, 1]