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

Число называется простым, если оно делится только на себя и 1. Например, числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,... простые. Числа, которые имеют кроме себя и 1 другие положительные делители называются составными. Число 1 считается ни простым, ни составным. Оно действительно занимает в ряде натуральных чисел особое положение. Ведь оно имеет только 1 делитель, а все другие натуральные числа имеют два или более двух делителей.

Теорема. Наименьший, отличный от 1, делитель целого числа, большего единицы, есть число простое.

Доказательство: Пусть q - наименьший, отличный от 1, делитель натурального числа Предположим, что число q составное, тогда оно имеет делитель . По свойству транзитивности – делитель числа п, причем , что противоречит выбору числа q. Полученное противоречие говорит о том, что наше предположение неверно и число q простое. ■

Теорема. Простых чисел бесконечно много.

Доказательство: Предположим, что их конечное число и – все простые числа. Тогда число отлично от 1 и от , т.е. составное, а значит оно делится хотя бы на одно простое число. Пусть Тогда т.е. делит 1, а это неверно. Аналогично получим, что N не может делиться ни на одно другое простое число. Противоречие. ■