Простые и составные числа

Теория чисел

ПРОСТЫЕ ЧИСЛА. ДЕЛИТЕЛИ ЧИСЕЛ

Простые и составные числа

Давайте вспомним, что когда число c = a * b является произведением двух чисел a и b, то мы называем а и b множителями или делителями числа с.

Каждое число имеет тривиальное разложение на множители с = 1 * с = с * 1.

Соответственно мы называем числа 1 и с тривиальными делителями числа с.

Любое число с > 1, у которого существует нетривиальное разложение на множители, называется составным.

Если число с имеет только тривиальное разложение на множители, то оно называется простым.

Среди первых 100 чисел простыми являются следующие 25 чисел:

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, являются составными. Мы можем сформулировать следующее утверждение:

Теорема Любое целое число с> 1 является, либо простым, либо имеет простой множитель.

Доказательство. Если с не является простым, числом, то у него есть наименьший нетривиальный множитель р. Тогда р — простое число, так как если бы р — было составным, то число с имело бы ещё меньший множитель.

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

Первое, что может прийти в голову, — это попытаться разделить данное число с на все числа, меньшие его. Но надо признать, что этот способ мало удовлетворителен. Однако, мы можем значительно упростить задачу, заметив, что при разложении на множители оба множителя а и b не могут быть больше, чем √ с, так как в противном случае мы получили бы

ab > √ с • √ с,

что невозможно. Таким образом, чтобы узнать, имеет ли число с делитель, достаточно проверить, делится ли число с на простые числа, не превосходящие — √ с.

Пример 1. Если с =1973, то находим, что √ с = 44…. Так как ни одно из простых чисел до 43 не делит с, то это число является простым.

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

Другим очень простым методом является применение таблиц простых чисел, т. е. использование простых чисел уже найденных другими. За последние 200 лет было составлено и издано много таблиц простых чисел. Наиболее обширной из них является таблица Д. X. Лемера, содержащая все простые числа до 10 000 000. Наша таблица содержит все простые числа до 1000.

Таблица:

Простые числа среди первой тысячи чисел

Упражнение 1. Заметим, что числа от 90 до 96 включительно являются семью последовательными составными числами; найдите четырнадцать последовательных составных чисел.

Дата добавления: 2015-08-05