Простое число и его определение.

[Iosif1]

Я поблагодарил nnosipov за совет, но не потому, что посчитал его совет мудрым.
Думал, что это понятно.
До такого я и сам мог додуматься, если бы имел возможность осуществить задуманное.
Мне и так удалось кое-чему научиться для того, чтобы общаться на форумах.
Кто-то скажет: «Невелика премудрость»!
- Кому как.
Причины могут быть разные. Не стоит их перечислять.
Я понимаю, что один математик знает то, что он знает, и не всегда то, что знает другой математик.
Да и не всегда хочет это знать.
Но если это из его, так сказать, интересов, то это, по моему мнению, нонсенс.
Вроде есть на форуме математики, интересующиеся простыми числами, и факторизацией, и криптографией …
Неужели среди них нет такого, у которого есть интерес к тому, что уже стало известно мне, но ещё не известно ему?
Разработанная методика позволяет определять простоту числа, на основании его факторизации посредством конечного количества расчётов, не зависящих от величины числа.
Признаюсь, что у меня были надежды на интерес математической общественности к методике уже давно.
Теперь остаётся надежда, хоть кого-то заинтересовать.
Замечу, что имею возможность давать информацию только файлами (о причине уже упоминал).
Понимание методики достигалось благодаря Skype и файлам.

[Deggial]

Тема изначально не содержала ни одного содержательного и внятно сформулированного утверждения, а теперь ожидать что-то стало совершенно бесперспективно.

Iosif1 в сообщении #909890 писал(а):

Разработанная методика позволяет определять простоту числа, на основании его факторизации посредством конечного количества расчётов, не зависящих от величины числа.

На это весёлой ноте тема переезжает из форума «Дискуссионные темы (М)» в форум «Пургаторий (М)»

[Someone]

Собственно, тема весьма давняя и пургаторная в том смысле, что заявления автора ни на чём не основаны. Возможно, были эксперименты с небольшими числами, которые разлагаются на множители за доли секунды методом пробного деления, но такие числа в настоящее время никого не интересуют, а интересуют числа, содержащие сотни цифр в десятичной записи, не говоря уже о поиске рекордных простых чисел, содержащих миллионы цифр.
Однако утверждения о необыкновенной эффективности этого метода вновь всплыли. Поэтому желательно дать некоторые пояснения.
Сам по себе предлагаемый метод не является новым. Я о нём узнал, ещё будучи младшим школьником (в 1961 году, когда учился в 4-м классе), когда купил в книжном магазине книгу Б. А. Кордемского "Математическая смекалка" (Государственное издательство технико-теоретической литературы, Москва, 1957). Там этот метод называется решетом Сундарама и оформлен в виде двумерной таблицы, строки и столбцы которой являются арифметическими прогрессиями:

\begin{tabular}{rrrrrrr} 4&7&10&13&16&19&\cdots\\ 7&12&17&22&27&32&\cdots\\ 10&17&24&31&38&45&\cdots\\ 13&22&31&40&49&58&\cdots\\ 16&27&38&49&60&71&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{tabular}

Число, расположенное на пересечении строки № $x$ и столбца № $y$, равно $2xy+x+y$.

Работает это так. Пусть задано нечётное натуральное число $N=2n+1$. Если число $n$ имеется в таблице, то $N$ — составное, если же числа $n$ в таблице нет, то $N$ — простое.
Обоснование очень простое.
Если $N$ — нечётное составное, то есть, существуют такие (нечётные) натуральные $p>1$ и $q>1$, что $N=pq$, то числа $n=\frac{N-1}2$, $x=\frac{p-1}2$ и $y=\frac{q-1}2$ являются натуральными; тогда выполняется равенство $2n+1=(2x+1)(2y+1)$, то есть, $n=2xy+x+y$. Следовательно, число $n$ имеется в таблице и расположено на пересечении строки № $x$ и столбца № $y$.
Наоборот, если число $n$ есть в таблице и расположено на пересечении строки № $x$ и столбца № $y$, то $N=2n+1=4xy+2x+2y+1=(2x+1)(2y+1)$ и, следовательно, составное.

