Числа простые и составные
Множество целых неотрицательных чисел по количеству делителей разбивается на следующие классы:
1. Класс чисел, имеющих один единственный делитель. Этот класс содержит только 1 (это число ни простое, ни составное).
2. класс простых чисел.
3. Класс чисел, содержащий бесконечное множество делителей. Этот класс содержит только число 0.
4. класс составных чисел, имеющих более двух делителей.
Решето Эратосфена
Греческий математик и астроном, живший в III веке до н. э. Эратосфен Киренский дал один из первых способов поиска простых чисел не превосходящих натурального числа а, основанный на вычеркивании чисел по определенному правилу.
Воспользуемся им для определения всех простых чисел до 40.
В
ыпишем
все натуральные числа от 1 до 40.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
2.Зачеркнем число 1, оно не является простым.
3. Число 2 – простое, оно имеет только два делителя, обведем его.
4. После этого зачеркнем каждое второе число, стоящее после 2, то есть 4, 6, 8, …
5. Первое не зачеркнутое число 3 является простым, обведем его.
6. Вычеркнем каждое третье число, стоящее после 3, то есть числа 9, 15, … (числа 6, 12 и др. зачеркнули ранее).
7. Первое не зачеркнутое число 5 является простым, обведем его и зачеркнем каждое пятое число, стоящее после 5.
8. Те числа, которые останутся после четырех зачеркиваний являются простыми.
Метод Эратосфена позволяет отыскивать все простые числа, не превосходящие заданного числа а. Но он не дает ответа на вопрос: конечно или бесконечно множество простых чисел.
Решением этой проблемы занимался греческий математик Евклид.
Теорема Евклида. Множество простых чисел бесконечно.
Доказательство проведем методом от противного.
Предположим, что множество простых чисел конечно и состоит из чисел 2, 3, 5, 7, …, р, где р – самое большое простое число.
Если множество простых чисел конечно, то существует произведение всех этих чисел: 2 3 5 7 … р = k.
Прибавим к произведению всех простых чисел 1 и рассмотрим число k + 1.
Очевидно, что k + 1 > k k > р k + 1 > р.
Число k + 1 простым быть не может, так как мы предположили, что выписали все простые числа и других простых чисел нет.
Следовательно, число k + 1 – составное. В этом случае оно должно иметь хотя бы один простой делитель.
Число k + 1 не делится ни на одно из чисел 2, 3, 5, 7, …, р, так как при делении на любое из них получается остаток, равный 1. следовательно, число k + 1 – простое и предположение, что множество простых чисел конечно неверно и значит множество простых чисел бесконечно.