Алгебра. Лекция 4. Количество и сумма натуральных делителей числа. Критерий простоты. Решето Эратосфена

1. Лекция 4 Количество и сумма натуральных делителей числа. Критерий простоты. Решето Эратосфена

2. Количество натуральных делителей числа

Теорема
Пусть
- каноническое
разложение натурального числа n (n>1)
Количество натуральных делителей числа n
равно τ(n) = (α1 +1)(α2 +1)…(αs +1)
Пример
τ(60)= τ(2²∙3∙5)=(2+1)(1+1)(1+1)=12

3. Сумма натуральных делителей числа

Теорема
Если
- каноническое
разложение натурального числа n (n>1),
то сумма всех натуральных делителей
числа n равна

4.

Примеры
1000000 26 56 7 7 49;
2 7 1 57 1
1000000
;
2 1 5 1
4050 2 34 52 2 5 3 30;
2 2 1 35 1 53 1
4050
11253.
2 1 3 1 5 1

5. Теорема (Евклида) Множество простых чисел бесконечно

2 3 1 7,
2 3 5 1 31,
2 3 5 7 1 211,
2 3 5 7 11 1 2311,
2 3 5 7 11 13 1 30031,
………………………

6. Доказательство теоремы Евклида

• Предположим, что Р – последнее, самое большое простое
число
• Рассмотрим натуральное число М=2∙3∙5∙7∙…∙ Р +1
• Если число М составное, то оно должно иметь по
крайней мере один простой делитель
• Но этим делителем не может быть ни одно из простых
чисел 2, 3, 5, …, Р, поскольку при делении М на каждое из
них получается остаток 1
• Следовательно, число М либо само простое, либо
делится на простое число, большее Р
• Значит, предположение, что существует наибольшее
простое число Р, неверно и множество простых чисел
бесконечно

7. Теорема (критерий простоты) Если число n>1 и не имеет простых делителей то п – простое

Теорема (критерий простоты)
Если число n>1 и не имеет простых
делителей p n , то п – простое
Доказательство
• Если бы п было составным, то n=ab, где 1<a<n и 1<b<n
• Оба множителя не могут быть больше n , иначе их
произведение ab было бы больше п
• Следовательно, хотя бы одно из чисел а и b не
превышает n
• Если, например, число a n , то его простой делитель
p n.
• Таким образом, любое составное число имеет простой
делитель, не превышающий n

8. Решето Эратосфена

Эратосфе́н Кире́нский (276 - 194 гг. до н.э.) —
греческий математик, астроном, географ, филолог и
поэт. Первый известный ученый, доказавший, что
Земля имеет форму шара