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


==  Определение  ==


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

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

<math> \phi (1)=1, </math>
<math> \phi (2)=1, </math>
<math> \phi (3)=2, </math>
<math> \phi (4)=2, </math>
<math> \phi (5)=4. </math>


==  Свойства  ==


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



* Если <math>p</math> &mdash; простое число, то <math>\phi (p)=p-1</math>.

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

* Если <math>p</math> &mdash; простое, <math>a</math> &mdash; натуральное число, то <math>\phi (p^a)=p^a-p^{a-1}</math>.

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

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

(Этот факт следует из [[китайской теоремы об остатках|китайской теоремы об остатках]]. Рассмотрим произвольное число <math>z \le ab</math>. Обозначим через <math>x</math> и <math>y</math> остатки от деления <math>z</math> на <math>a</math> и <math>b</math> соответственно. Тогда <math>z</math> взаимно просто с <math>ab</math> тогда и только тогда, когда <math>z</math> взаимно просто с <math>a</math> и с <math>b</math> по отдельности, или, что то же самое, <math>x</math> взаимно просто с <math>a</math> и <math>y</math> взаимно просто с <math>b</math>. Применяя китайскую теорему об остатках, получаем, что любой паре чисел <math>x</math> и <math>y</math> <math>(x \le a, ~ y \le b)</math> взаимно однозначно соответствует число <math>z</math> <math>(z \le ab)</math>, что и завершает доказательство.)

</ul>

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

если

<math> n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k} </math>



(где все <math>p_i</math> &mdash; простые), то

<math> \phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdot \ldots \cdot \phi(p_k^{a_k}) = </math>
<math> = (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}) = </math>
<math> = 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). </math>


==  Реализация  ==


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

<source>
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;
}
</source>



Ключевое место для вычисление функции Эйлера &mdash; это нахождение '''факторизации''' числа <math>n</math>. Его можно осуществить за время, значительно меньшее <math>O(\sqrt{n})</math>: см. [[Эффективные алгоритмы факторизации|Эффективные алгоритмы факторизации]].


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


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

<math> a^{\phi(m)} \equiv 1 \pmod m, </math>


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

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

<math> a^{m-1} \equiv 1  \pmod m </math>



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


==  Задачи в online judges  ==


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



* [[''''''UVA #10179 "Irreducible Basic Fractions" ~~~~ [сложность: низкая]|UVA #10179 "Irreducible Basic Fractions" ~~~~ [сложность: низкая]]]

* [[''''''UVA #10299 "Relatives" ~~~~ [сложность: низкая]|UVA #10299 "Relatives" ~~~~ [сложность: низкая]]]

* [[''''''UVA #11327 "Enumerating Rational Numbers" ~~~~ [сложность: средняя]|UVA #11327 "Enumerating Rational Numbers" ~~~~ [сложность: средняя]]]

* [[''''''TIMUS #1673 "Допуск к экзамену" ~~~~ [сложность: высокая]|TIMUS #1673 "Допуск к экзамену" ~~~~ [сложность: высокая]]]

</ul>