Функция Эйлера - NiNa.Az

Не следует путать с функцией распределения простых чисел.

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

Первая тысяча значений ${\displaystyle \varphi (n)}$

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

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

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

Вычисление

Первые 99 значений функции Эйлера

${\displaystyle \varphi (n)}$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Общие сведения

Функция Эйлера ${\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)}$ используют другие методы, которые основываются на специфических свойствах функции Эйлера.

В таблице справа представлены первые 99 значений функции Эйлера. Значение ${\displaystyle \varphi (n)}$ при ${\displaystyle n>1}$ не превосходит ${\displaystyle n-1}$, и в точности ему равно, если ${\displaystyle n}$ — простое. Таким образом, если в координатах ${\displaystyle (n,\;y)}$ провести прямую ${\displaystyle y=n-1}$, то значения ${\displaystyle y=\varphi (n)}$ будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения ${\displaystyle \varphi (n)}$ снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число ${\displaystyle n}$, такое, что ${\displaystyle \varphi (n)}$ лежит ниже этой прямой. Ещё одной интересной особенностью графика является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой ${\displaystyle y=n-1}$, на которой лежат значения ${\displaystyle \varphi (n)=n-1}$, где ${\displaystyle n}$ — простое, выделяется прямая, примерно соответствующая ${\displaystyle y=n/2}$, на которую попадают значения ${\displaystyle \varphi (2n)=\varphi (n)=n-1}$, где ${\displaystyle n}$ — простое.

Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.

Мультипликативность функции Эйлера

Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел ${\displaystyle m}$ и ${\displaystyle n}$

${\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}$

Доказательство мультипликативности

Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема.

