Приглашение в теорию чисел - [5]
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Все остальные числа, кроме 1, являются составными. Мы можем сформулировать следующее утверждение:
Теорема 2.1.1. Любое целое число с> 1 является, либо простым, либо имеет простой множитель.
Доказательство. Если с не является простым, числом, то у него есть наименьший нетривиальный множитель р. Тогда р — простое число, так как если бы р — было составным, то число с имело бы ещё меньший множитель.
Теперь мы подошли к нашей первой важной задаче в теории чисел: как определить, является ли произвольное число простым или нет, и в случае, если оно составное, то как найти какой-либо его нетривиальный делитель?
Первое, что может прийти в голову, — это попытаться разделить данное число с на все числа, меньшие его. Но надо признать, что этот способ мало удовлетворителен. Согласно теореме 2.1.1 достаточно делить на все простые числа, меньшие √с. Но мы можем значительно упростить задачу, заметив, что при разложении на множители (2.1.1) оба множителя а и b не могут быть больше, чем c, так как в противном случае мы получили бы
ab > √с • √с,
что невозможно. Таким образом, чтобы узнать, имеет ли число с делитель, достаточно проверить, делится ли число с на простые числа, не превосходящие — √с.
Пример 1. Если с = 91, то √с = 9….; проверив простые числа 2, 3, 5, 7, находим, что 91 =7 13.
Пример 2. Если с =1973, то находим, что √с = 44…. Так как ни одно из простых чисел до 43 не делит с, то это число является простым.
Очевидно, что для больших чисел этот метод может быть очень трудоемким. Однако здесь, как и при многих других вычислениях в теории чисел, можно использовать современные методы. Довольно просто запрограммировать на ЭВМ деление данного числа с на все целые числа до √с и печатание тех из них, которые не имеют остатка, т. е. тех, которые делят с.
Другим очень простым методом является применение таблиц простых чисел, т. е. использование простых чисел уже найденных другими. За последние 200 лет было составлено и издано много таблиц простых чисел. Наиболее обширной из них является таблица Д. X. Лемера, содержащая все простые числа до 10 000 000. Наша таблица 1 содержит все простые числа до 1000.
Таблица 1
Простые числа среди первой тысячи чисел
Некоторые энтузиасты-вычислители уже подготовили таблицы простых чисел, превосходящих 10 000 000. Но, по-видимому, не имеет большого смысла идти на значительные затраты и усилия, чтобы опубликовать эти таблицы. Лишь в очень редких случаях математику, даже специалисту в теории чисел, приходится решать вопрос о том, является ли какое-то большое число простым. Кроме того, большие числа, о которых математик хочет узнать, являются они составными или простыми, не берутся им произвольно. Числа, которые он хочет исследовать, обычно появляются в специальных математических задачах, и, таким образом, эти числа имеют очень специфическую форму.
Система задач 2.1.
1. Какие из следующих чисел являются простыми: а) год вашего рождения; б) текущий год; в) номер вашего дома.
2. Найдите простое число, следующее за простым числом 1973.
3. Заметим, что числа от 90 до 96 включительно являются семью последовательными составными числами; найдите девять последовательных составных чисел.
§ 2. Простые числа Мерсенна
В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.
Простые числа Мерсенна являются простыми числами специального вида
М>р = 2>p - 1, (2.2.1)
где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о совершенных числах, которые мы рассмотрим позже. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.
Если начать вычислять числа (2.2.1) для различных простых чисел р, то видно, что не все они оказываются простыми. Например,
М>2 = 2>2 — 1 = 3 = простое,
М>3 = 2>3 — 1 = 7 = простое,
М>5 = 2>5 — 1 = 31 = простое,
М>7 = 2>7 — 1 = 127 = простое,
М>11 = 2>11 — 1 = 2047 = 23 89.
Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел М>p для различных простых чисел р.
Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение. То, что с этой работой все-таки можно справиться уже для довольно больших чисел, объясняется существованием эффективных способов выяснения простоты для чисел такого вида.
В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750 году, когда Леонард Эйлер[5] установил, что число М>31 является простым. К этому времени было найдено восемь простых чисел Мерсенна, соответствующих значениям
