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

Сентябрь 14, 2022

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

Содержание

2. Количество натуральных делителей числа Теорема Пусть - каноническое разложение натурального числа n (n>1) Количество натуральных делителей
3. Сумма натуральных делителей числа Теорема Если - каноническое разложение натурального числа n (n>1), то сумма всех
4. Примеры
5. Теорема (Евклида) Множество простых чисел бесконечно ………………………
6. Доказательство теоремы Евклида Предположим, что Р – последнее, самое большое простое число Рассмотрим натуральное число М=2∙3∙5∙7∙…∙
7. Теорема (критерий простоты) Если число n>1 и не имеет простых делителей то п – простое Доказательство
8. Решето Эратосфена Эратосфе́н Кире́нский (276 - 194 гг. до н.э.) — греческий математик, астроном, географ, филолог
10. Скачать презентацию

Слайд 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

Примеры

Слайд 5

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

Слайд 6

Доказательство теоремы Евклида
Предположим, что Р – последнее, самое большое простое число

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

Слайд 7

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

то п – простое

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

Слайд 8