69
правок
Изменения
→Задача об ожерельях
Мы можем улучшить эту формулу, если рассмотрим выражение <math>\mathrm{gcd}(i,n)</math>. Пусть <math>\mathrm{gcd}(i,n) = q</math>, тогда числа <math>i</math> и <math>n</math> оба делятся на <math>q</math> и больше не имеют общих делителей. Тогда <math>\mathrm{gcd}(\frac{i}{q},\frac{n}{q}) = 1</math>. Таких натуральных <math>i \in [1 ; n]</math> и имеющих <math>\mathrm{gcd}(i,n) = q</math> ровно <tex>\varphi\left(\dfrac{n}{q}\right)</tex>.
Пользуясь функцией Эйлера, мы можем привести формулу к финальному более лаконичному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
== Алгоритм ==
