Задача 60758

Тема:    [ Функция Эйлера ]

Сложность: 3 Классы: 9,10,11

Условие

Функция Эйлера φ(n) определяется как количество чисел от 1 до n, взаимно простых с n. Найдите   a) φ(17);   б) φ(p);   в) φ(p²);   г) φ(p^α).

Решение

г) При подсчете φ(p^α) нужно отбросить все числа, делящиеся на p. Среди чисел от 1 до p^α таких ровно p^α–1. Поэтому  φ(p^α) = p^α–1(p – 1).

Ответ

а) 16;   б)  p – 1;   в)  p(p – 1);   г)  p^α–1(p – 1).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.132