Приглашение в теорию чисел

Небольшое изменение метода решета позволит нам получить большую информацию. Предположим, что всякий раз, впервые подчеркивая числа, мы будем подписывать под ним простое число, с помощью которого оно отсеивается. Тогда 15 и 35 были бы записаны как

15, 35
 3   5

и т. д., как это показано на последовательности, выписанной выше. Таким образом, мы не только указали простые числа, но и для каждого составного числа привели наименьшее простое число, являющееся его делителем. Такой список чисел называется таблицей делителей. Таблица делителей является более сложной, чем таблица простых чисел. Чтобы немного упростить ее, обычно из нее исключают те составные числа, у которых простые делители малы, например, 2, 3, 5, 7. Самая большая такая таблица была вычислена на ЭВМ Д. X. Лемером и содержит все числа, вплоть до 10 000 000.

Как мы видели, решето Эратосфена может быть использовано для построения таблиц простых чисел и таблиц делителей. Однако оно может быть использовано и для теоретических исследований. Многие важные результаты в современной теории чисел были получены методом решета. Приведем результат, известный еще Евклиду:

Существует бесконечное число простых чисел.

Доказательство. Предположим, что существует только k простых чисел:

2, 3, 5…, р_k.

Тогда в решете не оказалось бы неподчёркнутых чисел, больших, чем р_k. Но это невозможно, так как произведение этих простых чисел

р = 2 • 3 • 5 • … • р_k

будет отсеиваться k раз, по разу для каждого простого числа, поэтому следующее число р + 1 не может быть подчеркнуто ни для одного из них.

Система задач 2.4.

1. Составьте таблицы простых чисел для каждой из сотен: 1—100, 101–200, … 901—1000.

2. Попытайтесь определить количество простых чисел в диапазоне 10001— 10100.

ГЛАВА 3 ДЕЛИТЕЛИ ЧИСЕЛ

§ 1. Основная теорема о разложении на множители

Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с; например,

72 = 8 • 9, 150 = 10 • 15.

При разложении числа с на множители один из них, и даже оба (а и b) могут оказаться составными. Если а — составное, то разложение на множители можно продолжить:

а = a₁ • a₂, с = a₁ • a₂ • b.

Примерами этого могут служить рассмотренные выше числа

72 = 2 • 4 • 9, 150 = 2 • 5 • 15.

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

Таким образом мы показали, что

Каждое целое число, большее 1, является простым числом или произведением простых чисел.

Последовательное разложение числа на множители может быть выполнено многими способами. При этом можно использовать таблицу делителей. Сначала найдем наименьшее простое число р₁, делящее число с, так что с = р₁с₁. Если с₁ — составное число, то по таблице делителей найдем наименьшее простое число р₂, делящее с₁, так что

c₁ = р₂ • с₂,   c = p₁ • p₂ • с₂.

Затем найдем наименьший простой делитель числа с₂ и т. д.

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

Этот результат мы можем кратко выразить следующим образом:

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

Возможно, что вы так часто слышали об этой так называемой «основной теореме арифметики» и пользовались ею, что она представляется вам очевидной, но это совсем не так. Эта теорема может быть доказана несколькими различными способами, однако ни один из них не тривиален. Здесь мы приведём доказательство, используя способ «от противного», который часто называют его латинским названием reductio ad absurdum (приведением к абсурду). Этот способ заключается в следующем: предположив ложность теоремы, которую нужно доказать, показывают, что это предположение приводит к противоречию.

Доказательство. Предположим, что наша теорема о единственности разложения на множители неверна. Тогда должны существовать числа, имеющие по крайней мере два различных разложения на простые множители. Выберем из них наименьшее и обозначим его через с₀. Для небольших чисел, скажем, меньших 10, истинность теоремы можно установить прямой проверкой. Число с₀ имеет наименьший простой множитель р₀, и мы можем записать:

c₀ = p₀ d₀.

Так как d₀ < c₀, то число d₀ единственным образом раскладывается на простые множители. Отсюда следует, что разложение числа c₀ на простые