Неограниченный ряд простых чисел

В теории чисел особенно важную роль играет класс всех простых чисел. Большая часть чисел может быть разложена на меньшие множители, например: , и т.п. Числа, которые таким образом не разлагаются, носят название простых.

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

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

Данное Евклидом доказательства существования бесконечного множества простых чисел представляет собой типичный образец математического рассуждения. В основе его лежит доказательство от противного, приведенное к абсурду. Эта же основная идея послужила Эйлеру и для того, чтобы дать еще второе доказательство неограниченности ряда простых чисел [1], речь о котором и пойдет далее.

Предпошлем доказательству два простых замечания. Пусть – отрезок длиной 2 м (рис. 1).

Будем двигаться по нему от до его середины , затем от до середины остающейся половины , затем от до середины остатка и т.д., приближаясь, таким образом, все время к , мы всегда будем оставаться перед .

При этом мы будем получать последовательно отрезки длиной в м, м, м, и т.д., которые в сумме будут меньше м:

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

,

если , то вторая дробь правой части положительна и, следовательно, ее вычитание уменьшает результат, значит:

.

В частности, если – простое число, то всегда выполняется , и поэтому полученное неравенство удовлетворяется, если вместо подставить значение :

(1)

Обозначим: , тогда, очевидно:

,

, и вообще

(2)

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

Согласно формуле (1) для всех простых чисел мы можем написать:

,

,

………………………………..

,

и образовать произведение всех этих сумм. Это произведение будет меньше произведения чисел, находящихся в правых частях наших неравенств:

.

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

Например,

,

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

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

.

Представим себе все простые множители, входящие в состав чисел ряда:

(3)

Пусть наибольшее из этих простых чисел будет . В таком случае числа ряда (3) будут составлены исключительно из простых множителей , причем ни одно из них не войдет в степени, большей . Действительно, если бы первое из этих чисел, 2, вошло в состав какого-либо числа из ряда (3) в степени, большей , то само это число должно было бы быть больше , т.е. выйти за пределы рассматриваемого ряда. По отношению к следующим, большим простым числам это тем более невозможно. Таким образом, все числа ряда (3) должны содержаться среди делителей числа .

Образуем теперь, см. выше, произведение не для произвольного простого числа , а для только что указанного простого числа , взяв вместо . Тогда выражение будет содержать в себе все слагаемые и, кроме того, много других. Таким образом, , а в свою очередь . Из формулы (2) , и мы получаем окончательно, что

(4)

Напомним еще раз, что – произвольное целое положительное число, а – наибольший из простых множителей, входящих в числа ряда (3). Левую часть неравенства (4) можно, разумеется, сделать сколь угодно большой, для этого нужно лишь взять достаточно большое . Но если бы существовало только некоторое определенное конечное число простых чисел, то не могло бы превзойти последнее из этих простых чисел, и тогда правая часть неравенства (4) не могла бы неограниченно возрастать, тем самым мы пришли бы к противоречию. Поэтому последовательность простых чисел не может оборваться.

Дадим еще одно доказательство неограниченности ряда простых чисел, но перед этим несколько теорем о простых числах.

Теорема 1. Каждое натуральное число имеет по меньшей мере один простой делитель.

Доказательство. Пусть – натуральное число . Это число имеет делители, большие единицы, например само . Среди делителей числа , больших единицы, существует наименьший. Обозначим его через . Если бы не было простым, то, согласно определению простых чисел, равнялось бы произведению двух натуральных чисел, больших единицы: . В этом случае было бы делителем числа , а значит, и числа , большим единицы и притом меньшим , что противоречит определению числа . Теорема 1 доказана.

Теорема 2. Каждое составное число имеет по меньшей мере один простой делитель .

Доказательство. Если есть составное число, то , где и – натуральные числа и . Предположим, например, что . Тогда , и, следовательно, . Но есть число . Поэтому, согласно теореме 1, число имеет простой делитель , который, очевидно, и, следовательно, . Но как делитель делителя числа является делителем и числа . Таким образом, число имеет простой делитель . Итак, теорема 2 доказана.

Теорема 3. Если – натуральное число , то между и содержится по меньшей мере одно простое число [3].

Доказательство. Так как , то целое число , очевидно, и, согласно теореме 1, имеет простой делитель , который , а следовательно, и . Если допустить, что , то будет одним из сомножителей произведения и, значит, будет делителем числа . Но, будучи также делителем числа , будет делителем разности этих чисел, или числа , что невозможно. Таким образом, , а так как уже выяснено, что , то имеем , и, значит, теорема 3 доказана.

Итак, для каждого натурального числа существует простое число, большее его. Отсюда следует, что простых чисел бесконечно много.

Как можно найти все простые числа, меньшие данного числа?

Способ, о котором будет идти речь, известен был уже в древности: он носит название решето Эратосфена.

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

Итак, из последовательности мы вычеркнем число 1, затем числа, большие чем 2 и делящиеся на 2, далее числа, большие чем 3 и делящиеся на 3. Чисел, делящихся на 4, вычеркивать нам уже не придется, так как они вычеркнуты как числа и делящиеся на 2. Таким образом, далее мы будем вычеркивать числа, большие чем 5 и делящиеся на 5 и т.д. При этом мы можем уже не вычеркивать ни одно из чисел . Действительно, если – составное число и , то, согласно теореме 2, число имеет простой делитель , следовательно, , и число окажется вычеркнутым как число, большее и делящееся на .

Так, например, желая получить все простые числа , вычеркнем из последовательности число 1, затем числа и делящиеся на 2, далее числа и делящиеся на 3, затем числа и делящиеся на 5 и, наконец, числа и делящиеся на 7. Все числа, оставшиеся в нашей последовательности, будут простыми. Таким путем мы получим следующую последовательность (в которой все простые числа выделены жирным и курсивным шрифтами):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60.

Формулы, дающие простые числа

Были сделаны попытки найти элементарные арифметические формулы, которые давали бы только простые числа, хотя бы без требования, чтобы они давали все простые числа. Ферма высказал предположение (не выставляя его в качестве положительного утверждения), что все числа вида:

являются простыми. В самом деле, при мы получаем все простые числа. Но в 1732 г. Эйлер разложил на множители число , таким образом, число – уже не простое. Позднее среди этих «чисел Ферма» удалось обнаружить другие составные числа, причем ввиду непреодолимых трудностей, с которыми были связаны непосредственные пробы, в каждом случае были выработаны более глубокие теоретико-числовые методы. В настоящее время остается неизвестным даже то, дает ли формула Ферма бесконечное множество простых чисел [2].

Вот другое простое и замечательное выражение, дающее много простых чисел:

.

При есть простое число, но уже при простого числа не получается:

.

Еще одно выражение:

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

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

ЛИТЕРАТУРА

1. Радемахер Г., Теплиц О. Числа и фигуры. Опыты математического мышления. М.: Наука, 1966, 264 с.

2. Курант Р., Роббинс Г. Что такое математика? – М.: МЦНМО, 2001, 568с.

3. Серпинский В. Что мы знаем и чего не знаем о простых числах. Л., 1963, 92 с.