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

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

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

Функция Эйлера φ(n) — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и φ(1) = 1.^[1]

Например, для числа 24 существует 8 взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому φ(24) = 8.

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

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

Вычисление

Общие сведения Функция Эйлера $\varphi(n)$ показывает, сколько натуральных чисел из отрезка $[1,n-1]$ имеют c $n$ только один общий делитель - единицу. Функция Эйлера определена на множестве натуральных чисел, и значения ее лежат в множестве натуральных чисел. Как следует из определения, чтобы вычислить $\varphi(n),$ нужно перебрать все числа от $1$ до $n-1$ и для каждого проверить, имеет ли оно общие делители с $n,$ а затем подсчитать, сколько чисел оказались взаимно простыми с $n.$ Эта процедура весьма трудоемка, поэтому для вычисления $\varphi(n)$ используют другие методы, которые основываются на специфических свойствах функции Эйлера. В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение $\varphi(n)$ не превосходит $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$ - простое. Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.

Первые 99 значений функции Эйлера (последовательность A000010 в OEIS) $\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

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

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

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

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

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

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

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

$a_1'm+a_1m' \equiv a_2'm+a_2m' \pmod{mm'},$

тогда

$a_1m' \equiv a_2m' \pmod m,$

поэтому

$a_1 \equiv a_2 \pmod m;$

аналогично

$a_1' \equiv a_2' \pmod m'.$

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

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

Теорема 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$ значение функции Эйлера задается явной формулой:^[7]

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

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

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

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

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

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

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

$\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{align} \varphi(n) &= \varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \cdots\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) \cdots p_k^{\alpha_k} \left(1- \frac{1}{p_k} \right)\\ &= p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} \left(1- \frac{1}{p_1} \right) \left(1- \frac{1}{p_2} \right) \cdots \left(1- \frac{1}{p_k} \right)\\ &=n \left(1- \frac{1}{p_1} \right)\left(1- \frac{1}{p_2} \right) \cdots\left(1- \frac{1}{p_k} \right). \end{align}$

Свойства

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

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

$\varphi(mn)=\varphi(m)\varphi(n) \;\;\; \forall m, n \in \N: \;\; (m,n)=1.$

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

$\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) \not = 1$ и $(n',d) \not = 1.$ Поэтому можно записать:

$d = d_1^{\delta_1} \cdots d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdots d_{K}^{\delta_{K}},$

$m' = d_1^{\alpha_1} \cdots d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdots p_r^{\beta_r},$

$n' = d_{k+1}^{\gamma_{k+1}} \cdots d_{K}^{\gamma_{K}} \cdot q_1^{\epsilon_1} \cdots q_s^{\epsilon_s}.$

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

$\varphi(mn) = \varphi(d^2 \cdot m'n') = \varphi((d_1^{\delta_1} \cdots d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdots d_{K}^{\delta_{K}})^2 \cdot d_1^{\alpha_1} \cdots d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdots p_r^{\beta_r} \cdot d_{k+1}^{\gamma_{k+1}} \cdots d_{K}^{\gamma_{K}} \cdot q_1^{\epsilon_1} \cdots q_s^{\epsilon_s}).$

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

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

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

$\begin{align} \varphi(mn) &= d_1^{\alpha_1+\delta_1}(1-\frac{1}{d_1}) \cdots d_k^{\alpha_k+\delta_k}(1-\frac{1}{d_k}) \cdot p_1^{\beta_1}(1-\frac{1}{p_1}) \cdots p_r^{\beta_r}(1-\frac{1}{p_r}) \cdot d_{k+1}^{\delta_{k+1}}(1-\frac{1}{d_{k+1}}) \cdots d_{K}^{\delta_{K}}(1-\frac{1}{d_{K}})\\ &\; \cdot \; d_{k+1}^{\gamma_{k+1}+\delta_{k+1}}(1-\frac{1}{d_{k+1}}) \cdots d_{K}^{\gamma_{K}+\delta_{K}}(1-\frac{1}{d_{K}}) \cdot q_1^{\epsilon_1}(1-\frac{1}{q_1}) \cdots q_s^{\epsilon_s}(1-\frac{1}{q_s}) \cdot d_1^{\delta_1}(1-\frac{1}{d_1}) \cdots d_{k+1}^{\delta_{k+1}}(1-\frac{1}{d_{k+1}})\\ &\; \cdot \; \frac{1}{(1-\frac{1}{d_1}) \cdots (1-\frac{1}{d_K})}. \end{align}$

В первой строке записано $\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), &\text{ m = 2k }, k \in \N, \\ \varphi(m), &\text{ m = 2k - 1}, k \in \N. \end{cases}$
• $\varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n),$ где $M$ наименьшее общее кратное $m$ и $n.$

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

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

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

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

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

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

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

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

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

Следующее равенство^[9][10] является следствием теоремы Зигмонди (англ.)

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

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

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

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

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

• Функция Эйлера $\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) = \empty,$ если $m$ нечётно и $m \not = 1.$

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

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

  $A(m) = m \prod_{p-1|m}\frac{p}{p-1},$   где $p$ - простое.

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

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

Очевидно, если $\varphi(n) = m,$ то $m < n.$ С другой стороны, если $\varphi(n) = m$   и   $n = p_1^{\alpha_1} \cdots 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|n,$ то $p-1|\varphi(n).$ Поэтому

$\forall p_i: \; p_i-1|m.$

Следовательно $n \leq 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) = \empty.$

В самом деле, делители 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) \not = 14, \; n \in (15, 42].$

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

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

