Тест для чисел Ферма

[Батороев]

Dmitriy40
Я так и написал, что тест - вероятностный, т.е. отсеивает составные ЧФ за исключением редких псевдопростых (например, $F_{16}$).

[dgwuqtj]

Батороев
Как это он вероятностный, если нигде не используются случайные события? Всё детерминировано. Вероятностные тесты работают примерно так: выберем случайное число или строку $x$, а дальше что-то посчитаем.

[nnosipov]

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

псевдопростых (например, $F_{16}$)

Кстати, да, число $F_{16}$ является псевдопростым (и даже строго псевдопростым) по основанию $2$. Но не является таковым по основанию $3$ (и, как следствие, оно составное).

[Батороев]

dgwuqtj
Я в математике человек темный и математических книг стараюсь не читать, а разбираться самостоятельно (такое у меня хобби). Поэтому слов, которым математики придали свой определенный математический смысл не особо знаю. А применил я слово "вероятностный" в бытовом значении - в смыле "число - вероятно простое". Вы уж простите дедушку!

-- 02 сен 2024 19:45 --

nnosipov в сообщении #1652791 писал(а):

Кстати, да, число $F_{16}$ является псевдопростым (и даже строго псевдопростым) по основанию $2$. Но не является таковым по основанию $3$ (и, как следствие, оно составное).

После того, как Вы сообщили, что данное число составное, я предположил, что оно такое, как Вы пишете, но проверить не мог. Excel, на котором я считаю, даже на числе $F_{6}$ дает ошибки. Спасибо!

[vicvolf]

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

Число Ферма $F_n$ является делителем числа $(F_{n+1}-2)$. Других зависмостей я не наблюдал.

Независимо от того является ли число $F_n$ простым или нет оно является делителем числа $F_{n+1}-2$, т.е. независимо от того является ли число $F_n$ простым или нет число $F_{n+1}-2$ является составным. Поэтому независимо от того является ли число $F_n$ простым или нет, число $F_{n+1}$ может быть простым или нет.

[Батороев]

vicvolf
Как Вы спросили, так я и ответил - про конкретное простое число $F_{n}$ и число $F_{n+1}$. Спросили бы про произвольные числа Ферма, я бы написал, что $(F_{n+1}-2)$ является произведением всех предыдущих ЧФ.

[Батороев]

Dmitriy40 в сообщении #1652665 писал(а):

Не работает тест.

Dmitriy40 в сообщении #1652675 писал(а):

Батороев
Вы предложили - Вам и доказывать корректность. Хоть в своей непонятной формулировке, хоть в нормальной.

В пилотном сообщении я написал, что "тест гипотетический", т.е. не утверждал, что тест точный.
Как впоследствии справедливо отметил уважаемый nnosipov, он пропускает составные ЧФ, псевдопростые по основанию $2$. Но и в таком виде, на мой непросвещенный взгляд, тест должен представлять определенный интерес. Поэтому попытаюсь показать корректность теста, правда, "в своей непонятной формулировке".
Итак, имеем тест:

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

Правильно так:

$$(2^{n}-1) = n+(n+1)+m\cdot (n+2) \eqno (1)$$

(Оффтоп)

nnosipov в сообщении #1652661 писал(а):

Вот я просил ТС по-человечески написать условие... Вот оно: $2^n-2n-2 \equiv 0 \pmod{n+2}$. Не нужно никакого $m$.

Моя «нечеловеческая» запись – это попытка раскрыть суть теста наиболее наглядно.

Имеем число Ферма $F_{n}$.
Назовем «ступенью» переход от любой степени к её удвоенной.
Составляем таблицу остатков чисел от $1$ до $(F_{n}-1)$ по основанию данного ЧФ.
Количество ступеней в такой таблице $2^{n}$, но с учетом индексов чисел Ферма, применяемых в математике (2), крайнюю справа степень обозначаем через $(2^{n}-1)$. Отсюда получаем левую часть уравнения (1).

Первые $(n+1)$ ступеней занимают степени двойки от $2$ до $(-1)\pmod {F_{n}}$. С учетом (2) таких ступеней $n$. Это и есть первое слагаемое в правой части уравнения (1).

Почти во всех столбцах (ступенях) таблицы имеем остатки, равные $2\pmod {F_{n}}$.
Последний столбец, в котором имеется такой остаток - это ступень $(2^n-n-1)$ (3). При этом двойка, затем пробежав $(n+1)$ ступеней, в степени $(2^{n}-1)$ получает остаток $(-1)\pmod {F_{n}}$ (4). Отсюда имеем второе слагаемое в правой части уравнения (1).

В ставшихся незадействованными ступенях таблицы должно уложиться целое число полных циклов степеней $2$-ки (5).
Полным циклом я называю число остатков степеней двойки по ступеням: $(2;4;16;... (-1);1) \pmod {F_{n}}$. Полный цикл занимает $(n+2)$ ступеней. Отсюда получаем третье слагаемое в правой части уравнения (1).
Целочисленность циклов (5) определяет правомерность применения условий (3) и (4).

[Батороев]

nnosipov в сообщении #1652661 писал(а):

Вот оно: $2^n-2n-2 \equiv 0 \pmod{n+2}$. Не нужно никакого $m$.

Можно еще и так: $2^n+2\equiv {0}\pmod {n+2}$.

[Dmitriy40]

А ещё можно так: $2^n \equiv n \pmod{n+2}$. И много как ещё.

[Батороев]

Dmitriy40 в сообщении #1654822 писал(а):

А ещё можно так: $2^n \equiv n \pmod{n+2}$. И много как ещё.

Согласен, что можно по-разному.

Но в моем варианте:

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

Можно еще и так: $2^n+2\equiv {0}\pmod {n+2}$.

показывается, что для простого числа Ферма (больше $17$) в число ступеней двойки: $2^0;2^1;2^2;2^4... 2^{2^{F_{n}-1}}$, а это число равно $2^n+2$, должно нацело уложиться число полных циклов степеней $2$-ки.

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

Полным циклом я называю число остатков степеней двойки по ступеням: $(2;4;16;... (-1);1) \pmod {F_{n}}$. Полный цикл занимает $(n+2)$ ступеней.

[Батороев]

Для большей ясности приведу пример для $F_{4}=65537$:
Число ступеней двойки $2^0;2^1;2^2;2^4;2^{16};2^32;.. 2^{65536}$ - всего $18$ ступеней.
1. Сначала рассматриваем степени числа $2$:
$1,2,4,16,256,65536$ - итого $6$ ступеней (т.е. получаем полный цикл степеней двойки, но в данном случае единичка находится спереди).
2. Находим остаток $2\pmod {F_{4}}$ в седьмой ступени, например, у числа $5851$, которое в свою очередь затем пробегает полный цикл степеней двойки: $2;4;16;256;65536;1$ ($6$ ступеней).
3. Следующий остаток $2\pmod {F_{4}}$ находим в $13$-ой ступени (это последняя ступень, в которой есть такой остаток), например, у числа $23$, которое затем также пробегает полный цикл степеней двойки: $2;4;16;256;65536;1$ (6 ступеней).
В итоге получаем остаток $1\pmod {F_{4}}$ в $18$-ой ступени, как и определено Малой теоремой Ферма.

[Dmitriy40]

Я один за объяснением происхождения простой формулы так и не увидел доказательства высказанного утверждения?

[nnosipov]

Dmitriy40
Здесь понять бы, о каком вообще утверждении идет речь. Первоначальное утверждение ТС оказалось неверным (был приведен контрпример), а нового утверждения я так и не усмотрел.

[Батороев]

Dmitriy40 в сообщении #1654883 писал(а):

Я один за объяснением происхождения простой формулы так и не увидел доказательства высказанного утверждения?

Я и не претендовал на то, что докажу. Тем более в пилотном сообщении я охарактеризовал тест, как гипотетический, т.е. возможно правильный. Как оказалось тест пропускает отдельные числа Ферма, но при этом отсекает львиную долю других составных.
Мои рассуждения основывались на то, чтобы получить в последних ступенях остатки в виде полного цикла степеней двойки.
Конечно, для проверки ЧФ на простоту можно использовать МТФ и тест Пепина. Но больно числа Ферма "могучи", чтобы их "ворочить".
Тогда я решил проанализировать поведение известных простых ЧФ. И обратил внимание на то, что остатки $2\pmod {F_{n}}$ заканчиваются в ступени $2^n-(n+1)$ и далее таких остатков нет, что вполне объяснимо, т.к. двойка должна пройти полный цикл степеней и занять последние $n+2$ ступени.
Далее я решил проверить, как должны соотноситься между собой другие полные циклы степеней двойки, встречающиеся внутри таблицы степеней? И пришел к выводу, что этих циклы должны целочисленно укладываться в число $2^{n}+2$ всех ступеней таблицы. И лишь в этом случае можно получить многообразие свидетелей простоты, у которых в последних $n+2$ ступенях будет полный цикл степеней двойки.
Например, для числа $F_{4} = 65537$ такие свидетели простоты (см. пример): $23; (2\cdot 23); (5851\cdot 23);(2\cdot 5851\cdot 23)...$. И это только для одного из $32$ чисел по п.2 и одного из $2048$ чисел по п.3.

[Dmitriy40]

nnosipov
Я так понял после контрпримера утверждение просто смягчилось с "отсеивает все" до "отсеивает почти все" (составные).
Вот только обоснования я так и не понял, математического (а не этой повторённой кучи слов), даже есть ли оно. Насколько вообще отличается вероятность для произвольного $n$ оказаться отсеянным (число Ферма составное) от 50%? Т.е. насколько данному тесту вообще можно верить? Вы поняли? Тесты этого не показывают, слишком по малому чисел Ферма известен вердикт.