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

Определение

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

Первые значения этой функции:

$n$	1	2	3	4	5	6	7	8	9	10
$phi(n)$	1	1	2	2	4	2	6	4	6	4

Далее в ряде A000010 в энциклопедии OEIS.

Свойства

• Если $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)$ ("мультипликативность" функции Эйлера).

Пояснение: Этот факт следует из китайской теоремы об остатках.

Функция Эйлера для произвольного $n$

Функцию Эйлера можно получить для любого $n$ через его факторизацию (разложение $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)$

Приложения

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

• $a^{phi(m)} \equiv 1 \pmod m$, где $a$ и $m$ взаимно просты.

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

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

Ссылки

• Функция Эйлера на e-maxx.ru (для программистов)
• Функция Эйлера в Википедии (для математиков)

Реализация

• Поиск значения функции Эйлера он-лайн (скоро)