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

---

Фу́нкция Э́йлера ${\displaystyle \varphi (n)}$ — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных ${\displaystyle n}$ и взаимно простых с ним^[1].

Например, для числа 36 существует 12 меньших его и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), поэтому ${\displaystyle \varphi (36)=12}$.

Названа в честь Эйлера, который впервые использовал её в 1763 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования», вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение ${\displaystyle \varphi (n)}$^[2].

Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов (см. сравнение по модулю), теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA^[3].

Функция Эйлера ${\displaystyle \varphi (n)}$ показывает, сколько натуральных чисел из отрезка ${\displaystyle [1,\;n]}$ имеют c ${\displaystyle n}$ только один общий делитель — единицу. Функция Эйлера определена на множестве натуральных чисел, и значения её лежат во множестве натуральных чисел.

Как следует из определения, чтобы вычислить ${\displaystyle \varphi (n)}$, нужно перебрать все числа от ${\displaystyle 1}$ до ${\displaystyle n-1}$, и для каждого проверить, имеет ли оно общие делители с ${\displaystyle n}$, а затем подсчитать, сколько чисел оказались взаимно простыми с ${\displaystyle n}$. Эта процедура для больших чисел ${\displaystyle n}$ весьма трудоёмка, поэтому для вычисления ${\displaystyle \varphi (n)}$ используют другие методы, которые основываются на специфических свойствах функции Эйлера.

---