Теорема 1. Пусть ${\displaystyle (m,\;m')=1}$ и ${\displaystyle a}$ пробегает полную систему вычетов по модулю ${\displaystyle m}$, в то время как ${\displaystyle a'}$ пробегает полную систему вычетов по модулю ${\displaystyle m'}$. Тогда числа ${\displaystyle a'm+am'}$ образуют полную систему вычетов по модулю ${\displaystyle mm'}$.

Доказательство. Если

${\displaystyle a_{1}'m+a_{1}m'\equiv a_{2}'m+a_{2}m'{\pmod {mm'}},}$

тогда

${\displaystyle a_{1}m'\equiv a_{2}m'{\pmod {m}},}$

поэтому

${\displaystyle a_{1}\equiv a_{2}{\pmod {m}};}$

аналогично

${\displaystyle a_{1}'\equiv a_{2}'{\pmod {m'}}.}$

Поэтому существует ${\displaystyle mm'}$ несравнимых по модулю чисел, которые образуют полную систему вычетов по модулю ${\displaystyle mm'}$.

Теперь можно доказать основное утверждение.

Теорема 2. Функция Эйлера мультипликативна.

Доказательство. Если ${\displaystyle (m,\;m')=1}$, то по Теореме 1 достаточно найти все значения ${\displaystyle a'm+am'}$ которые взаимно просты с ${\displaystyle mm'}$:

${\displaystyle (a'm+am',\;mm')=1}$

${\displaystyle \Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1}$

${\displaystyle \Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1}$

${\displaystyle \Leftrightarrow (a,\;m)=1,\;(a',\;m')=1.}$

Покажем справедливость первого перехода от противного

Обозначим ${\displaystyle z=a'm+am'}$.

${\displaystyle (\Rightarrow )}$ Дано ${\displaystyle (z,\;mm')=1}$. Пусть ${\displaystyle (z,\;m)=d>1}$, тогда ${\displaystyle (z,\;mm')\geqslant d}$ — противоречие

${\displaystyle (\Leftarrow )}$ Дано ${\displaystyle (z,\;m)=1,\;(z,\;m')=1}$. Пусть ${\displaystyle (z,\;mm')=d>1}$, тогда либо ${\displaystyle m}$, либо ${\displaystyle m'}$ будут иметь общий множитель с ${\displaystyle z}$ (например по Лемме Евклида) — противоречие.

Поэтому ${\displaystyle \varphi (mm')}$ чисел, которые меньше числа ${\displaystyle mm'}$ и взаимно просты с ним, являются наименьшими положительными вычетами среди ${\displaystyle \varphi (m)\varphi (m')}$ значений ${\displaystyle a'm+am'}$, для которых ${\displaystyle a}$ взаимно просто с ${\displaystyle m}$ и ${\displaystyle a'}$ взаимно просто с ${\displaystyle m'}$. Отсюда следует, что

${\displaystyle \varphi (mm')=\varphi (m)\varphi (m').}$

Функция Эйлера от простого числа

Для простого ${\displaystyle p}$ значение функции Эйлера задаётся явной формулой:

${\displaystyle \varphi (p)=p-1,}$

которая следует из определения. Действительно, если ${\displaystyle p}$ — простое, то все числа, меньшие ${\displaystyle p}$, взаимно просты с ним, а их ровно ${\displaystyle p-1}$ штук.

Для вычисления функции Эйлера от степени простого числа используют следующую формулу:

${\displaystyle \varphi (p^{n})=p^{n}-p^{n-1}.}$

Это равенство обосновывается следующим образом. Подсчитаем количество чисел от ${\displaystyle 1}$ до ${\displaystyle p^{n}}$, которые не взаимно просты с ${\displaystyle p^{n}}$. Все они, очевидно, кратны ${\displaystyle p}$, то есть, имеют вид: ${\displaystyle p,\;2p,\;3p,\;\ldots ,\;p^{n-1}p.}$ Всего таких чисел ${\displaystyle p^{n-1}}$. Поэтому количество чисел, взаимно простых с ${\displaystyle p^{n}}$, равно ${\displaystyle p^{n}-p^{n-1}}$.

Функция Эйлера от натурального числа

Вычисление ${\displaystyle \varphi (n)}$ для произвольного натурального ${\displaystyle n}$ основывается на мультипликативности функции Эйлера, выражении для ${\displaystyle \varphi (p^{n})}$, а также на основной теореме арифметики. Для произвольного натурального числа значение ${\displaystyle \varphi (n)}$ представляется в виде:

${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),\;\;n>1,}$

где ${\displaystyle p}$ — простое число и пробегает все значения, участвующие в разложении ${\displaystyle n}$ на простые сомножители.

Доказательство

Как следует из основной теоремы арифметики, всякое натуральное число ${\displaystyle n>1}$ единственным образом представляется в виде:

${\displaystyle n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{k}^{\alpha _{k}},}$

где ${\displaystyle p_{1}<\ldots <p_{k}}$ — простые числа, ${\displaystyle \alpha _{1},\;\ldots ,\;\alpha _{k}}$ — натуральные числа.

Используя мультипликативность функции Эйлера и выражение для ${\displaystyle \varphi (p^{k})}$, получаем: ${\displaystyle {\begin{aligned}\varphi (n)&=\varphi (p_{1}^{\alpha _{1}})\varphi (p_{2}^{\alpha _{2}})\cdot \ldots \cdot \varphi (p_{k}^{\alpha _{k}})=\\&=p_{1}^{\alpha _{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{\alpha _{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{k}}}\right)=\\&=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right)=\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right).\end{aligned}}}$

Пример применения:

${\displaystyle \varphi (36)=\varphi (2^{2}\cdot 3^{2})=\varphi (2^{2})\varphi (3^{2})=(2^{2}-2)(3^{2}-3)=2\cdot 6=12.}$

${\displaystyle \varphi (36)=\varphi (2^{2}\cdot 3^{2})=36\cdot {\Bigl (}1-{\frac {1}{2}}{\Bigr )}\cdot {\Bigl (}1-{\frac {1}{3}}{\Bigr )}=36\cdot {\frac {1}{2}}\cdot {\frac {2}{3}}=36\cdot {\frac {1}{3}}=12}$

Свойства

Обобщённая мультипликативность

Функция Эйлера является мультипликативной арифметической функцией, то есть

${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\;\;\;\forall m,\,n\in \mathbb {N} \colon (m,\,n)=1.}$

Здесь существенно, что наибольший общий делитель ${\displaystyle m}$ и ${\displaystyle n}$ равен единице. Оказывается, существует обобщение этой формулы на случай, когда ${\displaystyle m}$ и ${\displaystyle n}$ имеют общие делители, отличные от единицы. А именно, для любых натуральных ${\displaystyle m}$ и ${\displaystyle n}$ :

${\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)\cdot {\frac {d}{\varphi (d)}},}$

где ${\displaystyle d}$ — наибольший общий делитель ${\displaystyle m}$ и ${\displaystyle n.}$ Это свойство является естественным обобщением мультипликативности.

Доказательство обобщённой мультипликативности

Пусть ${\displaystyle (m,\,n)=d,}$ тогда ${\displaystyle m=m'd,\;n=n'd,}$ причем в общем случае ${\displaystyle (m',\,d)\neq 1}$ и ${\displaystyle (n',\,d)\neq 1.}$ Поэтому можно записать:

${\displaystyle d=d_{1}^{\delta _{1}}\cdot \ldots \cdot d_{k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}},}$

${\displaystyle m'=d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{1}}\cdot \ldots \cdot p_{r}^{\beta _{r}},}$

${\displaystyle n'=d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}.}$

Здесь первые ${\displaystyle k}$ делителей ${\displaystyle d}$ являются также делителями ${\displaystyle m',}$ а последние ${\displaystyle K-k}$ делителей ${\displaystyle d}$ являются делителями ${\displaystyle n'.}$ Распишем:

${\displaystyle \varphi (mn)=\varphi (d^{2}\cdot m'n')=\varphi ((d_{1}^{\delta _{1}}\cdot \ldots \cdot d_{k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}})^{2}\cdot d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{1}}\cdot \ldots \cdot p_{r}^{\beta _{r}}\cdot d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}).}$

В силу мультипликативности функции Эйлера, а также с учётом формулы

${\displaystyle \varphi (p^{n})=p^{n}(1-{\frac {1}{p}}),}$

где ${\displaystyle p}$ — простое, получаем:

${\displaystyle {\begin{aligned}\varphi (mn)&=d_{1}^{\alpha _{1}+\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k}^{\alpha _{k}+\delta _{k}}\left(1-{\frac {1}{d_{k}}}\right)\cdot p_{1}^{\beta _{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdot \ldots \cdot p_{r}^{\beta _{r}}\left(1-{\frac {1}{p_{r}}}\right)\cdot d_{k+1}^{\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\delta _{K}}\left(1-{\frac {1}{d_{K}}}\right)\times \\&\;\times \;d_{k+1}^{\gamma _{k+1}+\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\gamma _{K}+\delta _{K}}\left(1-{\frac {1}{d_{K}}}\right)\cdot q_{1}^{\varepsilon _{1}}\left(1-{\frac {1}{q_{1}}}\right)\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}\left(1-{\frac {1}{q_{s}}}\right)\cdot d_{1}^{\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k+1}^{\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\times \\&\;\times \;{\frac {1}{\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{d_{K}}}\right)}}.\end{aligned}}}$

В первой строке записано ${\displaystyle \varphi (m),}$ во второй — ${\displaystyle \varphi (n),}$ а третью можно представить, как ${\displaystyle d/\varphi (d).}$ Поэтому:

${\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)\cdot {\frac {d}{\varphi (d)}}.}$

Некоторые частные случаи:

• ${\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n).}$
• ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m),&m=2k,\;k\in \mathbb {N} ,\\\varphi (m),&m=2k-1,\;k\in \mathbb {N} .\end{cases}}}$
• ${\displaystyle \varphi (M)\cdot \varphi (d)=\varphi (m)\cdot \varphi (n),}$ где ${\displaystyle M}$ — наименьшее общее кратное ${\displaystyle m}$ и ${\displaystyle n}$, а ${\displaystyle d}$ — их наибольший общий делитель.

Теорема Эйлера

Наиболее часто на практике используется свойство, установленное Эйлером:

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}},}$

если ${\displaystyle a}$ и ${\displaystyle m}$ взаимно просты.
Это свойство, которое называют теоремой Эйлера, вытекает из Теоремы Лагранжа и того факта, что ${\displaystyle \varphi (m)}$ равна порядку мультипликативной группы обратимых элементов кольца вычетов по модулю ${\displaystyle m}$.
В качестве следствия теоремы Эйлера можно получить малую теорему Ферма. Для этого нужно взять не произвольное ${\displaystyle m,}$ а простое. Тогда:

${\displaystyle a^{m-1}\equiv 1{\pmod {m}}.}$

Последняя формула находит применение в различных тестах простоты.

Другие свойства

Исходя из представимости ${\displaystyle \varphi (n)}$ произведением Эйлера, несложно получить следующее полезное утверждение:

${\displaystyle a\mid b\Rightarrow \varphi (a)\mid \varphi (b).}$

Следующее равенство является следствием ^[англ.]:

${\displaystyle \varphi (a^{n}+b^{n})\equiv 0{\pmod {n}},\;a>b\geqslant 1.}$

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

${\displaystyle \sum _{d\mid n}\varphi (d)=n.}$

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

${\displaystyle \sum _{1\leqslant k\leqslant n \atop (k,\;n)=1}k={\frac {1}{2}}n\varphi (n),\;n>1.}$

Множество значений

Исследование структуры множества значений функции Эйлера является отдельной сложной задачей. Здесь представлены лишь некоторые результаты, полученные в этой области.

• Функция Эйлера ${\displaystyle \varphi (n)}$ принимает только чётные значения при ${\displaystyle n>2.}$ Причём, если ${\displaystyle n}$ имеет ${\displaystyle r}$ различных нечётных простых делителей, то ${\displaystyle 2^{r}\mid \varphi (n).}$

Доказательство (функция Эйлера принимает только чётные значения при n > 2)

Действительно, если ${\displaystyle p}$ — простое нечётное и ${\displaystyle \alpha >1,}$ то

${\displaystyle p^{\alpha -1}(p-1)}$ — чётное.

Из равенства

${\displaystyle \varphi (n)=\prod _{i=1}^{k}p_{i}^{\alpha _{i}-1}(p_{i}-1)}$

следует утверждение.

В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции. Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду следующее.

1. Значения функции Эйлера повторяются (например, ${\displaystyle \varphi (1)=\varphi (2)=1}$), следовательно обратная функция является многозначной.
2. Функция Эйлера принимает лишь чётные значения при ${\displaystyle n>2,}$ то есть ${\displaystyle \varphi ^{-1}(m)=\varnothing ,}$ если ${\displaystyle m}$ нечётно и ${\displaystyle m\neq 1.}$

В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза ${\displaystyle \varphi }$ является следующая теорема.

• Пусть ${\displaystyle m}$ — чётное, положим

  ${\displaystyle A(m)=m\prod _{p-1\mid m}{\frac {p}{p-1}},}$ где ${\displaystyle p}$ — простое.

Если ${\displaystyle n\in \varphi ^{-1}(m),}$ то ${\displaystyle m<n\leqslant A(m).}$

Доказательство теоремы

Очевидно, если ${\displaystyle \varphi (n)=m,}$ то ${\displaystyle m<n.}$ С другой стороны, если ${\displaystyle \varphi (n)=m}$ и ${\displaystyle n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s}},}$ то

${\displaystyle m=n\prod _{i=1}^{s}{\frac {p_{i}-1}{p_{i}}}\;\Rightarrow \;n=m\prod _{i=1}^{s}{\frac {p_{i}}{p_{i}-1}}.}$

Однако, если ${\displaystyle p\mid n,}$ то ${\displaystyle p-1\mid \varphi (n).}$ Поэтому

${\displaystyle \forall p_{i}:\;p_{i}-1\mid m.}$

Следовательно ${\displaystyle n\leqslant A(m).}$

Эта теорема показывает, что прообраз элемента ${\displaystyle m\in \mathbb {N} }$ всегда представляет собой конечное множество. Также она даёт следующий практический способ нахождения прообраза:

1) вычислить ${\displaystyle A(m)}$;

2) вычислить ${\displaystyle \varphi (n)}$ для всех ${\displaystyle n}$ из полуинтервала ${\displaystyle (m,\,A(m)]}$;

3) все числа ${\displaystyle n,}$ для которых ${\displaystyle \varphi (n)=m,}$ образуют прообраз элемента ${\displaystyle m}$.

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

Пример 1 (Вычисление прообраза)

Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 — простые числа. Вычисляем

${\displaystyle A(4)=4\cdot {\frac {2}{1}}\cdot {\frac {3}{2}}\cdot {\frac {5}{4}}=15.}$

Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:

