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

Натуральное число p>1 называется простым числом, если оно имеет ровно два делителя 1 и р.

Натуральное число n>1 называется составным числом, если оно имеет больше 2х делителей, т. е. оно делится по крайней мере на одно число не равное 1 и n.

1 — не относится ни к простым, ни к составным числам.

Среди простых чисел существует только одно четное (2), все остальные нечетные.

Свойства:

1) Если простое число рn и n1, то p=n.

Действительно, если предположить, что рn, тогда р имеет три делителя 1, р, n. А это означает, что р — составное, что противоречит условию => p=n.

2) Если р1 и р2 различные простые числа, то р2 нер1 и р1 нер2.

Действительно, предположить противное, т. е. деление возможно, а это значит что простые числа р1 и р2 имеют по 3 делителя, чего быть не может.

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

Натуральное число p>1 называется простым числом, если оно имеет ровно два делителя 1 и р.

Натуральное число n>1 называется составным числом, если оно имеет больше 2х делителей, т. е. оно делится по крайней мере на одно число не равное 1 и n.

Свойства:

3) Всякое натуральное число n>1 делится по крайней мере на одно простое число.

Докажем методом мат. индукции:

n>1, n=2, n2 — верно.

Предположим, что для всех натуральных чисел до (n-1) включительно это верно.

Если n-простое число, то утверждение верно.

Если n-составное, то можно представить n=n1*n2; n1, n2.

4) Если n-натуральное число, р-простое, то либо nр, либо (n, p)=1, n1.

Пусть (n, p)=d, тогда nd и pd => d=1, p=d.

Если d=1, то (n, p)=1,а если d=p, то np.

5) Если произведение 2х или более натуральных чисел делится на просто число р, то хотя бы один из сомножителей делится на р.

Пусть (a*b)p => ap или b. Если ар, то теорема доказана.

Пусть, а не р, тогда (а, р)=1, х, у =>

ах+ру=1 (*b).

(ab)x+pby=b — все делится на b.