Вівторок, 23.04.2024, 20:52

Гость

Мішатронік

Меню сайту

Наше опитування

Статистика

Онлайн всього: 1

Гостей: 1

Користувачів: 0

Определение

Функция Эйлера $\phi (n)$ (иногда обозначаемая $\varphi(n)$ или ${\it phi}(n)$ ) — это количество чисел от до , взаимно простых с . Иными словами, это количество таких чисел в отрезке [1; n] , наибольший общий делитель которых с равен единице.

Несколько первых значений этой функции (A000010 в энциклопедии OEIS):

$\phi (1)=1,$
$\phi (2)=1,$
$\phi (3)=2,$
$\phi (4)=2,$
$\phi (5)=4.$

Свойства

Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:

Если — простое число, то $\phi (p)=p-1$ .
(Это очевидно, т.к. любое число, кроме самого , взаимно просто с ним.)
Если — простое, — натуральное число, то $\phi (p^a)=p^a-p^{a-1}$ .
(Поскольку с числом не взаимно просты только числа вида $(k \in \mathcal{N})$ , которых $p^a / p = p^{a-1}$ штук.)
Если и взаимно простые, то $\phi(ab) = \phi(a) \phi(b)$ ("мультипликативность" функции Эйлера).
(Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное число $z \le ab$ . Обозначим через и остатки от деления на и соответственно. Тогда взаимно просто с тогда и только тогда, когда взаимно просто с и с по отдельности, или, что то же самое, взаимно просто с и взаимно просто с . Применяя китайскую теорему об остатках, получаем, что любой паре чисел и $(x \le a, ~ y \le b)$ взаимно однозначно соответствует число $(z \le ab)$ , что и завершает доказательство.)

Отсюда можно получить функцию Эйлера для любого $\it n$ через его факторизацию (разложение на простые сомножители):

если

$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot [...]$

(где все p_i — простые), то

$\phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \[...]$
$= (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_[...]$
$= n \cdot \left( 1-{1\over p_1} \right) \cdot \le[...]$

Реализация

Простейший код, вычисляющий функцию Эйлера, факторизуя число элементарным методом за $O (\sqrt n)$ :

int phi (int n) {
 int result = n;
 for (int i=2; i*i<=n; ++i)
 if (n % i == 0) {
 while (n % i == 0)
 n /= i;
 result -= result / i;
 }
 if (n > 1)
 result -= result / n;
 return result;
}

Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа . Его можно осуществить за время, значительно меньшее $O(\sqrt{n})$ : см. Эффективные алгоритмы факторизации.