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

Простым числом называется такое натуральное число, большее 1, которое имеет только два делителя – единицу и само это число.

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

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

Простые числа играют большую роль в математике – по существу они являются «кирпичиками», из которых строятся составные числа. Это утверждается в теореме, называемой основной теоремой арифметики натуральных чисел: любое составное число можно единственным образом представить в виде произведения простых множителей.

Например, запись 330=2·3·5·11 есть представление числа 330 в виде произведения простых множителей или разложение его на простые множители.

Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей. Поэтому представление числа 330 в виде произведения 2·3·5·11 или произведения 3·5·11·2 есть, по существу, одно и то же разложение числа 330 на простые множители.

Раскладывая числа на простые множители, используют признаки делимости на 2, 3, 5 и др., а повторяющиеся простые множители представляют в виде степени. Например, 240=2·2·2·2·3·5=24·3·5. Такое разложение числа на простые множители называют каноническим.

Задача 30. Разложить число 180 на простые множители.

Решение. Число 180 делится на 2. Значит, 2 есть один из простых множителей в разложении числа 180. Разделим 180 на 2. Число 2 запишем справа от знака равенства, а частное 90 – под числом 180. Число 90 делим на простое число 2, получаем 45. Число 45 на простое число 3, получаем 15. Делим 15 на 3, получаем 5. Число 5 – простое, при делении его на 5 получаем 1. Разложение на множители закончено.

Таким образом, 180=22·32·5.

В связи с возможностью представлять любое составное число в виде произведения простых множителей возникает необходимость определять, является данное число простым или составным. Эту задачу умели решать еще древнегреческие математики, которым были известны многие свойства простых чисел. Так, Эратосфеном (III в. до н.э.) был придуман способ получения простых чисел, не превышающих натурального числа а. Воспользуемся им для поиска всех простых чисел от 1 до 50.

Выпишем все натуральные числа от 1 до 50 и зачеркнем число 1 – оно не является простым. Число 2 – простое, обведем его кружком. После этого зачеркиваем каждое второе число, стоящее после 2, т.е. числа 4, 6, 8,...

Первое незачеркнутое число 3 является простым, обведем его кружком. И вычеркнем каждое третье число, стоящее после 3, т.е. числа 9, 15,... (числа 6, 12 и др. зачеркнуты раньше).

Первое незачеркнутое число 5 является простым, его также обведем кружком. Зачеркнем каждое пятое число после 5 и т.д.

Те числа, которые останутся после четырех вычеркиваний (исключая числа 2, 3, 5 и 7), не делятся ни на 2, ни на 3, ни на 5, ни на 7. В арифметике доказано, что если натуральное число а, большее единицы, не делится ни на одно из простых чисел, квадрат которых не превосходит а, то а число простое. Поскольку 72 = 49, а 49 < 50, то все оставшиеся числа – простые.

Итак, простыми числами, не превосходящими 50, являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

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

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