Совершенно очевидно, что проверка числа на простоту таким методом равносильна частичному разложению на множители и потому не может быть более эффективной, чем поиск делителя. Известно, что поиск делителя — существенно более сложная задача, чем проверка на простоту.

В данной теме предлагается обобщение решета Сундарама:

Iosif1 в сообщении #884409 писал(а):

Для упрощения выражений можно выражать уравнения в виде не чисел, а их номеров, которые определяются как целочисленные частные от деления чисел на выбранные модули, с прибавлением к числам, или вычетом от чисел единицы.
Поэтому каждый номер любого составного числа, не содержащего сомножителей $2$ и $3$ можно выразить вариантами:

$N_6=6x_6y_6±x_6±y_6$ ; (1)

$N_4=4x_4y_4±x_4±y_4$ ; (2)

Становится ясно, что если составное число можно, то простое число не может быть так обеспечено одновременно,ибо в таком случае оно становится составным.

Собственно, предлагается для числа $N$, не делящегося ни на $2$, ни на $3$, искать решения четырёх уравнений $4xy\pm x\pm y=N_4$ и четырёх уравнений $6xy\pm x\pm y=N_6$, где $N_4=\frac{N\pm 1}4$ и $N_6=\frac{N\pm 1}6$ (в обоих случаях знак выбирается так, чтобы частное было целым). Непонятно, конечно, зачем так много уравнений. Достаточно найти решение одного из восьми предлагаемых уравнений, чтобы получить разложение числа на два множителя; для доказательства простоты нужно доказать отсутствие решений у одного или двух правильно выбранных уравнений из четырёх первых или из четырёх вторых. Так же, как и для решета Сундарама, задача равносильна поиску делителя и, следовательно, сложнее проверки на простоту.

Правила выбора уравнений.
1) $4xy\pm x\pm y=n$
Если $N=4n+1$, то $N$ разлагается либо в произведение $(4x+1)(4y+1)$, либо в произведение $(4x-1)(4y-1)$. Соответственно, нужно искать решения двух уравнений $4xy+x+y=n$ и $4xy-x-y=n$.
Если $N=4n-1$, то $N$ разлагается в произведение $(4x+1)(4y-1)$, поэтому достаточно искать решения одного уравнения $4xy-x+y=n$ (второе уравнение $4xy+x-y=n$ отличается только обозначениями неизвестных).
Этот вариант решета работает и для чисел, делящихся на $3$. Правдоподобно, что он равносилен решету Сундарама.
2) $6xy\pm x\pm y=n$
Если $N=6n+1$, то $N$ разлагается либо в произведение $(6x+1)(6y+1)$, либо в произведение $(6x-1)(6y-1)$. Соответственно, нужно искать решения двух уравнений $6xy+x+y=n$ и $6xy-x-y=n$.
Если $N=6n-1$, то $N$ разлагается в произведение $(6x+1)(6y-1)$, поэтому достаточно искать решения одного уравнения $6xy-x+y=n$ (второе уравнение $6xy+x-y=n$ отличается только обозначениями неизвестных).

Очевидный метод поиска решений предлагаемых уравнений состоит в том, чтобы выразить одну неизвестную и подставлять вместо другой последовательные натуральные числа $1$, $2$, $3$,… Например, для уравнения $6xy+x+y=n$ выражаем $y=\frac{n-x}{6x+1}$ и подставляем вместо $x$ последовательные натуральные числа, начиная с единицы. Останавливаемся, когда получится целое частное, либо частное станет меньше $x$ (для других уравнений условие остановки может быть другим; предлагаемая процедура наверняка не самая эффективная для данных уравнений).

В итоге, я не могу ожидать высокой эффективности обсуждаемого метода по сравнению с другими методами проверки простоты числа, и пока не вижу здесь более эффективного метода поиска делителя, чем "тривиальный" метод пробного деления. НоIosif1, разумеется, убеждён, что его метод суперэффективный.