Вопросы к гос. экзамену по дисциплине Математика Алгебра (стр. 11 из 11)
Проведем доказательство методо от противного.
Пусть простых чисел конечное число: p1p2 ¼ pк. Рассмотрим N = p1p2 ¼ pк+1. Исследуем полученное число: 
1) N > 1 => оно простое или составное; N ¹ pi, i = 1, к ; 
2) N 
pi, , i = 1, к =>, т.к. при делении на pi получен остаток 1;3)
N – составное. Если N составное, то ему надлежит делиться на 1, N и еще на какое-нибуть простое число (см. ниже), но это не так, поэтому N не является составным. Полученное противоречие и доказывает теорему. 
Теорема 5. Наименьший, отличный от 1 делитель составного числа, является простым числом.Пусть n Î N имеет делители, отличные от 1. Обозначим тот делитель, который будет наименьшим среди всех делителей. Пусть это натуральное число к, т.е. n = к . m; к, m Î N, к > 1. Исследуем к.
Если к = p – простое число, то теорема верна.
Если к – составное число, то к = к1 m1, тогда n = к1 (m1 m), n к1, к1 < к, что противоречит выбранному наименьшему значению. Это и доказывает теорему. 
Достаточно часто в математике приходитс для числа а Î N выяснять, является оно простым или составным. Для решения подобных задач предложен способ, носящий название “решето Эратосфена…” или способа отсеивания чисел кратных 2,3,…,p,… .Опишем этот способ.
Если даны числа натурального ряда: 1,2,3,4,5,…,n, то для установления какими они являются: простыми или составными, поступают так: вычеркивают 1,2 и каждое второе, ибо каждое второе начинается от 3, делится на 2, поэтому является составным. Затем повторяем эту процедуру для 3. 3 вычеркивается и каждое третье, ибо 6 – третье по счету за 3, делится на 3. названную процедуру повторяют до простого числа с не превосходящего
. Оставшиеся числа являются простыми. 
Такой алгоритм можно использовать и для установления чисел в промежутке от n1 до n2.Опишем его спецификацию . Если надо установить какие числа в промежутке от n1 до n2 являются простыми, то поступим так:
1) выясним простое или составное является число n1:
1.1 Проверим его делимость на 2,3,5,…p ≤
. Если оно не делится на эти простые числа, то оно простое;1.2 Если оно делится хотя бы на одно из этих чисел, то оно составное.
2) при выяснении простого числа n, одновременно поступаем так:
2.1 если n1 2, то вычеркивают его и каждый второй (как в первом случае); и переходим к (n1 + 1);
2.2 если n1 2, то к числу добавляем 1 и вычеркиваем n1 + 1 и любое второе за ним;2.3 если было 2.1, то переходим к (n1 + 1) и проверяется делим его на 3, повторяем процедуру решета Эратосфена переходит к (n1 + 2);
2.4 Если было 2.2, то проверяют делимость на 3;
2.4.1. если n1 3, то проверяю решето Эратосфена и переходят следующему.
не вычеркнутому числу и исследуют его делимое на 5;
2.4.2. если n1 = 3q + r, то в зависимости от r = 1 или r = 2, добавляем 1 или 2 и
n1 + 1, n1 + 2.
И любое третье по счету и т.д.
2.5 Если n1 оказалось простым, то все не вычеркнутые числа тоже простые. Если n1 оказалось составным, а ni – простое, то все стоящие за ni числа остальные простые.