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

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Содержание

Определение

Функция Эйлера 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

Ссылки

Реализация

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

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация