Processing math: 32%

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

Функция Эйлера φ(n) — мультипликативнаяарифметическая функция, равная количеству натуральных чисел, меньших nи взаимно простых с ним. При этом полагают по определению, что число 1взаимно просто со всеми натуральными числами, и φ(1)=1.
 Например, для числа 24 существует 8 меньших его и взаимно простых с нимчисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому φ(24)=8.
 Названа в честь Эйлера, который впервые использовал её в 1760 году всвоих работах по теории чисел для доказательства малой теоремы Ферма, азатем и для доказательства более общего утверждения — теоремы Эйлера.Позднее функцию использовал Гаусс в своем труде «Арифметическиеисследования», вышедшем в свет в 1801 году. Гаусс ввёл ставшеестандартным обозначение φ(n).
 Функция Эйлера находит применение в вопросах, касающихся теорииделимости и вычетов (см. сравнение по модулю), теории чисел,криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA.

Вычисление


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


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

φ(mn)=φ(m)φ(n).

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


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

φ(p)=p1,
 которая следует из определения. Действительно, если p — простое, товсе числа, меньшие p, взаимно просты с ним, а их ровно p1 штук.
 Для вычисления функции Эйлера от степени простого числа используютследующую формулу:

φ(pn)=pnpn1.
 Это равенство обосновывается следующим образом. Подсчитаем количествочисел от 1 до pn, которые не взаимно просты с pn. Все они,очевидно, кратны p, то есть, имеют вид:p,2p,3p,,(pn11)p. Всего таких чисел pn11.Поэтому количество чисел, взаимно простых с pn, равноpn1(pn11)=pnpn1.

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


 Вычисление φ(n) для произвольного натурального n основываетсяна мультипликативности функции Эйлера, выражении для φ(pn), атакже на основной теореме арифметики. Для произвольного натуральногочисла значение φ(n) представляется в виде:

φ(n)=npn(11p),n>1,
 где p — простое число и пробегает все значения, участвующие вразложении n на простые сомножители.

Свойства


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


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

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

φ(mn)=φ(m)φ(n)dφ(d),
 где d — наибольший общий делитель m и n. Это свойство являетсяестественным обобщением мультипликативности. \{cdotsd\_\{K\}\^\{\{delta\_\{K\}\},
m=dα11dαkkpβ11pβrr,
n=dγk+1k+1dγKKqϵ11qϵss.Здесь первые k делителей d являются также делителями m, апоследние Kk делителей d являются делителями n. Распишем:
φ(mn)=φ(d2mn)=φ((dδ11dδkkdδk+1k+1dδKK)2dα11dαkkpβ11pβrrdγk+1k+1dγKKqϵ11qϵss).В силу мультипликативности функции Эйлера, а также с учётом формулы
φ(pn)=pn(11p), где 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)}.
 \texttt \textbarframe-style = border: 1px solid rgb(200,200,200); \textbar\\\texttt title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;\textbar \\\texttt content-style = color: black; background-color: white; text-align: left; \textbar\\\texttt hidden=1
 \}\} Некоторые частные случаи:

  • \;\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, а d — их наибольший общий делитель.

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


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

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).
 Следующее равенство является следствием :

\varphi(a^{n} + b^{n}) \equiv 0 \pmod n, \; a > b \ge 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).

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

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

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

  • Пусть m — чётное, положим
    A(m) = m \prod_{p-1|m}\frac{p}{p-1}, где p — простое.


 Если n \in \varphi^{-1}(m), то m < n \le 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 раз вычислитьфункцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтомунахождение прообраза в целом является вычислительно сложной задачей.

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


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



  • Оценка снизу значений функции Эйлера:
    \varphi(n) \ge \sqrt{n},


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

  • Оценка сверху для составных n:
    \varphi(n) \le n - \sqrt{n},


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

  • Для всех натуральных значений n \ge 3 справедливо двойное неравенство:
    \frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.

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

) с\emphn

  • Верхняя грань отношения \varphi(n)/n приближается к единице с ростом n:
    \varlimsup \frac{\varphi(n)}{n} = 1.
  • В то же время отношение \varphi(n)/n^{1-\delta} может быть сколь угодно большим:
    \forall \delta > 0: \; \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,\{cdots\{right\{\}

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

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





 \{left\{\{\{frac\{\{varphi(n)\}\{n\},\{;\{;n= 1,2,\{cdots\{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) \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).
 \{varphi(n) \textgreater \{frac \{n\}\{e\^\{gamma\{; \{log\{log n + \{frac \{3\} \{\{log\{log n\}\}
  для n \textgreater 2,

  • В качестве оценки сверху был установлен следующий факт: существует бесконечно много натуральных 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.

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


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

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


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

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


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

a \cdot x \equiv b \pmod n.
 Решение задаётся формулой:

x \equiv b \cdot a^{\varphi(n)-1} \pmod n, если (a,n) = 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).\\Пример. Группа\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) \ge 14, где \omega(n) — количество простых делителей. В1970 году Lieuwens установил, что если 3\mid n, то \omega(n) \ge 213и n > 5{,}5 \times 10^{570}. Wall в 1980 году доказал, что если30\mid n, то \omega(n) \ge 26.
 По сей день неизвестно, существуют ли составные решения задачи Лемера.Если предположить, что их не существует, то получается следующийкритерий простоты: n — простое тогда и только тогда, когда\varphi(n)\mid n-1.

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


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

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

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