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

В зависимости от числа делителей среди натуральных чисел различают простые и составные  числа.

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

Например, число 13 – простое, поскольку у него только два делителя: 1 и 13.

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

Так число 4 составное, у него три делителя: 1, 2 и 4.

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

Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, … , и все они могут быть получены по формуле a = 4q , где q принимает значения 1, 2, 3, … .

Докажем некоторые свойства простых чисел.

1. Если простое число p делиться на некоторое натуральное число n, отличное от 1, то оно совпадает с n.

Доказательство. Если бы pn, то оно имело бы три делителя: 1, n и p, а тогда оно не было бы простым.

2. Если p и q – различные простые числа, то p не делиться на q.

Доказательство. Так как p – простое, то оно делиться на 1 и само на себя. Но по условию q – простое и pq. Значит, оно делиться на q, на 1 и отлично от 1. Значит, q не является делителем числа p.

3. Если натуральное число a не делиться на простое число p, то a и p взаимно простые.

Доказательство. Возьмем НОД(a, p) = d. Тогда pd. Но простое число p имеет лишь два делителя: 1 и p . Поэтому либо d=p, либо d=1. Если бы d=p, то ap вопреки условию. Значит, остается лишь случай d=1. А в этом случае а и р взаимно простые.

4. Если произведение двух натуральных чисел a и b делиться на простое число p, то хотя бы одно из них делиться на p.

Доказательство. Предположим, что, а не делиться на p. Тогда по свойству 3 числа а и р взаимно простые. Но так как a