ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .