на два множителя почти одинаковой величины, так как тогда у мало. Если N простое, процесс будет продолжаться до тех пор, пока мы не дойдем до решения

X + у = N, X - у = 1. В качестве примера возьмем N = 9271. Оно лежит между 96 и 97, так что т = 97. Первым числом в ряду (7) будет число

97 - 9271 = 138. Следуюш;ие получаются добавлением последовательно 2т + 1, 2т + 3 и так далее, т. е. 195, 197 и так далее. Это дает ряд чисел

138, 333, 530, 729, 930, ... Четвертое из них - точный квадрат (оно равно 27), и мы получаем

9271 = 100 - 27 = 127 • 73. Интересный алгоритм разложения был открыт капитаном военно-морских сил США Дрэмом (N. А. Draim). В этом алгоритме результат каждого шага деления используется для того, чтобы подготовить число к следуюгцему делению. Имеются различные формы этого алгоритма, простейшей, вероятно, является форма, в которой последовательными делителями служат нечетные числа 3, 5, 7, 9, ..., простые или составные. Поясним действие этого алгоритма на численном примере; возьмем, скажем, N = 4511. Первый шаг - деление на 3, частное 1503, остаток 2:

4511 = 3-1503 + 2. Следуюгций шаг - вычитание удвоенного частного из данного числа и добавление остатка:

4511 - 2 . 1503 = 1505; 1505 + 2 = 1507. Последнее число надо разделить на следуюгцее нечетное число 5:

1507 = 5-301 + 2. Следуюш;ий шаг - вычитание удвоенного частного из первого, получившегося на предыдуш;ем шагу числа (из 1505 в данном случае) и добавление к нему последнего остатка:

1505 - 2 - 301 = 903; 903 + 2 = 905. Это число надо разделить на следуюш;ее нечетное число 7. Да-

лее мы действуем таким же образом: 905 = 7 • 129 + 2;

903 - 2 . 129 = 645; 645 + 2 = 647; 647 = 9 • 71 + 8;

645 - 2-71 = 503; 503 + 8 = 511; 511 = 11-46 + 5;

503 - 2-46 = 411; 411 + 5 = 416;

416 = 13-32 + 0. Мы получили нулевой остаток, и алгоритм говорит нам, что 13 является делителем данного числа 4511. Второй сомножитель находится в результате первой половины следующего шага:

411 - 2-32 = 347.

Действительно,

4511 = 13-347, так как 347 - простое число, разложение закончено.

Обосновать действие алгоритма в общем случае - задача элементарной алгебры. Пусть Ni - данное число; первый шаг состоял в том, чтобы представить Ni в виде

Nl = 3qi+ri. На следующем шагу мы строим числа

М2 = Nl - 2qi и N2 = М2 + гь Затем делим число TV2 на 5:

N2 = 5q2 + г2. на третьем шагу мы строим числа

Мз = М2 - 22 и ТУз = Мз + г2.

и так далее. Из написанных уравнений следует, что

N2=2Ni-5qu

TV3 = 3TVi - 7qi - 72,

Щ = 4TVi - 91 - 92 - 93

и так далее. Значит, N2 делится на 5 тогда и только тогда, когда 2Ni делится на 5, или Ni делится на 5. Лз делится на 7 тогда и только тогда, когда 3Ni делится на 7, или Ni делится на 7, и так далее. Когда мы дойдем до наименьшего простого делителя Nl будет иметь место точная делимость и нулевой остаток.

Общее уравнение, аналогичное приведенным выше, имеет вид

Nn = nNi - (2n + l)(5i + 52 + • • • + Qn-i); (8)

общее уравнение для имеет вид

Mn = Ni- 2{qi + 52 + • • • + ?n-i). (9)

Если 2n + 1 - делитель данного числа TVi, то Nn делится на 2п + 1, так что

Nn = {2n + l)qn,

откуда nNi = (2п + l)(5i + ?2 + * * * + в силу (8). Далее, в силу (9) мы имеем

\2n + lJ 2п+1 Таким образом, множителем, дополнительным к 2п + 1, является что и получилось в численном примере.

В рассмотренном численном примере TVi, N2, ... убывают монотонно. В общем случае это свойство имеет место лишь в начале алгоритма и может не выполняться в дальнейшем. Тем не менее оказывается, что последующие числа всегда много меньше, чем исходное число.

10. Простые числа. Понятие простого числа очень естественно, однако вопросы, связанные с простыми, часто весьма трудны, и на многие из этих вопросов современная математика не в состоянии дать удовлетворительный ответ. Мы заканчиваем эту главу кратким перечислением некоторых результатов и гипотез, связанных с простыми числами.

В п. 3 мы привели евклидово доказательство бесконечности числа простых. То же рассуждение применимо для доказательства бесконечности числа простых некоторого специального вида. Так как каждое простое число, большее 2, нечетно, то любое простое принадлежит одной из двух арифметических прогрессий

(a) 1, 5, 9, 13, 17, 21, 25,

(b) 3, 7, 11, 15, 19, 23, 27,

прогрессия (а) состоит из всех чисел вида 4j; + 1, а прогрессия (Ь) - из всех чисел вида 4; - 1 (или 4j; + 3, что то же самое). Докажем сначала, что в прогрессии (Ь) имеется бесконечно много