Задача 60760

Темы:    [ Функция Эйлера ] [ Арифметика остатков (прочее) ]

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

Условие

Функция Эйлера  φ(n)  определяется как количество чисел от 1 до n, взаимно простых с n.
Основным свойством функции Эйлера является её мультипликативность.
Для взаимно простых a и b рассмотрим таблицу

В каких столбцах этой таблицы находятся числа взаимно простые с числом b?
Сколько в каждом из этих столбцов чисел взаимно простых с a?
Докажите мультипликативность функции Эйлера, ответив на эти вопросы.

Подсказка

Числа, взаимно простые с b, находятся в  φ(b)  столбцах. В каждом из них  φ(a)  чисел, взаимно простых с a (см. задачу 60733).

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

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