Функция Эйлера (Srutenx |wlyjg)

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

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

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

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

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

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

Вычисление

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

$\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

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

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

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

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

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

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

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

$\varphi (mn)=\varphi (m)\varphi (n).$

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

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

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

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

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

тогда

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

поэтому

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

аналогично

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

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

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

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

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

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

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

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

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

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

$\varphi (mm')=\varphi (m)\varphi (m').$

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

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

$\varphi (p)=p-1,$

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

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

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

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

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

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

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

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

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

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

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

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

Используя мультипликативность функции Эйлера и выражение для $\varphi (p^{k})$, получаем: ${\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}}$

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

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

$\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$

Свойства

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

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

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

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

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

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

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

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

$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}},$

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

$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}}.$

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

$\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}}).$

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

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

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

$a\mid b\Rightarrow \varphi (a)\mid \varphi (b).$

Следующее равенство является следствием теоремы Зигмонди:

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

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

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

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

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

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

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

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

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

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

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

Из равенства

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

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

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

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

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

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

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

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

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

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

$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}}.$

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

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

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

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

1) вычислить $A(m)$;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для всякого составного $n.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  $\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);$

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

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

Ряд Дирихле

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

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

Ряд Ламберта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$d\cdot e=1\;{\bmod {\;}}\varphi (n).$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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}}$

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

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

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

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

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

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

$1=(a\cdot a^{-1})\cdot a^{\varphi (n)}\;{\bmod {\;}}n=a\cdot (a^{-1}\cdot a^{\varphi (n)})\;{\bmod {\;}}n=a\cdot a^{\varphi (n)-1}\;{\bmod {\;}}n.$

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

Найдем $5^{-1}\;{\bmod {\;}}7$, то есть такое число $x$, что

$5\cdot x\equiv 1{\pmod {7}}.$

Очевидно, $5$ и $7$ не имеют общих делителей кроме единицы, $(5,7)=1$, при этом число $7$ простое и

$\varphi (7)=7-1=6,$

поэтому удобно воспользоваться формулой, приведенной выше:

$5^{6-1}\;{\bmod {\;}}7=5^{5}\;{\bmod {\;}}7=25\cdot 25\cdot 5\;{\bmod {\;}}7=(-3)\cdot (-3)\cdot 5\;{\bmod {\;}}7=9\cdot 5\;{\bmod {\;}}7=2\cdot 5\;{\bmod {\;}}7=3.$

Легко проверить, что в самом деле

$5\cdot 3\equiv 1{\pmod {7}}.$

Замечание 1 (Оценка сложности вычисления)

В общем случае для вычисления обратных значений алгоритм Евклида быстрее, чем использование теоремы Эйлера, так как битовая сложность вычисления по алгоритму Евклида имеет порядок $O(k^{2}),$ в то время как вычисление по теореме Эйлера требует порядка $O(k^{3})$ битовых операций, где $k=\lceil \log _{2}{n}\rceil .$ Однако, в случае, когда известно разложение $\varphi (n)-1$ на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм «возводи в квадрат и перемножай».

Замечание 2 (Отсутствие решения в случае (a, n) ≠ 1)

Если $(a,\,n)\neq 1,$ то обратного к $a$ элемента не существует, или, иначе говоря, уравнение

$a\cdot x\equiv 1{\pmod {n}}$

не имеет решения на множестве натуральных чисел.
Доказательство. В самом деле, допустим

$(a,\,n)=d>1,$

и решение существует. Тогда по определению наибольшего общего делителя

$a=d\cdot a',\ n=d\cdot n',$ причем $(a',\,n')=1;$

поэтому можно записать:

$d\cdot a'\cdot x=d\cdot n'\cdot t+1,$ где $t\in \mathbb {N} _{0},x\in \mathbb {N} ;$

или, перегруппировав слагаемые,

$a'\cdot x-n'\cdot t={\frac {1}{d}}.$

Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью

$d=1,$

что противоречит предположению.

Решение линейного сравнения

Метод вычисления обратного элемента можно использовать для решения сравнения

$a\cdot x\equiv b{\pmod {n}}.$

Решение задаётся формулой:

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

Пример (Решение линейного сравнения)

Рассмотрим сравнение

$7\cdot x\equiv 3{\pmod {9}}.$

Так как $(7,9)=1,$ можно воспользоваться указанной формулой:

$x=3\cdot 7^{\varphi (3^{2})-1}\;{\bmod {\;}}9=3\cdot 7^{3\cdot (3-1)-1}\;{\bmod {\;}}9=3\cdot 7^{5}\;{\bmod {\;}}9=3\cdot 49\cdot 49\cdot 7\;{\bmod {\;}}9=3\cdot 4\cdot 4\cdot 7\;{\bmod {\;}}9=3.$

Подстановкой убеждаемся, что

$7\cdot 3\equiv 3{\pmod {9}}.$

Замечание (Неединственность решения или отсутствие решения в случае (a, n) ≠ 1)

Если $(a,\,n)\neq 1$, сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение

$2\cdot x\equiv 3{\pmod {4}}$

не имеет решения на множестве натуральных чисел. В то же время сравнение

$4\cdot x\equiv 6{\pmod {22}}$

имеет два решения

$x=7,\;x=18.$

Вычисление остатка от деления

Функции Эйлера позволяет вычислять остатки от деления больших чисел.

Пример 1 (Последние три цифры в десятичной записи числа)

Найдем последние три цифры в десятичной записи числа $2^{100}.$ Замечая, что

$\varphi (125)=\varphi (5^{3})=5^{3}-5^{2}=100,$

получаем

$2^{100}\;{\bmod {\;}}125=2^{125-25}\;{\bmod {\;}}125=2^{\varphi (125)}\;{\bmod {\;}}125=1\;{\bmod {\;}}125.$

Переходя теперь от модуля $125$ к модулю $1000,$ имеем:

$2^{100}\equiv 1{\pmod {125}}\equiv 376{\pmod {1000}}.$

Следовательно, десятичная запись числа $2^{100}$ оканчивается на $376.$

Пример 2 (Остаток от деления на 1001)

Найдем остаток от деления $729^{720}$ на $1001.$ Легко видеть, что

$(729,\;1001)=1.$

Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством

$\varphi (p)=p-1,$ для всякого простого $p,$

получаем

$\varphi (1001)=\varphi (7\cdot 11\cdot 13)=\varphi (7)\cdot \varphi (11)\cdot \varphi (13)=6\cdot 10\cdot 12=720.$

По теореме Эйлера

$729^{720}\equiv 1{\pmod {1001}}.$

Нахождение порядка мультипликативной группы кольца вычетов

Мультипликативная группа кольца вычетов по модулю $m$ состоит из $\varphi (m)$ классов вычетов.
Пример. Приведённая система вычетов по модулю 14 состоит из $\varphi (14)=6$ классов вычетов: $[1]_{14},\ [3]_{14},\ [5]_{14},\ [9]_{14},\ [11]_{14},\ [13]_{14}.$

Приложения в теории групп

Число порождающих элементов в конечной циклической группе $G$ равно $\varphi (|G|)$. В частности, если мультипликативная группа кольца вычетов по модулю $m$ является циклической группой — что возможно только при $m=2,\;4,\;p^{n},\;2p^{n}$, где $p$ — простое нечётное, $n$ — натуральное, — то существует $\varphi (\varphi (m))$ генераторов группы (первообразных корней по модулю $m$).
Пример. Группа $\mathbb {Z} _{14}^{\times },$ рассмотренная в примере выше, имеет $\varphi (\varphi (14))=\varphi (6)=2$ генератора: $3$ и $5.$

Нерешенные вопросы

Задача Лемера

Основная статья: Задача Лемера о функции Эйлера

Как известно, если $p$ — простое, то $\varphi (p)=p-1.$ В 1932 году Деррик Лемер задался вопросом, существует ли такое составное число $n$, что $\varphi (n)$ является делителем $n-1$. Лемер рассматривал уравнение:

$k\varphi (n)=n-1,$

где $k$ — целое. Ему удалось доказать, что если $n$ — решение уравнения, то либо $n$ — простое, либо оно является произведением семи или более различных простых чисел. Позже были доказаны и другие сильные утверждения. Так, в 1980 году Cohen и Hagis показали, что если $n$ составное и $\varphi (n)$ делит $n-1,$ то $n>10^{20}$ и $\omega (n)\geqslant 14,$ где $\omega (n)$ — количество простых делителей. В 1970 году Lieuwens установил, что если $3\mid n,$ то $\omega (n)\geqslant 213$ и $n>5{,}5\cdot 10^{570}.$ Wall в 1980 году доказал, что если $30\mid n,$ то $\omega (n)\geqslant 26$.

По сей день неизвестно, существуют ли составные решения задачи Лемера. Если предположить, что их не существует, то получается следующий критерий простоты: $n$ — простое тогда и только тогда, когда $\varphi (n)\mid n-1$.

Гипотеза Кармайкла

Если посмотреть даже на первые десять значений функции Эйлера {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, бросается в глаза, что среди них много повторяющихся. Гипотеза Кармайкла состоит в том, что нет такого значения $m$, которое функция Эйлера принимала бы только один раз.

В 1907 году Кармайкл предложил как упражнение доказать следующее утверждение:

Если $n$ — натуральное число, то существует натуральное число $m\neq n$ такое, что $\varphi (n)=\varphi (m).$

Иначе это утверждение можно сформулировать так: не существует натурального числа $m$ такого, что $\dim(\varphi ^{-1}(m))=1.$

Однако в 1922 году Кармайкл обнаружил, что предложенное им доказательство содержит ошибку. В этом же году он показал, что если $\dim(\varphi ^{-1}(m))=1,$ то $m>10^{37}.$ Позже эта оценка неоднократно улучшалась, и современное значение нижней границы, с которой стоит начинать искать контрпример для гипотезы Кармайкла, есть $m=10^{10^{7}}.$ Это значение получили Schlafly и Wagon в 1994 году, используя метод Klee.

В 1999 году Форд доказал следующую теорему:

$\forall k\geqslant 2\;\exists m\colon \dim(\varphi ^{-1}(m))=k.$

Это означает, что, задавшись некоторым числом $k\geqslant 2,$ можно найти среди множества значений функции Эйлера такое значение $m,$ что оно принимается ровно $k$ раз. Однако, доказать, что нет такого значения, которое функция Эйлера принимала бы только один раз, до сих пор никому не удалось.

См. также

• Список объектов, названных в честь Леонарда Эйлера

Литература

• Charles Sandifer. The early mathematics of Leonhard Euler. — MAA, 2007. — С. 391. — ISBN 0-88385-559-3.
• József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici. Euler's φ-function // Handbook of Number Theory I. — Springer, 2005. — 622 с.
• Виноградов И. М. Основы теории чисел. — 5-е изд. — М.—Л.: Гостехиздат, 1952. — 180 с. — 100 000 экз.
• G. H. Hardy, E. M. Wright. An Introduction to the Theory of Numbers. — fourth edition. — Oxford: Oxford University Press, 1975. — 421 с.
• Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Элементы алгебры и теории чисел // Основы криптографии. — 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — 480 с. — ISBN 5-85438-025-0.
• Bruce Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C. — Australia: John Wiley & Sons, 1995. — ISBN 0-471-12845-7.
• Сагалович Ю. Л. Введение в алгебраические коды — М.: МФТИ, 2007. — 262 с. — ISBN 978-5-7417-0191-1
• Paulo Ribenboim. The New Book of Prime Number Records. — New York: Springer, 1996. — ISBN 0-387-94457-5.
• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. — ISBN 5-7417-0377-9.
• David M. Burton. Elementary Number Theory. — Sixth Edition. — University of New Hampshire: McGraw-Hill, 2007. — 512 с. — ISBN 978-0-07-305188-8.
• Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. — М.: МЦНМО, 2003. — 44 с. — ISBN 5-94057-141-7.

Ссылки

• Арнольд В. И., Группы Эйлера и арифметика геометрических прогрессий (2003)
• Coleman R., Some remarks on Euler’s totient function (2012)
• Dineva R., The Euler Totient, the Möbius, and the Divisor Functions (2005)
• Ford K., The number of solutions of φ(x) = m (1999)
• József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I (2005)
• Gupta H., Euler’s totient function and its inverse (1981)
• Hardy, Wright An Introduction to the Theory of Numbers (2008)
• Lehmer D. H., On Euler’s Totient Function (1932)
• Ruiz S., A Congruence With the Euler Totient Function (2004)
• Schramm, Wolfgang, The Fourier Transform of Functions of the Greatest Common Divisor (2008)
• Weisstein, Eric W. «Totient Function.» From MathWorld — A Wolfram Web Resource. http://mathworld.wolfram.com/TotientFunction.html