69
правок
Изменения
→Различные свойства функции Эйлера
Рассмотрим <math>n</math> дробей <math>\frac{1}{n}, \frac{2}{n}, \dots , \frac{n}{n}</math>. Каждую дробь представим в виде несократимой дроби <math>\frac{p}{q}</math>.
Заметим, что множество значений <math>q</math> {{---}} это множество делителей числа <math>n</math>. Так как дробь <math>\frac{p}{q}</math> несократима, то <math>p</math> и <math>q</math> взаимно-просты. Зная, что <math>p \leq q</math>, легко понять, что всего дробей со знаменателем <math>q</math> ровно <math>\varphi(q)</math>. Так как, все <math>n</math> дробей мы представили в несократимом виде, где знаменатель является делителем <math>n</math>, то <math>\displaystyle \sum_{d | n} \varphi(d) = n</math>, так как всего дробей <math>n</math>, что и требовалось доказать.
}}