${\displaystyle \varphi ^{-1}(4)=\{5,\;8,\;10,\;12\}.}$

Пример 2 (Не все чётные числа являются значениями функции Эйлера)

Не существует, например, такого числа ${\displaystyle m,}$ что ${\displaystyle \varphi (m)=14.}$ То есть:

${\displaystyle \varphi ^{-1}(14)=\varnothing .}$

В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа — простые. Поэтому

${\displaystyle A(14)=14\cdot {\frac {2}{1}}\cdot {\frac {3}{2}}=42.}$

Перебрав все числа от 15 до 42, несложно убедиться, что

${\displaystyle \varphi (n)\neq 14,\;n\in (15,\,42].}$

Асимптотические соотношения

Простейшие неравенства

• Оценка снизу значений функции Эйлера:

  ${\displaystyle \varphi (n)\geqslant {\sqrt {n}},}$

для всех ${\displaystyle n,}$ кроме ${\displaystyle n=2}$ и ${\displaystyle n=6.}$

• Оценка сверху для составных ${\displaystyle n}$:

  ${\displaystyle \varphi (n)\leqslant n-{\sqrt {n}},}$

для всякого составного ${\displaystyle n.}$

• Для всех натуральных значений ${\displaystyle n\geqslant 3}$ справедливо двойное неравенство:

  ${\displaystyle {\frac {\log 2}{2}}\cdot {\frac {n}{\log {n}}}<\varphi (n)<n.}$

Сравнение φ(n) с n

• Верхняя грань отношения ${\displaystyle \varphi (n)/n}$ приближается к единице с ростом ${\displaystyle n}$:

  ${\displaystyle \varlimsup {\frac {\varphi (n)}{n}}=1.}$

• В то же время отношение ${\displaystyle \varphi (n)/n^{1-\delta }}$ может быть сколь угодно большим:

  ${\displaystyle \forall \delta >0\colon {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}$

Отношение последовательных значений

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

  ${\displaystyle \lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}=0}$ и ${\displaystyle \lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}=\infty .}$

• Формулы, приведенные выше, получил Somayajulu в 1950 году. А четырьмя годами позже Шинцель и Серпинский доказали, что множество

${\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,\;2,\;\ldots \right\}}$

плотно в множестве действительных положительных чисел.

• В том же году они установили, что множество

${\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,\;2,\;\ldots \right\}}$

плотно на интервале ${\displaystyle (0,\;1).}$

Асимптотики для сумм

• Точное выражение для суммы последовательных значений функции Эйлера:

  ${\displaystyle \sum _{n\leqslant x}\varphi (n)={\frac {3}{\pi ^{2}}}x^{2}+O(x\ln x).}$

Отсюда вытекает, что ^[англ.] функции Эйлера равно ${\displaystyle 6n/\pi ^{2}}$. Этот результат интересен тем, что позволяет получить вероятность события, состоящего в том, что два наугад выбранных натуральных числа являются взаимно простыми. А именно, эта вероятность равна ${\displaystyle 6/\pi ^{2}}$.

• С учётом приведённого выше выражения, можно получить следующие асимптотические оценки:

  ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}=O(n)}$;

  ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}=O(\ln n)}$.

• Используя мультипликативность функции Эйлера и свойства суммы делителей ${\displaystyle \sigma (n)}$, несложно установить, что

  ${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,\;n>1}$.

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

• В 1909 году Ландау получил равенство:

  ${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma },}$

где ${\displaystyle \gamma }$ — постоянная Эйлера — Маскерони.

• Этот результат можно уточнить. В 1962 году была получена оценка снизу для функции Эйлера:

  ${\displaystyle \varphi (n)\geqslant {\frac {n}{e^{\gamma }\log \log n+{\frac {2{,}5}{\log \log n}}}},}$

для всех ${\displaystyle n\geqslant 3}$, с одним исключением ${\displaystyle n=2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23;}$ в указанном случае следует заменить ${\displaystyle 2{,}5}$ на ${\displaystyle 2{,}50637.}$ Это одна из наиболее точных оценок снизу для ${\displaystyle \varphi (n)}$.

• В качестве оценки сверху был установлен следующий факт: существует бесконечно много натуральных ${\displaystyle n}$ таких, что

  ${\displaystyle \varphi (n)<e^{-\gamma }{\frac {n}{\log \log n}}.}$

Как отмечает ^[англ.] по поводу доказательства этого неравенства: «Способ доказательства интересен тем, что неравенство сначала устанавливается в предположении, что гипотеза Римана верна, а затем в предположении, что она не верна».

Связь с другими функциями

Функция Мёбиуса

• Следующую формулу можно использовать для вычисления ${\displaystyle \varphi (n)}$:

  ${\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right),}$

где ${\displaystyle \mu (m)}$ — функция Мёбиуса.

• Другие соотношения с функцией Мёбиуса:

  ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right);}$

  ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ;}$

  ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$.

Ряд Дирихле

• Ряд Дирихле с коэффициентами ${\displaystyle \varphi (n)}$ можно представить через дзета-функцию Римана:

  ${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}},\;s>2.}$

Ряд Ламберта

• Сумма ряда Ламберта с коэффициентами ${\displaystyle \varphi (n)}$:

  ${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}},\;|q|<1.}$

Наибольший общий делитель

• Функция Эйлера является дискретным преобразованием Фурье наибольшего общего делителя:

  ${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)e^{{-2\pi i}{\tfrac {k}{n}}}.}$

Действительная часть:

${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)\cos {2\pi {\frac {k}{n}}}.}$

В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей ${\displaystyle n.}$

Связь с латинскими квадратами

• Число циклических латинских квадратов порядка ${\displaystyle N}$ с фиксированной первой строкой определяется функцией Эйлера ${\displaystyle \varphi (N)}$. Данную особенность можно использовать при вычислении значения функции Эйлера путем подсчета соответствующего числа квадратов заданного порядка ${\displaystyle N}$ используя алгоритм без умножений и делений, однако асимптотически это медленнее, чем расчет на базе факторизации аргумента ${\displaystyle N}$. Циклические диагональные латинские квадраты являются подмножеством циклических латинских квадратов, поэтому число циклических диагональных латинских квадратов с фиксированной первой строкой (последовательность A123565 в OEIS) является ограничением снизу на значение функции Эйлера ${\displaystyle \varphi (N)}$.

Приложения и примеры

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

На основе алгоритма, предложенного в 1978 году Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом, была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов — система RSA. Криптостойкость этой системы определяется сложностью разложения на сомножители целого ${\displaystyle n}$-разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом.

На этапе создания пары из секретного и открытого ключей вычисляется

${\displaystyle \varphi (n)=\varphi (p\cdot q)=(p-1)\cdot (q-1),}$

где ${\displaystyle p}$ и ${\displaystyle q}$ — простые. Затем выбираются случайные числа ${\displaystyle d,\ e}$ так, чтобы

${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$

Затем сообщение шифруется открытым ключом адресата:

${\displaystyle c=m^{e}\;{\bmod {\;}}n.}$

После этого расшифровать сообщение может только обладатель секретного ключа ${\displaystyle d}$:

${\displaystyle m=c^{d}\;{\bmod {\;}}n.}$

Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.

Доказательство корректности расшифрования

В силу выбора чисел на этапе создания ключей

${\displaystyle e\cdot d=1+a\cdot \varphi (n).}$

Если ${\displaystyle (m,\,n)=1,}$ то, с учетом теоремы Эйлера,

${\displaystyle c^{d}=m^{ed}=m^{1}m^{a\varphi (n)}=m\cdot 1^{a}=m\;{\bmod {\;}}n.}$

В общем случае ${\displaystyle m}$ и ${\displaystyle n}$ могут иметь общие делители, но расшифрование всё равно оказывается верным. Пусть ${\displaystyle m=0\;{\bmod {\;}}p.}$ По китайской теореме об остатках:

${\displaystyle m=c^{d}\;{\bmod {\;}}n\;\Leftrightarrow \;{\begin{cases}m=c^{d}\;{\bmod {\;}}p,\\m=c^{d}\;{\bmod {\;}}q.\end{cases}}}$

Подставляя ${\displaystyle c=m^{e},}$ получаем тождество

${\displaystyle {\begin{cases}m^{ed}=0=m\;{\bmod {\;}}p,\\m^{ed}=m(m^{q-1})^{a(p-1)}=m\cdot 1^{a(p-1)}=m\;{\bmod {\;}}q.\end{cases}}}$

Следовательно,

${\displaystyle m^{ed}=m\;{\bmod {\;}}pq.}$

Вычисление обратного элемента

Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю ${\displaystyle n}$, а именно:

${\displaystyle a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}},}$ если ${\displaystyle (a,\,n)=1.}$

Эта формула следует из теоремы Эйлера:

${\displaystyle 1=(a\cdot {}^{}}$