MAXimal

Функция Эйлера и её вычисление

Page source on a TeX-like language:

\h1{ Функция Эйлера }

\h2{ Определение }

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

Несколько первых значений этой функции (\href=http://oeis.org/A000010{A000010 в энциклопедии OEIS}):

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

\h2{ Свойства }

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

\ul{

\li Если $p$ --- простое число, то $\phi (p)=p-1$.

(Это очевидно, т.к. любое число, кроме самого $p$, взаимно просто с ним.)

\li Если $p$ --- простое, $a$ --- натуральное число, то $\phi (p^a)=p^a-p^{a-1}$.

(Поскольку с числом $p^a$ не взаимно просты только числа вида $pk$ $(k \in \mathcal{N})$, которых $p^a / p = p^{a-1}$ штук.)

\li Если $a$ и $b$ взаимно простые, то $\phi(ab) = \phi(a) \phi(b)$ ("мультипликативность" функции Эйлера).

(Этот факт следует из \algohref=chinese_theorem{китайской теоремы об остатках}. Рассмотрим произвольное число $z \le ab$. Обозначим через $x$ и $y$ остатки от деления $z$ на $a$ и $b$ соответственно. Тогда $z$ взаимно просто с $ab$ тогда и только тогда, когда $z$ взаимно просто с $a$ и с $b$ по отдельности, или, что то же самое, $x$ взаимно просто с $a$ и $y$ взаимно просто с $b$. Применяя китайскую теорему об остатках, получаем, что любой паре чисел $x$ и $y$ $(x \le a, ~ y \le b)$ взаимно однозначно соответствует число $z$ $(z \le ab)$, что и завершает доказательство.)

}

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

если

$$ n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k} $$

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

$$ \phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdot \ldots \cdot \phi(p_k^{a_k}) = $$
$$ = (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_2^{a_2-1}) \cdot \ldots \cdot (p_k^{a_k} - p_k^{a_k-1}) = $$
$$ = n \cdot \left( 1-{1\over p_1} \right) \cdot \left( 1-{1\over p_2} \right) \cdot \ldots \cdot \left( 1-{1\over p_k} \right). $$

\h2{ Реализация }

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

\code
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;
}
\endcode

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

\h2{ Приложения функции Эйлера }

Самое известное и важное свойство функции Эйлера выражается в \bf{теореме Эйлера}:
$$ a^{\phi(m)} \equiv 1 \pmod m, $$
где $\it a$ и $\it m$ взаимно просты.

В частном случае, когда $\it m$ простое, теорема Эйлера превращается в так называемую \bf{малую теорему Ферма}:
$$ a^{m-1} \equiv 1  \pmod m $$

Теорема Эйлера достаточно часто встречается в практических приложениях, например, см. \algohref=reverse_element{Обратный элемент в поле по модулю}.

\h2{ Задачи в online judges }

Список задач, в которых требуется посчитать функцию Эйлера,либо воспользоваться теоремой Эйлера, либо по значению функции Эйлера восстанавливать исходное число:

\ul{

\li \href=http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120{UVA #10179 \bf{"Irreducible Basic Fractions"} ~~~~ [сложность: низкая]}

\li \href=http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1240{UVA #10299 \bf{"Relatives"} ~~~~ [сложность: низкая]}

\li \href=http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302{UVA #11327 \bf{"Enumerating Rational Numbers"} ~~~~ [сложность: средняя]}

\li \href=http://acm.timus.ru/problem.aspx?space=1&num=1673{TIMUS #1673 \bf{"Допуск к экзамену"} ~~~~ [сложность: высокая]}

}