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

Fobee · января 6, 2012, 14:45

Есть такая задача, при решении которой я столкнулся с трудностью:

Доказать, что сумма $[tex]\phi (d)[/tex]$ по всем делителям d числа m равна m.

Начало моего решения:
$[tex]m=\prod_{i=1}^n d_i^{k_i}[/tex]$
$[tex]\sum_{j=1}^{k_i} \phi \left (d_i^{k_j} \right ) = (d_i - 1) \left (1+d_i+d_i^2+ \cdots + d_i^{k_i-1} \right ) = d_i^{k_i} - 1[/tex]$
Проблема в том, что делители числа m не ограничиваются тем, что я написал, и непонятно, как собрать всё воедино. Заранее спасибо.

Тайльнемер · января 6, 2012, 15:45

Нашёл доказательство. Сам бы до такого не догадался.

Цитировать
Выпишем дроби: . Этих дробей ровно $[tex]m[/tex]$ .
Теперь сократим все дроби (первую дробь сократим до ). Очевидно, что у сокращённых дробей знаменатели будут делителями числа $[tex]m[/tex]$ . Причём дробей с каждым знаменателем-делителем $[tex]d[/tex]$ будет ровно , потому что всякая правильная несократимая дробь со знаменателем $[tex]d[/tex]$ получится, а вариантов числителя в точности . Общее количество дробей тогда будет .
Но это равно $[tex]m[/tex]$ , поскольку всего есть ровно $[tex]m[/tex]$ дробей. Что и требовалось доказать.

Fobee · января 6, 2012, 16:01

Спасибо большое. Такой приём - это изыск.

Лингвофорум

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

Fobee

Тайльнемер

Fobee

Быстрый ответ