Напомним известные вам определения простого и составного числа. Натуральное число называется простым, если оно имеет только два натуральных делителя: единицу и само это число. Натуральное число называется составным, если оно имеет более двух натуральных делителей. Число 1 не является ни простым, ни составным числом.
Выпишем в порядке возрастания простые числа, входящие в первую сотню натуральных чисел. Получим
В настоящее время составлены таблицы, содержащие миллионы простых чисел. Естественно встаёт вопрос, существует ли наибольшее простое число. Ответ на этот вопрос ещё в III в. до н. э. дал великий греческий математик Евклид, который доказал, что «простых чисел больше, чем любое их число», т. е. бесконечно много.
Проведём соответствующее доказательство. Допустим, что существует наибольшее простое число р. Составим произведение всех простых чисел от 2 до р включительно и обозначим его через а:
а = 2 • 3 • 5 • ... • р.
Рассмотрим число а + 1:
а + 1 = 2 • 3 • 5 • ... • р+1.
Число а + 1 не является простым, так как оно больше р, а по предположению р — наибольшее простое число. Оно не является также составным, так как но свойству делимости суммы не делится ни на одно из простых чисел, входящих в произведение 2 • 3 • 5 • ... • р, а других простых чисел по предположению нет. Полученное противоречие показывает, что предположение неверно и наибольшего простого числа не существует.
Много раз делались попытки найти какое-либо выражение, значениями которого являются только простые числа. Рассмотрим, например, выражение F(n) = 2n2 + 29. Вычисляя его значения при n = 1, 2, 3, ..., найдём, что F(l) = 3, F(2) = 37, F(3) = 47, F(4) = 61, F(5) = 79, F(6) = 101, F(7) = 127. Мы видим, что каждый раз получается простое число. Можно предположить, что значение выражения F(n) при любом натуральном n является простым числом. Однако это не так. Например, число F(29) = 2 • 292 + 29 не является простым, так как из свойства делимости суммы следует, что оно делится на 29. Вообще, доказано, что не существует многочлена F(n) с целыми коэффициентами, значением которого при любом натуральном n является простое число.
Всякое составное число, как известно, можно представить в виде произведения простых чисел или, как говорят, разложить на простые множители и притом единственным способом, если не учитывать порядок множителей. Разложим, например, на простые множители число 360:
При разложении числа на простые множители произведение одинаковых множителей обычно представляют в виде степени:
360 = 23 • З2 • 5.
Разложением чисел на простые множители удобно пользоваться при нахождении их наибольшего общего делителя или наименьшего общего кратною.
Найдём, например, наибольший общий делитель и наименьшее общее кратное чисел 504 и 2352. Разложив каждое из этих чисел на простые множители, получаем, что
504 = 23 • З2 • 7 и 2352 = 24 • 3 • 72.
Чтобы найти наибольший общий делитель этих чисел, надо каждый из множителей взять в степени с наименьшим показателем, с каким он входит в эти числа, а чтобы найти их наименьшее общее кратное — с наибольшим показателем.
Обозначив через d наибольший общий делитель этих чисел, а через к их наименьшее общее кратное, получаем, что
d = 23 • 3 • 7 = 168, k = 23 • З2 • 72 = 7056.
Пример. Наименьшее общее кратное двух чисел равно 96. Одно из этих чисел — число 6. Каким может быть другое число?
Решение: Разложив числа 96 и 6 на простые множители, получаем, что
96 = 25 • 3, 6 = 2 • 3.
Очевидно, что в разложение искомого числа на простые множители должны входить пять двоек и не более одной тройки. Значит, второе число либо равно 25, т. е. 32, либо равно 25 • 3, т. е. 96.
Упражнения
Если в выражении а2 + а + 17 подставлять вместо а числа 0, 1, 2, 3, ..., то сначала получаются простые числа. Укажите наименьшее натуральное значение а, при котором значение этого выражения является составным числом.
Докажите, что значение выражения является составным числом:
а) 159 + З13;
б) 167 + 255 - 414.
Найдите наибольшее двузначное число, равное произведению двух простых чисел.
Пусть р — простое число. Укажите наименьшее значение р, при котором значение выражения 2p - 1 не является простым числом.
Найдите все простые числа, на которые делится сумма:
а) 2 + 22 + 23 + 24;
б) 5 + 52 + 53 + 54.
Разложите на простые множители число: а) 5082; б) 7605.
Разложите на простые множители число а, если
а = 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10.
Найдите наибольший общий делитель чисел:
а) 765 и 315;
б) 792 и 1936.
Найдите наименьшее общее кратное чисел:
а) 294 и 756;
б) 693 и 1617.
В последовательностях записаны в порядке возрастания все натуральные числа, которые не превосходят 200, причём в первой последовательности записаны числа, кратные 6, а во второй — кратные 8:
6, 12, 18, ...;
8, 16, 24, ....
Сколько в этих последовательностях одинаковых чисел?
