§5. Некоторые теоретико-числовые приложения комбинаторики §5. Некоторые теоретико-числовые приложения комбинаторики Определение 1. Натуральное число называется простым, если оно имеет ровно два разных делите
Примеры. Числа 2, 3, 5, 7, 11 простые, числа 4, 6, 18, 100 составные. Отметим, что число 1 не является ни простым, ни составным. Существует стандартная система обозначений простых чисел: Р1 – первое по величине простое число (ясно, что Р1 = 2), Р2 – следующее простое число, (Р2 = 3), (Р3 = 5), (Р4 = 7), (Р5 = 11), (Р6 = 13), (Р7 = 17), (Р8 = 19) и т.д. Вообще Рn – n-ое простое число. К сожалению, не существует аналитической формулы f (n), которая позволила бы вычислять любое простое число Pn. Теорема 2. Простых чисел существует бесконечно много. Доказательство. Допустим, существует лишь конечное число простых чисел. Перечислим их: P1, Р2, …, РN. Значит, любое другое натуральное число содержит в качестве делителя по крайней мере одно из Рi (i = 1, 2, …, N). Рассмотрим число Р = Р1 Р2 … РN + 1. Очевидно, что это число не делится ни на одно из чисел