НОД(2^n+1,n!-1)=1 или 2n+1, третьего не дано

[maxal]

Пусть $n$ - натуральное число.
Доказать, что $\gcd(2^n+1,n!-1)$ равен либо $1$, либо $2n+1$, третьего не дано.

[Руст]

Можно сказать точнее, если p=2n+1 простое и сивол Лежандра (2/p)=-1 (т.е. n=1(mod 4) или n=2(mod 4)), то общий делитель p, в противном случае 1.

[maxal]

Руст
Не всегда. Надо наложить еще кое-какие условия.

[Руст]

Да, упустил, что n!-1 не всегда делится на p, для этого n должен быть нечётным, что обеспечивает n!=+-1(mod p). Получается, что число n=1(mod 4) и 2n+1 простое. При этом как исключить ситуацию n!=-1 не знаю как выразить.

[maxal]

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

Получается, что число n=1(mod 4) и 2n+1 простое. При этом ситуация n!=-1 исключается из-за того, что простое число p=3(mod 4).

Этого тоже недостаточно. Пример для n=5: число 5!-1 не делится на 11.

[Руст]

Именно этим примером понял, что не просто исключить случай n!=-1(mod p) и успел исправить первоначальное. Принцип доказательства не так сложен, сразу видно, что если простое число входит в gcd, то p>n, и если T период 2 -ки по модулю р, то 2n/T нечётное число.

[Руст]

Я эту задачу увидел ещё в Mathlinks под видом не решённой и проверенной до n=45000. maxal это действительно не решённая задача? Мне вроде ясно как решить, только не хочется расписывать подробности из-за громоздкости.

[maxal]

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

Я эту задачу увидел ещё в Mathlinks под видом не решённой и проверенной до n=45000. maxal это действительно не решённая задача? Мне вроде ясно как решить, только не хочется расписывать подробности из-за громоздкости.

Это я проверил до 45000, но на MathLinks я эту задачу не помещал. Видимо, кто-то из SeqFan запостил. Быстро слухи распространяются. ;)
А задача да, нерешенная.

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

Да, точно. Вот топик на MathLinks: https://artofproblemsolving.com/community/h119639 (updated)

[Руст]

Сейчас немного в запарке. Попробую привести решение на следующей неделе.

[maxal]

Рустем, что там с решением?

[Руст]

maxal писал(а):

Рустем, что там с решением?

Для полного решения времени нет. Постараюсь дать соображения, которые могут привести к доказательству. Ясно, что период 2 по модулю простого делителя р gcd чётное, обозначим его 2d. Тогда p=2kd+1, n=md, m - нечётное число. Надо показать, что возможно, только k=m=1. Введём произведения

$$x(a,i)=\prod_{0<ax+i<p}(ax+i), \ y(a,j)=\prod_{\frac{jp}{a}<y<\frac{(j+1)p}{a}}y, \ i,j=0,1,...a-1.$$

Нас интересует только их значения по модулю p и имеется естественная связь между ними $x(a,i)=a^my(a,j), \ i=-jp(mod \ a).$ Когда а является делителем p-1 (только этот случай нас интересует) m не зависит от j и равен [p/a], т.е. между x(a,i) и y(a,j) взаимно однозначное соответствие с точностью до единого мультипликатора. Удобнее работать с x(a,i) и показать, что x(a,i) являются корнями уравнения $x^a+1=0$ и никакое произведение номеров x(a,i) идущих по арифметической прогрессии не равно 1.
Попробуй довести эти соображения до доказательства.

[Руст]

То, что писал, неверно. Сделав ещё раз попытку доказать, пришёл к мнению, что это скорее всего не верно. В случае $p=3\mod 8 \ n=\frac{p-1}{2}$ примерно в половине случаев $gcd(2^n+1,n!-1)=p$. Ситал, какие простые кроме этого случая могут делит gcd. Расчёт в течение часа до миллиона дал следующие исключения:
$p=521881, n=221799$,
$p=521881,n=300081$,
$p=774593,n=338884$.
Тем самым гипотеза опровергнута. Возможно, что имеется только конечное число исключений.

[maxal]

Правильно ли я понял, что указанный список исчерпывает все случаи с $p,n<10^6$ ?
Имеет смысл закинуть эти контрпримеры и на форум MathLink тоже (ссылка приведена выше).

[Руст]

maxal писал(а):

Правильно ли я понял, что указанный список исчерпывает все случаи с $p,n<10^6$ ?
Имеет смысл закинуть эти контрпримеры и на форум MathLink тоже (ссылка приведена выше).

Нет, исчерпывает все случаи p<10^6. Сейчас программа досчитала до $p=1380611,n=690305$.(Это не исключение просто я выдавал на печать те случаи, когда n/T целое нечётное число больше 1, где T полупериод для 2: минимальное с условием $p|2^T+1$).

[Руст]

Назовём простое число р специальным, если $n=\frac{p-1}{2}, \ p|gcd(2^n+1,n!-1)$ и исключительным, если существует n $n\not =\frac{p-1}{2}, \ p|gcd(2^n+1,n!-1).$
Из того, что при p=1(mod 4) выполняется $p|(\frac{p-1}{2}!)^2+1$, следует что такое число не является специальным простым числом. А простые числа вида p=7(mod 8) вообще не делят числа вида $2^n+1$, поэтому специальными простыми могут быть только простые вида p=3(mod 8), причём из $n!=1\mod p$ получается, что квадратичных вычетов среди чисел 1,2,3,...(p-1)/2 было нечётным (соответственно квадратичных невычетов чётно). Последнее условие эквивалентно так же нечётности количества нечётных квадратичных вычетов. Примерно половина простых вида p=3(mod 8) удовлетворяют этому условию и являются специальными.
Среди простых меньше 5 000 000 имеется ровно 3 исключительных:
$p=521881,n=221799, \ n=300081,$
$p=774593,n=338884,$
$p=4327489, n=3652374.$
Если кто хочет найти ещё исключительные простые (которых, как я понимаю бесконечно много) предлагаю алгоритм поиска. Будем по циклу нарасти число m и вычислим число

$$X_m=\prod_{d|m, d-odd}(2^{m/d}+1)^{\mu (d)}.$$

Во внутреннем цикле пробегаем по нечётным k и вычисляем $a_k=(km)!\mod X_m$, если $(a_k-1,X_m)>1$, то $n=km$ исключительное число для всех простых делителей $p|(a_k-1,X_m)$. При этом время от времени вычисляем $b_k=(a_k,X_m)$ и сокращаем $X_m$ на простые делители $b_k$.
Я этот алгоритм не стал реализовать, хотя по нему можно было найти указанные исключительные n гораздо быстрее.