Русская Википедия:Функция Эйлера

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:EulerPhi.svg

Первая тысяча значений <math>\varphi(n)</math>

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

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

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

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

Вычисление

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

<math>\varphi(n)</math>	+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

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

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

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

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

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

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

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

<math>\varphi(mn)=\varphi(m)\varphi(n).</math>

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

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

<math>\varphi(p)=p-1,</math>

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

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

<math>\varphi(p^n)=p^n-p^{n-1}.</math>

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

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

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

<math>\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,</math>

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

Пример применения: <math>\varphi(36) = \varphi(2^2\cdot 3^2) = \varphi(2^2) \varphi(3^2) = (2^2-2)(3^2-3) = 2\cdot 6 = 12.</math>

Свойства

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

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

<math>\varphi(mn)=\varphi(m)\varphi(n) \;\;\; \forall m,\, n \in \N\colon (m,\,n)=1.</math>

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

<math>\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},</math>

где <math>d</math> — наибольший общий делитель <math>m</math> и <math>n.</math> Это свойство является естественным обобщением мультипликативности. Шаблон:Hider \cdot\ldots\cdot d_{K}^{\delta_{K}},</math>

<math>m' = d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r},</math>

<math>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}.</math>

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

<math>\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}).</math> В силу мультипликативности функции Эйлера, а также с учётом формулы

<math>\varphi(p^n) = p^n(1-\frac{1}{p}),</math>

где <math>p</math> — простое, получаем:

<math>

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

<math>\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.</math>

 |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

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

• <math>\;\varphi\left(n^m\right) = n^{m-1}\varphi(n).</math>
• <math>

\varphi(2m) = \begin{cases} 2\varphi(m), & m = 2k,\; k \in \N, \\ \varphi(m), & m = 2k - 1,\; k \in \N. \end{cases} </math>

• <math>\varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n),</math> где <math>M</math> — наименьшее общее кратное <math>m</math> и <math>n</math>, а <math>d</math> — их наибольший общий делитель.

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

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

<math>a^{\varphi(m)}\equiv 1\pmod m,</math>

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

<math>a^{m - 1}\equiv 1\pmod m.</math>

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

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

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

<math>a\mid b \Rightarrow \varphi(a)\mid\varphi(b).</math>

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

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

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

<math>\sum_{d\mid n}\varphi(d)=n.</math>

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

<math>\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n > 1.</math>

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

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

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

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

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

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

• Пусть <math>m</math> — чётное, положим

  <math>A(m) = m \prod_{p-1\mid m}\frac{p}{p-1},</math> где <math>p</math> — простое.

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

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

1) вычислить <math>A(m)</math>;

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

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

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

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

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

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

  <math> \varphi(n) \geqslant \sqrt{n},</math>

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

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

  <math>\varphi(n) \leqslant n - \sqrt{n},</math>

для всякого составного <math>n.</math>

• Для всех натуральных значений <math>n \geqslant 3</math> справедливо двойное неравенствоШаблон:Sfn:

  <math>\frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.</math>

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

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

  <math>\varlimsup \frac{\varphi(n)}{n} = 1.</math>

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

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

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

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

  <math>\lim\inf \frac{\varphi(n+1)}{\varphi(n)}= 0</math> и <math>\lim\sup \frac{\varphi(n+1)}{\varphi(n)}= \infty.</math>

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

<math>\left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,\;2,\;\ldots\right\}</math>

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

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

<math>\left\{\frac{\varphi(n)}{n},\;\;n = 1,\;2,\;\ldots\right\}</math>

плотно на интервале <math>(0,\;1).</math>

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

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

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

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

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

  <math>\sum_{k=1}^n\frac{k}{\varphi(k)}=O(n)</math>;

  <math>\sum_{k=1}^n\frac{1}{\varphi(k)}=O(\ln n)</math>.

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

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

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

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

  <math>\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma},</math>

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

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

  <math>\varphi(n) \geqslant \frac {n} {e^{\gamma}\log \log n + \frac{2{,}5}{\log \log n}},</math>

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

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

  <math>\varphi(n) < e^{-\gamma} \frac {n} {\log \log n}.</math>

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

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

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

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

  <math>\varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right),</math>

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

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

  <math>\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);</math>

  <math>\sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor;</math>

  <math>\sum_{d\mid n}\frac{\mu^2(d)}{\varphi(d)}=\frac{n}{\varphi(n)}</math>.

Ряд Дирихле

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

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

Ряд Ламберта

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

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

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

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

  <math>\varphi (n)=\sum\limits_{k=1}^n \gcd(k,\,n) e^{{-2\pi i}\tfrac{k}{n}}. </math>

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

<math>\varphi (n)=\sum\limits_{k=1}^n \gcd(k,\,n) \cos {2\pi\frac{k}{n}}.</math>

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

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

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

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

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

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

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

<math>\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),</math>

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

<math>d \cdot e = 1 \;\bmod \;\varphi(n).</math>

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

<math>c = m^e \;\bmod \;n.</math>

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

<math>m = c^d \;\bmod \;n.</math>

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

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

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

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

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

<math>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.</math>

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

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

<math>a \cdot x \equiv b \pmod n.</math>

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

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

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

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

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

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

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

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

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

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

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

<math>k\varphi(n) = n-1,</math>

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

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

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

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

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

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

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

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

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

<math>\forall k \geqslant 2 \;\exist m\colon \dim(\varphi^{-1}(m)) = k.</math>

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон: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

Внешние ссылки