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

Статья на основе материалов из Википедии

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

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

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

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

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

Вычисление

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

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

Как следует из определения, чтобы вычислить `\varphi(n)` , нужно перебрать все числа от `1` до `n-1` , и для каждого проверить, имеет ли оно общие делители с `n` , а затем подсчитать, сколько чисел оказались взаимно простыми с `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`  — простое.

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

a000010 -->) `\varphi(n)` +0+1+2+3+4+5+6+7+8+9
0+112242646
10+41041268816618
20+812102282012181228
30+8301620162412361824
40+16401242202422461642
50+20322452184024362858
60+16603036324820663244
70+24702472364036602478
80+32544082246442564088
90+24724460467232964260

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

Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел `m` и `n` `\varphi(mn)=\varphi(m)\varphi(n).` {{Hider| title = Доказательство мультипликативности| content =

Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема. : Теорема 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'` .

Теперь можно доказать основное утверждение. : Теорема 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').`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Для простого `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}-1)p.` Всего таких чисел `p^{n-1}-1` . Поэтому количество чисел, взаимно простых с `p^n` , равно `p^n-1-(p^{n-1}-1)=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` на простые сомножители.

{{Hider| title = Доказательство| content =

Как следует из основной теоремы арифметики, всякое натуральное число `n>1` единственным образом представляется в виде: `n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k},` где `p_1<\ldots

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

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

Свойства

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

Функция Эйлера является мультипликативной арифметической функцией, то есть `\varphi(mn)=\varphi(m)\varphi(n) \;\;\; \forall m,\, n \in \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.` Это свойство является естественным обобщением мультипликативности. {{Hider| title = Доказательство обобщённой мультипликативности| content =

Пусть `(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{align} \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{align} В первой строке записано `\varphi(m),` во второй — `\varphi(n),` а третью можно представить, как `d/\varphi(d).` Поэтому: `\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }} Некоторые частные случаи:

  • `\;\varphi\left(n^m\right) = n^{m-1}\varphi(n).`
\varphi(2m) = \begin{cases} 2\varphi(m), & m = 2k,\; k \in \N, \\ \varphi(m), & m = 2k - 1,\; k \in \N. \end{cases}

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

Наиболее часто на практике используется свойство, установленное Эйлером: `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).` Следующее равенство[3][4] является следствием : `\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.`

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

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

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

:Действительно, если `p` — простое нечётное и `\alpha > 1,` то `p^{\alpha - 1}(p - 1)` — чётное. :Из равенства `\varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i - 1}(p_i - 1)` :следует утверждение.

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }} В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции. Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду следующее.

  1. Значения функции Эйлера повторяются (например, `\varphi(1) = \varphi(2) = 1` ), следовательно обратная функция является многозначной.
  2. Функция Эйлера принимает лишь чётные значения при `n > 2,` то есть `\varphi^{-1}(m) = \varnothing,` если `m` нечётно и `m \neq 1.`
В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза `\varphi` является следующая теорема[6].
  • Пусть `m`  — чётное, положим
  • `A(m) = m \prod_{p-1\mid m}\frac{p}{p-1},` где `p`  — простое.
: Если `n \in \varphi^{-1}(m),` то `m < n \leqslant A(m).` {{Hider| title = Доказательство теоремы| content =

:Очевидно, если `\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).`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }} Эта теорема показывает, что прообраз элемента `m \in \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` раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.

{{Hider| title = Пример 1 (Вычисление прообраза)| content =

Найдем прообраз 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\}.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Не существует, например, такого числа `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].`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

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

  • Оценка снизу значений функции Эйлера[7]:
  • ` \varphi(n) \geqslant \sqrt{n},`
: для всех `n,` кроме `n = 2` и `n = 6.`
  • Оценка сверху для составных `n` [8]:
  • `\varphi(n) \leqslant n - \sqrt{n},`
: для всякого составного `n.`
  • Для всех натуральных значений `n \geqslant 3` справедливо двойное неравенство:
  • `\frac{\log2}{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 году была получена оценка снизу для функции Эйлера[9]:
  • `\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)` .
  • В качестве оценки сверху был установлен следующий факт[10]: существует бесконечно много натуральных `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)}` [11].

Ряд Дирихле

Ряд Ламберта

  • Сумма ряда Ламберта с коэффициентами `\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) \cos {2\pi\frac{k}{n}}.` : В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей `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.` Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках. {{Hider| title = Доказательство корректности расшифрования| content =

В силу выбора чисел на этапе создания ключей `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.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю `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.`

{{Hider| title = Пример (Вычисление обратного элемента)| content =

Найдем `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.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

{{Hider| title = Замечание 1 (Оценка сложности вычисления)| content =

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

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Если `(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 \N_0, x \in \N;` или, перегруппировав слагаемые, `a' \cdot x - n' \cdot t = \frac{1}{d}.` Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью `d = 1,` что противоречит предположению.

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Метод вычисления обратного элемента можно использовать для решения сравнения `a \cdot x \equiv b \pmod n.` Решение задаётся формулой: `x \equiv b \cdot a^{\varphi(n)-1} \pmod n,` если `(a,\,n) = 1.`

{{Hider| title = Пример (Решение линейного сравнения)| content =

Рассмотрим сравнение `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.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Если `(a,\,n) \neq 1` , сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение `2 \cdot x \equiv 3 \pmod 4` не имеет решения на множестве натуральных чисел. В то же время сравнение `4 \cdot x \equiv 6 \pmod {22}` имеет два решения `x = 7, \; x = 18.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

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

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

Найдем последние три цифры в десятичной записи числа `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.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

{{Hider| title = Пример 2 (Остаток от деления на 1001)| content =

Найдем остаток от деления `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}.`

|frame-style = border: 1px solid rgb(200,200,200); | title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;| content-style = color: black; background-color: white; text-align: left; | hidden=1 }}

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

Мультипликативная группа кольца вычетов по модулю `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` ).
Пример. Группа `\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`  — простое, либо оно является произведением семи или более различных простых чисел[1]. Позже были доказаны и другие сильные утверждения. Так, в 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, 1, 2, 2, 4, 2, 6, 4, 6, 4}, бросается в глаза, что среди них много повторяющихся. Гипотеза Кармайкла состоит в том, что нет такого значения `m` , которое функция Эйлера принимала бы только один раз.

В 1907 году Кармайкл предложил как упражнение доказать следующее утверждение: : Если `n`  — натуральное число, то существует натуральное число `m \neq n` такое, что `\varphi(n)=\varphi(m).` Иначе это утверждение можно сформулировать так[2]: не существует натурального числа `m` такого, что `\dim(\varphi^{-1}(m)) = 1.`

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

Стоит отметить, что в 1999 Форд доказал следующую теорему[13]: `\forall k \geqslant 2 \;\exist m\colon \dim(\varphi^{-1}(m)) = k.` Это означает, что, задавшись некоторым числом `k \geqslant 2,` можно найти среди множества значений функции Эйлера такое значение `m,` что оно принимается ровно `k` раз. Однако, доказать, что нет такого значения, которое функция Эйлера принимала бы только один раз, до сих пор никому не удалось[2].

См. также

Примечания

  1. Lehmer, 1932
  2. Coleman, Some remarks on Euler’s totient function
  3. Weisstein, MathWorld, Totient Function
  4. Ruiz, S., A Congruence With the Euler Totient Function, 2004
  5. Информация в этом разделе основана на статье: Coleman, Some remarks on Euler’s totient function
  6. Gupta H., 1981
  7. Kendall and Osborn 1965
  8. Sierpiński and Schinzel 1988
  9. (Theorem 15)
  10. Nicolas, 1983
  11. Rosica Dineva, The Euler Totient, the Möbius, and the Divisor Functions
  12. Schramm, 2008
  13. Ford, 1999

Литература

    Ссылки

    I am not robot