MAXimal

добавлено: 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

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