• Оценка снизу значений функции Эйлера:^[14][15]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  $\varphi(n) \ge e^{-\gamma} \frac {n} {\log \log n + (5/2 \; e^{\gamma} \log \log n)},$

для всех $n \ge 3$, с одним исключением $n = 2\times3\times5\times7\times11\times13\times17\times19\times23;$ в указанном случае следует заменить $5/2$ на $2.50637.$ Это одна из наиболее точных оценок снизу для $\varphi(n).$^[26]

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

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

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

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

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

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

  $\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)}.$ ^[29]

Ряд Дирихле

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

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

Ряд Ламберта

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

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

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

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

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

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

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

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

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

$\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$, а именно:^[34]

$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 (Оценка сложности вычисления)  

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

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

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

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

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

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

Решение задается формулой ^[35]

$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) \not = 1$, сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение

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

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

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

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

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

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

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

Пример 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)$ классов вычетов.^[39]
Пример. Приведённая система вычетов по модулю 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$ — натуральное,^[40] — то существует $\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$ - простое, либо оно является произведением семи или более различных простых чисел.^[41] Позже были доказаны и другие сильные утверждения. Так в 1980 году Cohen и Hagis показали, что если $n$ составное и $\varphi(n)$ делит $n-1,$ то $n > 10^{20}$ и $\omega(n) \ge 14,$ где $\omega(n)$ - количество простых делителей. В 1970 году Lieuwens установил, что если $3\;|\;n,$ то $\omega(n) \ge 213$ и $n > 5.5 \times 10^{570}.$ Wall в 1980 году доказал, что если $30\;|\;n,$ то $\omega(n) \ge 26.$^[42]

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

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

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

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

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

Иначе это утверждение можно сформулировать так:^[44]

Не существует натурального числа $m$ такого, что $\dim(\varphi^{-1}(m)) = 1.$

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

Стоит отметить, что в 1999 Форд доказал следующую теорему:^[45]

$\forall k \ge 2 \;\exist m: \dim(\varphi^{-1}(m)) = k.$

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

См. также

• Список объектов, названных в честь Леонарда Эйлера
• Теория чисел
• Функция Мёбиуса
• Символ Лежандра
• Символ Якоби
• Критерий Эйлера

Примечания

1. ↑ Ribenboim, 1996, p. 34
2. ↑ Sandifer, 2007, p. 203
3. ↑ Габидулин, 2011, Системы RSA
4. ↑ Burton, 2007, Theorem 7.2, p. 133
5. ↑ Hardy, 1975, Theorem 59, p. 52
6. ↑ Hardy, 1975, Theorem 60, p. 53
7. ↑ ^{1 2 3} Сагалович, 2007, Вычисление функции Эйлера, p. 35-36
8. ↑ Burton, 2007, Euler's Phi-Function, p. 136
9. ↑ Weisstein, MathWorld, Totient Function
10. ↑ Ruiz, S., A Congruence With the Euler Totient Function, 2004
11. ↑ Виноградов, 1952, Функция Эйлера
12. ↑ Информация в этом разделе основана на статье: Coleman, Some remarks on Euler’s totient function
13. ↑ Gupta H., 1981
14. ↑ ^{1 2 3} Handbok, 2005, Elementary inequalities for φ
15. ↑ Kendall and Osborn 1965
16. ↑ Sierpiński and Schinzel 1988
17. ↑ Hardy, 1975, Theorem 326, p. 267
18. ↑ Hardy, 1975, Theorem 327, p. 267
19. ↑ ^{1 2 3} Ribenboim, 1996, Values of Euler's Function, p. 38
20. ↑ Hardy, 1975, Theorem 330, p. 268
21. ↑ Hardy, 1975, Theorem 332, p. 269
22. ↑ Hardy, 1975, Theorem 329, p. 267
23. ↑ Handbok, 2005, On the function n/φ(n)
24. ↑ Hardy, 1975, Theorem 328, p. 267
25. ↑ Rosser and Schoenfeld, 1962
26. ↑ ^{1 2} Ribenboim, 1996, Distribution of Values of Euler's Function, p. 320
27. ↑ Nicolas, 1983
28. ↑ Виноградов, 1952, с. 29-31
29. ↑ Rosica Dineva, The Euler Totient, the Möbius, and the Divisor Functions
30. ↑ Hardy, 1975, Theorem 288, p. 250
31. ↑ Hardy, 1975, Theorem 309, p. 258
32. ↑ Schramm, 2008
33. ↑ Габидулин, 2011, Система шифрования RSA, с. 96
34. ↑ Алфёров, 2002, p. 462-463
35. ↑ ^{1 2} Schneier, 1995, The Euler Totient Function
36. ↑ Габидулин, 2011, Нахождение мультипликативного обратного по модулю, с. 233
37. ↑ Schneier, 1995, Number Theory
38. ↑ Сагалович, 2007, с. 36
39. ↑ Сагалович, 2007, Приведенная система вычетов
40. ↑ Виноградов, 1952, с. 106
41. ↑ ^{1 2} Lehmer, 1932
42. ↑ Ribenboim, 1996, p. 36-37
43. ↑ ^{1 2} Ribenboim, 1996, p. 39-40
44. ↑ ^{1 2} Coleman, Some remarks on Euler’s totient function
45. ↑ Ford, 1999

Литература

• 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
• Сагалович Ю. Л. Введение в алгебраические коды. — 2-е изд.. — М.: МФТИ, 2007. — 260 с. — ISBN 5-7417-0191-4
• 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

Ссылки

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

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.