Числовые функции (Количество и сумма натуральных делителей числа. Функция Эйлера). Лекция 2

1. Лекция 2 Числовые функции (Количество и сумма натуральных делителей числа. Функция Эйлера)

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. Функция Эйлера

6. Функция Эйлера

Пример:
1 1 1
60 60 1 1 1 16 ,
2 3 5
φ(81) = 81 – 27 = 54,
φ(5) = 5 – 1 = 4.