Похожие презентации:
Алгебра. Лекция 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 гг. до н.э.) —греческий математик, астроном, географ, филолог и
поэт. Первый известный ученый, доказавший, что
Земля имеет форму шара