О простых и составных числах

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

Выпишем в порядке возрастания простые числа, входящие в первую сотню натуральных чисел. Получим

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.

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

Проведём соответствующее доказательство. Допустим, что существует наибольшее простое число р. Составим произведение всех простых чисел от 2 до р включительно и обозначим его через а:

а = 2 • 3 • 5 • ... • р.

Рассмотрим число а + 1:

а + 1 = 2 • 3 • 5 • ... -р+1.

Число а + 1 не является простым, так как оно больше р, а по предположениюр — наибольшее простое число. Оно не является также составным, так как но свойству делимости суммы не делится ни на одно из простых чисел, входящих в произведение 2 • 3 • 5 • ... • р, а других простых чисел по предположению нет. Полученное противоречие показывает, что предположение неверно и наибольшего простого числа не существует.

Мною раз делались попытки найти какое-либо выражение, значениями которого являются только простые числа. Рассмотрим, например, выражение F(n) = 2n² + 29. Вычисляя его значения при n = 1, 2, 3, ..., найдём, что F(1) = 3, F(2) = 37, F(3) = 47, F(4) = 61, F(5)= 79, F(6)= 101, F(7) = 127. Мы видим, что каждый раз получается простое число. Можно предположить, что значение выражения F(n) при любом натуральном п является простым числом. Однако это не так. Например, число F(29) = 2 • 29² + 29 не является простым, так как из свойства делимости суммы следует, что оно делится на 29. Вообще, доказано, что не существует многочлена F(n) с целыми коэффициентами, значением которого при любом натуральном n является простое число.

Всякое составное число, как известно, можно представить в виде произведения простых чисел или, как говорят, разложить на простые множители и притом единственным способом, если не учитывать порядок множителей. Разложим, например, на простые множители число 360:

360 = 2 • 180 = 2 • 2 • 90 = 2 • 2 • 2 • 45 =

= 2 • 2 • 2 • 3 • 15 = 2 • 2 • 2 • 3 • 3 • 5.

При разложении числа на простые множители произведение одинаковых множителей обычно представляют в виде степени:

360 = 2³ • З² • 5.

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

Окончание >>>