добавлено: 10 Jun 2008 10:57
редактировано: 18 Oct 2011 20:20

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

Определение

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

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

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

Свойства

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

Если $p$ — простое число, то $\phi (p)=p-1$ .
(Это очевидно, т.к. любое число, кроме самого $p$ , взаимно просто с ним.)
Если $p$ — простое, $a$ — натуральное число, то $\phi (p^a)=p^a-p^{a-1}$ .
(Поскольку с числом $p^a$ не взаимно просты только числа вида $pk$ $(k \in \mathcal{N})$ , которых $p^a / p = p^{a-1}$ штук.)
Если $a$ и $b$ взаимно простые, то $\phi(ab) = \phi(a) \phi(b)$ ("мультипликативность" функции Эйлера).
(Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное число $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$ через его факторизацию (разложение $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;
}

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

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

Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:

$a^{\phi(m)} \equiv 1 \pmod m,$

где $\it a$ и $\it m$ взаимно просты.

В частном случае, когда $\it m$ простое, теорема Эйлера превращается в так называемую малую теорему Ферма:

$a^{m-1} \equiv 1 \pmod m$

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

Задачи в online judges

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