Задача
Функция Эйлера φ(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).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет