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

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

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

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

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

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

Вычисление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p}),n>1,$

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

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

$\phi (36)=\phi (2^2\cdot 3^2)=\phi (2^2)\phi (3^2)=(2^2-2)(3^2-3)=2\cdot 6=12.$

$\phi (36)=\phi (2^2\cdot 3^2)=36\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})=36\cdot \frac{1}{2}\cdot \frac{2}{3}=36\cdot \frac{1}{3}=12$

Свойства

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

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

$\phi (mn)=\phi (m)\phi (n)\mathrm{\forall }m,n\in \mathbb{N}:(m,n)=1.$

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

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

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

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

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

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

$a^{\phi (m)}\equiv 1(\mathrm{mod}m),$

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

$a^{m-1}\equiv 1(\mathrm{mod}m).$

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

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

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

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

Следующее равенство является следствием Шаблон:Iw:

$\phi (a^n+b^n)\equiv 0(\mathrm{mod}n),a>b⩾1.$

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

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

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

$\sum _{\genfrac{}{}{0ex}{}{1⩽k⩽n}{(k,n)=1}}k=\frac{1}{2}n\phi (n),n>1.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  $\phi (n)⩾\sqrt{n},$

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

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

  $\phi (n)⩽n-\sqrt{n},$

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

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

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

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

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

  $\bar{\lim }\frac{\phi (n)}{n}=1.$

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

  $\mathrm{\forall }\delta >0:\frac{\phi (n)}{n^{1-\delta }}\to \mathrm{\infty }.$

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

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

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

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

$\{\frac{\phi (n+1)}{\phi (n)},n=1,2,\dots \}$

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

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

$\{\frac{\phi (n)}{n},n=1,2,\dots \}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ряд Дирихле

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

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

Ряд Ламберта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$d\cdot e=1mod\phi (n).$

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

$c=m^{e}modn.$

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

$m=c^{d}modn.$

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

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

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

$a^{-1}\equiv a^{\phi (n)-1}(\mathrm{mod}n),$ если $(a,n)=1.$

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

$1=(a\cdot a^{-1})\cdot a^{\phi (n)}modn=a\cdot (a^{-1}\cdot a^{\phi (n)})modn=a\cdot a^{\phi (n)-1}modn.$

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

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

$a\cdot x\equiv b(\mathrm{mod}n).$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\mathrm{\forall }k⩾2\mathrm{\exists }m:\dim ({\phi }^{-1}(m))=k.$

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Source
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Арнольд В. И., Группы Эйлера и арифметика геометрических прогрессий (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