Ó Какоткин Роман Викторович. 29 ноября 2004 года.

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

Часть 1.

            Многим известна теорема «о единственности представления натурального числа в виде произведения простых сомножителей». Из самой формулировки вышеуказанной теоремы вытекает несколько следствий, открывающих для нас алгоритм распределения простых множителей при факторизации чисел натурального ряда, из которого следует:

            Алгоритм распределения простых чисел в натуральном ряду является обратно-матричным, т. е. множество простых чисел является остатком от исключения множества нечетных составных чисел (матрицы) из множества нечетных чисел.

            Произведение простых сомножителей является своеобразным «генетическим кодом» натуральных и рациональных чисел, позволяет определить все целочисленные делители и выделить из них общие делители для различных чисел и их групп.

            Множество целочисленных делителей числа, есть множество результатов перемножения простых сомножителей, входящих в результат факторизации числа.

 

            Пример: для n = 154, factory(n)=2*7*11

 (2, 7, 11, 2*7=14, 2*11=22, 7*11=77.) – множество целочисленных делителей числа – n.

 

            Но, будем последовательны и начнем логическую цепь рассуждений с вышеупомянутой теоремы, приводить текст доказательства которой  нет необходимости. Нам необходима не сама теорема, а вытекающие из нее следствия. А именно:

 

Следствие № 1. Любое четное, натуральное число , не имеющее нечетного делителя, имеет в результате факторизации (далее – factory(a)) в качестве простого сомножителя:

 

 , .

 

( factory – результат факторизации, произведение простых сомножителей вида )

 

Следствие № 2. Любое четное, натуральное число  имеет в factory(a) произведение:

 

, где  - наибольший нечетный делитель числа .

Пример: , , , .

 

Следствие № 3. Поскольку для каждого натурального числа  ,  и - являются делителями  , каждое натуральное число кратное простомубудет иметь в результате факторизации простой множитель , (т. е. каждое третье число будет иметь в качестве простого сомножителя тройку, каждое пятое – пятерку, каждое сорок девятое – семерку в квадрате, и т. д.).

 

Исходя из изложенного, мы можем разделить (по алгоритму факторизации) множество натуральных чисел - (N) на пять подмножеств, из которых (A), (B) – входят в множество четных чисел, а (K), (F), (P) – в множество нечетных чисел:

 

1.      Множество (A) – множество четных чисел вида .

 

2.      Множество (B) – множество четных чисел вида .

 

3.      Множество (K) – множество нечетных чисел вида .

 

4.      Множество (F) – множество нечетных чисел вида .

 

5.      Множество (P) – множество простых чисел.

 

АЛГОРИТМ ФАКТОРИЗАЦИИ:

 

 Для того чтобы факторизовать ряд натуральных чисел до, выполним следующее:

 

·        Каждое число натурального ряда (N) до представим в виде:

 

 

, где по умолчанию каждое, .

 

·        Каждому четному числу присвоим значение .

 

 

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

 

·        Каждому числу кратному - добавим значение в результат факторизации.

 

 

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

 

ФАКТОРИЗАЦИЯ ВЫПОЛНЕНА.

 

            ПРИМЕЧАНИЕ: Все числа, имеющие в результате факторизации один простой сомножитель с показателем степени равным единице - будут простыми. Для того чтобы начать факторизацию нам не нужно знать ни одного простого числа. Ряд простых чисел начнется с двойки и известных простых будет всегда достаточно для того, чтобы определить следующее простое.

·        Двойки достаточно для того, чтобы факторизовать следующее составное число (двойку в квадрате), но в результате станет известно следующее простое – тройка.

·        Произведение двойки и тройки факторизуют шестерку, определив простое – пятерку.

·        Куб двойки факторизует восьмерку и выявит простое – семерку.

·        Куб тройки факторизует девятку. И т. д. ...

 

Приведенный выше алгоритм факторизации натурального ряда чисел напоминает алгоритм определения ряда простых чисел, предложенный Эратосфеном (известный как «решето Эратосфена») и отличается от последнего тем, что кроме определения ряда простых чисел позволяет факторизовать весь ряд составных чисел.

 

В качестве примера привожу таблицу нечетных чисел (четные числа исключены для краткости изложения), факторизованных с помощью вышеописанного алгоритма:

 

ТАБЛИЦА № 1.

 

 

            Большинство теорем из  теории чисел прямо вытекают из «основной теоремы математики» - единственности представления натурального числа в виде произведения простых сомножителей. Но об этом речь пойдет во второй части…

(продолжение следует)