Четыре класса целых неотрицательных чисел.Простые и составные числа

Число 0 имеет бесконечно много делителей. Число 1 имеет единственный делитель 1. Любое натуральное число а > 1 имеет конечное число делителей, а в Þ 1 ≤ в ≤ а, т.е. в может принимать не более чем а различных значений.

Определение. Натуральное число, большее 1, называется простым, если оно делится только на себя и на 1. Натуральное число а называется составным, если а d, где 1 < d < а.

По числу различных натуральных делителей множество целых неотрицательных чисел N ₀ разбивается на четыре попарно непересекающихся подмножества (класса):

1) число 1 (имеет один натуральный делитель);

2) числа простые (имеют точно два натуральных делителя);

3) числа составные (имеют не менее трех различных натуральных делителей);

4) число 0 (имеет бесконечно много натуральных делителей).

Теорема 1 (о существовании простого делителя).

Если натуральное число а > 1,то оно имеет хотя бы один простой делитель.

Доказательство (методом от противного).

Пусть дано число а. Обозначим буквой d –наименьший среди натуральных делителей числа а, больших единицы. Предположим, что d не является простым числом, а значит имеет делитель t.

Т.е. d t Ù t < d, докажем, что t = 1. Т.к. а d Ù d t Þ а t, но ведь это означает, что t еще меньший, чем d делитель числа а, что противоречит выбору d, значит t = 1,т.е. d имеет только два натуральных делителя d и 1.

Теорема 2. Наименьший простой делитель составного числа а не превосходит .

Доказательство. Пусть дано число а. Обозначим буквой р его наименьший простой делитель, тогда а = р · в, при этом р ≤ в, т.к. иначе простой делитель числа в был бы меньше, чем р. Тогда а имело бы простые делители меньшие, чем р. Умножим левую и правую часть неравенства р ≤ в на р, получим р ² ≤ р · в = а Þ р ≤ .

Следствие. Если число а не делится ни на одно простое число, не превосходящее , то у него нет совсем простых делителей, меньших этого числа, т.е. это число простое.

Например, 137 простое число. В самом деле, 1l < < 12, если 137 не делится на простые числа меньшие 12, то оно простое. 137 не делится на 2, на 3, на 5, на 7, на 11. Вывод: 137 – простое число.

Дата добавления: 2015-07-18