Функция Эйлера
Фу́нкция Э́йлера [math]\displaystyle{ \varphi(n) }[/math] — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших [math]\displaystyle{ n }[/math] и взаимно простых с ним[1].
Например, для числа 36 существует 12 меньших его и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), поэтому [math]\displaystyle{ \varphi(36)=12 }[/math].
Названа в честь Эйлера, который впервые использовал её в 1763 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования», вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение [math]\displaystyle{ \varphi(n) }[/math][2].
Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов (см. сравнение по модулю), теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA[3].
Вычисление
[math]\displaystyle{ \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]\displaystyle{ \varphi(n) }[/math] показывает, сколько натуральных чисел из отрезка [math]\displaystyle{ [1,\;n-1] }[/math] имеют c [math]\displaystyle{ n }[/math] только один общий делитель — единицу. Функция Эйлера определена на множестве натуральных чисел, и значения её лежат во множестве натуральных чисел.
Как следует из определения, чтобы вычислить [math]\displaystyle{ \varphi(n) }[/math], нужно перебрать все числа от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math], и для каждого проверить, имеет ли оно общие делители с [math]\displaystyle{ n }[/math], а затем подсчитать, сколько чисел оказались взаимно простыми с [math]\displaystyle{ n }[/math]. Эта процедура для больших чисел [math]\displaystyle{ n }[/math] весьма трудоёмка, поэтому для вычисления [math]\displaystyle{ \varphi(n) }[/math] используют другие методы, которые основываются на специфических свойствах функции Эйлера.
В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение [math]\displaystyle{ \varphi(n) }[/math] не превосходит [math]\displaystyle{ n-1 }[/math], и в точности ему равно, если [math]\displaystyle{ n }[/math] — простое. Таким образом, если в координатах [math]\displaystyle{ (n,\;y) }[/math] провести прямую [math]\displaystyle{ y=n-1 }[/math], то значения [math]\displaystyle{ y=\varphi(n) }[/math] будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения [math]\displaystyle{ \varphi(n) }[/math] снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число [math]\displaystyle{ n }[/math], такое, что [math]\displaystyle{ \varphi(n) }[/math] лежит ниже этой прямой. Ещё одной интересной особенностью графика является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой [math]\displaystyle{ y=n-1 }[/math], на которой лежат значения [math]\displaystyle{ \varphi(n)=n-1 }[/math], где [math]\displaystyle{ n }[/math] — простое, выделяется прямая, примерно соответствующая [math]\displaystyle{ y=n/2 }[/math], на которую попадают значения [math]\displaystyle{ \varphi(2n)=\varphi(n)=n-1 }[/math], где [math]\displaystyle{ n }[/math] — простое.
Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.
Мультипликативность функции Эйлера
Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] [5]
- [math]\displaystyle{ \varphi(mn)=\varphi(m)\varphi(n). }[/math]
Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема[6].
- Теорема 1. Пусть [math]\displaystyle{ (m,\;m')=1 }[/math] и [math]\displaystyle{ a }[/math] пробегает полную систему вычетов по модулю [math]\displaystyle{ m }[/math], в то время как [math]\displaystyle{ a' }[/math] пробегает полную систему вычетов по модулю [math]\displaystyle{ m' }[/math]. Тогда числа [math]\displaystyle{ a'm+am' }[/math] образуют полную систему вычетов по модулю [math]\displaystyle{ m }[/math][math]\displaystyle{ m' }[/math].
- Доказательство. Если
- [math]\displaystyle{ a_1'm+a_1m'\equiv a_2'm+a_2m'\pmod{mm'}, }[/math]
- тогда
- [math]\displaystyle{ a_1m'\equiv a_2m'\pmod m, }[/math]
- поэтому
- [math]\displaystyle{ a_1\equiv a_2\pmod m; }[/math]
- аналогично
- [math]\displaystyle{ a_1'\equiv a_2'\pmod{m'}. }[/math]
- Поэтому существует [math]\displaystyle{ mm' }[/math] несравнимых по модулю чисел, которые образуют полную систему вычетов по модулю [math]\displaystyle{ mm' }[/math].
Теперь можно доказать основное утверждение[7].
- Теорема 2. Функция Эйлера мультипликативна.
- Доказательство. Если [math]\displaystyle{ (m,\;m')=1 }[/math], то по Теореме 1 [math]\displaystyle{ a'm+am' }[/math] пробегает приведённую систему вычетов по модулю [math]\displaystyle{ mm' }[/math], когда [math]\displaystyle{ a }[/math] и [math]\displaystyle{ a' }[/math] пробегают приведённые системы вычетов по модулям [math]\displaystyle{ m }[/math] и [math]\displaystyle{ m' }[/math] соответственно. Также:
- [math]\displaystyle{ (a'm+am',\;mm')=1 }[/math]
- [math]\displaystyle{ \Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1 }[/math]
- [math]\displaystyle{ \Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1 }[/math]
- [math]\displaystyle{ \Leftrightarrow (a,\;m)=1,\;(a',\;m')=1. }[/math]
- Поэтому [math]\displaystyle{ \varphi(mm') }[/math] чисел, которые меньше числа [math]\displaystyle{ mm' }[/math] и взаимно просты с ним, являются наименьшими положительными вычетами среди [math]\displaystyle{ \varphi(m)\varphi(m') }[/math] значений [math]\displaystyle{ a'm+am' }[/math], для которых [math]\displaystyle{ a }[/math] взаимно просто с [math]\displaystyle{ m }[/math] и [math]\displaystyle{ a' }[/math] взаимно просто с [math]\displaystyle{ m' }[/math]. Отсюда следует, что
- [math]\displaystyle{ \varphi(mm')=\varphi(m)\varphi(m'). }[/math]
Функция Эйлера от простого числа
Для простого [math]\displaystyle{ p }[/math] значение функции Эйлера задаётся явной формулой[8]:
- [math]\displaystyle{ \varphi(p)=p-1, }[/math]
которая следует из определения. Действительно, если [math]\displaystyle{ p }[/math] — простое, то все числа, меньшие [math]\displaystyle{ p }[/math], взаимно просты с ним, а их ровно [math]\displaystyle{ p-1 }[/math] штук.
Для вычисления функции Эйлера от степени простого числа используют следующую формулу[8]:
- [math]\displaystyle{ \varphi(p^n)=p^n-p^{n-1}. }[/math]
Это равенство обосновывается следующим образом. Подсчитаем количество чисел от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ p^n }[/math], которые не взаимно просты с [math]\displaystyle{ p^n }[/math]. Все они, очевидно, кратны [math]\displaystyle{ p }[/math], то есть, имеют вид: [math]\displaystyle{ p,\;2p,\;3p,\;\ldots,\;p^{n-1}p. }[/math] Всего таких чисел [math]\displaystyle{ p^{n-1} }[/math]. Поэтому количество чисел, взаимно простых с [math]\displaystyle{ p^n }[/math], равно [math]\displaystyle{ p^n-p^{n-1} }[/math].
Функция Эйлера от натурального числа
Вычисление [math]\displaystyle{ \varphi(n) }[/math] для произвольного натурального [math]\displaystyle{ n }[/math] основывается на мультипликативности функции Эйлера, выражении для [math]\displaystyle{ \varphi(p^{n}) }[/math], а также на основной теореме арифметики. Для произвольного натурального числа значение [math]\displaystyle{ \varphi(n) }[/math] представляется в виде[8]:
- [math]\displaystyle{ \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n\gt 1, }[/math]
где [math]\displaystyle{ p }[/math] — простое число и пробегает все значения, участвующие в разложении [math]\displaystyle{ n }[/math] на простые сомножители.
Как следует из основной теоремы арифметики, всякое натуральное число [math]\displaystyle{ n\gt 1 }[/math] единственным образом представляется в виде:
- [math]\displaystyle{ n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}, }[/math]
где [math]\displaystyle{ p_1\lt \ldots\lt p_k }[/math] — простые числа, [math]\displaystyle{ \alpha_1,\;\ldots,\;\alpha_k }[/math] — натуральные числа.
Используя мультипликативность функции Эйлера и выражение для [math]\displaystyle{ \varphi(p^{k}) }[/math], получаем: [math]\displaystyle{ \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} }[/math]
Пример применения: [math]\displaystyle{ \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]\displaystyle{ \varphi(mn)=\varphi(m)\varphi(n) \;\;\; \forall m,\, n \in \N\colon (m,\,n)=1. }[/math]
Здесь существенно, что наибольший общий делитель [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] равен единице. Оказывается, существует обобщение этой формулы на случай, когда [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] имеют общие делители, отличные от единицы. А именно, для любых натуральных [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] [9]:
- [math]\displaystyle{ \varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)}, }[/math]
где [math]\displaystyle{ d }[/math] — наибольший общий делитель [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n. }[/math] Это свойство является естественным обобщением мультипликативности.
Пусть [math]\displaystyle{ (m,\,n)=d, }[/math] тогда [math]\displaystyle{ m = m'd, \; n = n'd, }[/math] причем в общем случае [math]\displaystyle{ (m',\,d) \neq 1 }[/math] и [math]\displaystyle{ (n',\,d) \neq 1. }[/math] Поэтому можно записать:
- [math]\displaystyle{ 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}}, }[/math]
- [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ k }[/math] делителей [math]\displaystyle{ d }[/math] являются также делителями [math]\displaystyle{ m', }[/math] а последние [math]\displaystyle{ K-k }[/math] делителей [math]\displaystyle{ d }[/math] являются делителями [math]\displaystyle{ n'. }[/math] Распишем:
- [math]\displaystyle{ \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]\displaystyle{ \varphi(p^n) = p^n(1-\frac{1}{p}), }[/math]
где [math]\displaystyle{ p }[/math] — простое, получаем:
- [math]\displaystyle{ \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]\displaystyle{ \varphi(m), }[/math] во второй — [math]\displaystyle{ \varphi(n), }[/math] а третью можно представить, как [math]\displaystyle{ d/\varphi(d). }[/math] Поэтому:
- [math]\displaystyle{ \varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}. }[/math]
Некоторые частные случаи:
- [math]\displaystyle{ \;\varphi\left(n^m\right) = n^{m-1}\varphi(n). }[/math]
- [math]\displaystyle{ \varphi(2m) = \begin{cases} 2\varphi(m), & m = 2k,\; k \in \N, \\ \varphi(m), & m = 2k - 1,\; k \in \N. \end{cases} }[/math]
- [math]\displaystyle{ \varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n), }[/math] где [math]\displaystyle{ M }[/math] — наименьшее общее кратное [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math], а [math]\displaystyle{ d }[/math] — их наибольший общий делитель.
Теорема Эйлера
Наиболее часто на практике используется свойство, установленное Эйлером:
- [math]\displaystyle{ a^{\varphi(m)}\equiv 1\pmod m, }[/math]
если [math]\displaystyle{ a }[/math] и [math]\displaystyle{ m }[/math] взаимно просты.
Это свойство, которое называют теоремой Эйлера, вытекает из теоремы Лагранжа теории групп и того факта, что значение [math]\displaystyle{ \varphi(m) }[/math] равно количеству элементов (порядку) мультипликативной группы обратимых элементов кольца вычетов по модулю [math]\displaystyle{ m }[/math].
Следствием теоремы Эйлера является малая теорема Ферма. Если взять не произвольное натуральное [math]\displaystyle{ m, }[/math] а простое число [math]\displaystyle{ m, }[/math], то:
- [math]\displaystyle{ a^{p - 1}\equiv 1\pmod p. }[/math]
Последняя формула находит применение в различных тестах простоты.
Другие свойства
Исходя из представимости [math]\displaystyle{ \varphi(n) }[/math] произведением Эйлера, несложно получить следующее полезное утверждение:
- [math]\displaystyle{ a\mid b \Rightarrow \varphi(a)\mid\varphi(b). }[/math]
Следующее равенство[10][11] является следствием теоремы Зигмонди :
- [math]\displaystyle{ \varphi(a^{n} + b^{n}) \equiv 0 \pmod n, \; a \gt b \geqslant 1. }[/math]
Всякое натуральное число представимо в виде суммы значений функции Эйлера от его натуральных делителей[12]:
- [math]\displaystyle{ \sum_{d\mid n}\varphi(d)=n. }[/math]
Сумма всех чисел, меньших данного, и взаимно простых с ним, выражается через функцию Эйлера:
- [math]\displaystyle{ \sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n \gt 1. }[/math]
Множество значений
Исследование структуры множества значений функции Эйлера является отдельной сложной задачей. Здесь представлены лишь некоторые результаты, полученные в этой области[13].
- Функция Эйлера [math]\displaystyle{ \varphi(n) }[/math] принимает только чётные значения при [math]\displaystyle{ n \gt 2. }[/math] Причём, если [math]\displaystyle{ n }[/math] имеет [math]\displaystyle{ r }[/math] различных нечётных простых делителей, то [math]\displaystyle{ 2^{r} \mid \varphi(n). }[/math]
- Действительно, если [math]\displaystyle{ p }[/math] — простое нечётное и [math]\displaystyle{ \alpha \gt 1, }[/math] то
- [math]\displaystyle{ p^{\alpha - 1}(p - 1) }[/math] — чётное.
- Из равенства
- [math]\displaystyle{ \varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i - 1}(p_i - 1) }[/math]
- следует утверждение.
В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции. Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду следующее.
- Значения функции Эйлера повторяются (например, [math]\displaystyle{ \varphi(1) = \varphi(2) = 1 }[/math]), следовательно обратная функция является многозначной.
- Функция Эйлера принимает лишь чётные значения при [math]\displaystyle{ n \gt 2, }[/math] то есть [math]\displaystyle{ \varphi^{-1}(m) = \varnothing, }[/math] если [math]\displaystyle{ m }[/math] нечётно и [math]\displaystyle{ m \neq 1. }[/math]
В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза [math]\displaystyle{ \varphi }[/math] является следующая теорема[14].
- Пусть [math]\displaystyle{ m }[/math] — чётное, положим
- [math]\displaystyle{ A(m) = m \prod_{p-1\mid m}\frac{p}{p-1}, }[/math] где [math]\displaystyle{ p }[/math] — простое.
- Если [math]\displaystyle{ n \in \varphi^{-1}(m), }[/math] то [math]\displaystyle{ m \lt n \leqslant A(m). }[/math]
- Очевидно, если [math]\displaystyle{ \varphi(n) = m, }[/math] то [math]\displaystyle{ m \lt n. }[/math] С другой стороны, если [math]\displaystyle{ \varphi(n) = m }[/math] и [math]\displaystyle{ n = p_1^{\alpha_1} \cdot\ldots\cdot p_s^{\alpha_s}, }[/math] то
- [math]\displaystyle{ 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}. }[/math]
- Однако, если [math]\displaystyle{ p\mid n, }[/math] то [math]\displaystyle{ p-1\mid\varphi(n). }[/math] Поэтому
- [math]\displaystyle{ \forall p_i: \; p_i-1\mid m. }[/math]
- Следовательно [math]\displaystyle{ n \leqslant A(m). }[/math]
Эта теорема показывает, что прообраз элемента [math]\displaystyle{ m \in \N }[/math] всегда представляет собой конечное множество. Также она даёт следующий практический способ нахождения прообраза:
- 1) вычислить [math]\displaystyle{ A(m) }[/math];
- 2) вычислить [math]\displaystyle{ \varphi(n) }[/math] для всех [math]\displaystyle{ n }[/math] из полуинтервала [math]\displaystyle{ (m,\, A(m)] }[/math];
- 3) все числа [math]\displaystyle{ n, }[/math] для которых [math]\displaystyle{ \varphi(n)=m, }[/math] образуют прообраз элемента [math]\displaystyle{ m }[/math].
Может оказаться, что в указанном промежутке нет такого числа [math]\displaystyle{ n, }[/math] что [math]\displaystyle{ \varphi(n)=m; }[/math] в этом случае прообраз является пустым множеством.
Стоит отметить, что для вычисления [math]\displaystyle{ A(m) }[/math] нужно знать разложение [math]\displaystyle{ m }[/math] на простые сомножители, что для больших [math]\displaystyle{ m }[/math] является вычислительно сложной задачей. Затем нужно [math]\displaystyle{ A(m)-m }[/math] раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.
Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 — простые числа. Вычисляем
- [math]\displaystyle{ A(4) = 4 \cdot \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{5}{4} = 15. }[/math]
Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:
- [math]\displaystyle{ \varphi^{-1}(4) = \{5,\; 8,\; 10,\; 12\}. }[/math]
Не существует, например, такого числа [math]\displaystyle{ m, }[/math] что [math]\displaystyle{ \varphi(m) = 14. }[/math] То есть:
- [math]\displaystyle{ \varphi^{-1}(14) = \varnothing. }[/math]
В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа — простые. Поэтому
- [math]\displaystyle{ A(14) = 14 \cdot \frac{2}{1} \cdot \frac{3}{2} = 42. }[/math]
Перебрав все числа от 15 до 42, несложно убедиться, что
- [math]\displaystyle{ \varphi(n) \neq 14, \; n \in (15,\, 42]. }[/math]
Асимптотические соотношения
Простейшие неравенства
- Оценка снизу значений функции Эйлера[15][16]:
- [math]\displaystyle{ \varphi(n) \geqslant \sqrt{n}, }[/math]
- для всех [math]\displaystyle{ n, }[/math] кроме [math]\displaystyle{ n = 2 }[/math] и [math]\displaystyle{ n = 6. }[/math]
- Оценка сверху для составных [math]\displaystyle{ n }[/math][15][17]:
- [math]\displaystyle{ \varphi(n) \leqslant n - \sqrt{n}, }[/math]
- для всякого составного [math]\displaystyle{ n. }[/math]
- Для всех натуральных значений [math]\displaystyle{ n \geqslant 3 }[/math] справедливо двойное неравенство[15]:
- [math]\displaystyle{ \frac{\log2}{2} \cdot \frac{n}{\log{n}} \lt \varphi(n) \lt n. }[/math]
Сравнение φ(n) с n
- Верхняя грань отношения [math]\displaystyle{ \varphi(n)/n }[/math] приближается к единице с ростом [math]\displaystyle{ n }[/math][18]:
- [math]\displaystyle{ \varlimsup \frac{\varphi(n)}{n} = 1. }[/math]
- В то же время отношение [math]\displaystyle{ \varphi(n)/n^{1-\delta} }[/math] может быть сколь угодно большим[19]:
- [math]\displaystyle{ \forall \delta \gt 0\colon \frac{\varphi(n)}{n^{1 - \delta}} \rightarrow \infty. }[/math]
Отношение последовательных значений
- Следующие равенства показывают, насколько непредсказуемо ведет себя функция Эйлера[20]:
- [math]\displaystyle{ \lim\inf \frac{\varphi(n+1)}{\varphi(n)}= 0 }[/math] и [math]\displaystyle{ \lim\sup \frac{\varphi(n+1)}{\varphi(n)}= \infty. }[/math]
- Формулы, приведенные выше, получил Somayajulu в 1950 году. А четырьмя годами позже Шинцель и Серпинский доказали[20], что множество
- [math]\displaystyle{ \left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,\;2,\;\ldots\right\} }[/math]
- плотно в множестве действительных положительных чисел.
- В том же году они установили[20], что множество
- [math]\displaystyle{ \left\{\frac{\varphi(n)}{n},\;\;n = 1,\;2,\;\ldots\right\} }[/math]
- плотно на интервале [math]\displaystyle{ (0,\;1). }[/math]
Асимптотики для сумм
- Точное выражение для суммы последовательных значений функции Эйлера[21]:
- [math]\displaystyle{ \sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x). }[/math]
- Отсюда вытекает, что средний порядок функции Эйлера равно [math]\displaystyle{ 6n/\pi^{2} }[/math]. Этот результат интересен тем, что позволяет получить вероятность события, состоящего в том, что два наугад выбранных натуральных числа являются взаимно простыми. А именно, эта вероятность равна [math]\displaystyle{ 6/\pi^{2} }[/math][22].
- С учётом приведённого выше выражения, можно получить следующие асимптотические оценки:
- [math]\displaystyle{ \sum_{k=1}^n\frac{k}{\varphi(k)}=O(n) }[/math];
- [math]\displaystyle{ \sum_{k=1}^n\frac{1}{\varphi(k)}=O(\ln n) }[/math].
- Используя мультипликативность функции Эйлера и свойства суммы делителей [math]\displaystyle{ \sigma(n) }[/math], несложно установить, что[23]
- [math]\displaystyle{ \frac {6}{\pi^2} \lt \frac{\varphi(n) \sigma(n)}{n^2} \lt 1, \; n \gt 1 }[/math].
Порядок функции Эйлера
- В 1909 году Ландау получил равенство[24][25]:
- [math]\displaystyle{ \lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}, }[/math]
- где [math]\displaystyle{ \gamma }[/math] — постоянная Эйлера — Маскерони.
- Этот результат можно уточнить. В 1962 году была получена оценка снизу для функции Эйлера[26]:
- [math]\displaystyle{ \varphi(n) \geqslant \frac {n} {e^{\gamma}\log \log n + \frac{2{,}5}{\log \log n}}, }[/math]
- для всех [math]\displaystyle{ n \geqslant 3 }[/math], с одним исключением [math]\displaystyle{ n = 2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23; }[/math] в указанном случае следует заменить [math]\displaystyle{ 2{,}5 }[/math] на [math]\displaystyle{ 2{,}50637. }[/math] Это одна из наиболее точных оценок снизу для [math]\displaystyle{ \varphi(n) }[/math][27].
- В качестве оценки сверху был установлен следующий факт[28]: существует бесконечно много натуральных [math]\displaystyle{ n }[/math] таких, что
- [math]\displaystyle{ \varphi(n) \lt e^{-\gamma} \frac {n} {\log \log n}. }[/math]
- Как отмечает Пауло Рибенбойм по поводу доказательства этого неравенства[27]: «Способ доказательства интересен тем, что неравенство сначала устанавливается в предположении, что гипотеза Римана верна, а затем в предположении, что она не верна».
Связь с другими функциями
Функция Мёбиуса
- Следующую формулу можно использовать для вычисления [math]\displaystyle{ \varphi(n) }[/math][29]:
- [math]\displaystyle{ \varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right), }[/math]
- где [math]\displaystyle{ \mu(m) }[/math] — функция Мёбиуса.
- Другие соотношения с функцией Мёбиуса:
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \sum_{d\mid n}\frac{\mu^2(d)}{\varphi(d)}=\frac{n}{\varphi(n)} }[/math][30].
Ряд Дирихле
- Ряд Дирихле с коэффициентами [math]\displaystyle{ \varphi(n) }[/math] можно представить через дзета-функцию Римана[31]:
- [math]\displaystyle{ \sum_{n=1}^\infty\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}, \; s \gt 2. }[/math]
Ряд Ламберта
- Сумма ряда Ламберта с коэффициентами [math]\displaystyle{ \varphi(n) }[/math][32]:
- [math]\displaystyle{ \sum_{n=1}^\infty\frac{\varphi(n)q^n}{1-q^n}=\frac{q}{(1-q)^2}, \; |q|\lt 1. }[/math]
Наибольший общий делитель
- Функция Эйлера является дискретным преобразованием Фурье наибольшего общего делителя[33]:
- [math]\displaystyle{ \varphi (n)=\sum\limits_{k=1}^n \gcd(k,\,n) e^{{-2\pi i}\tfrac{k}{n}}. }[/math]
- Действительная часть:
- [math]\displaystyle{ \varphi (n)=\sum\limits_{k=1}^n \gcd(k,\,n) \cos {2\pi\frac{k}{n}}. }[/math]
- В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей [math]\displaystyle{ n. }[/math]
Связь с латинскими квадратами
- Число циклических латинских квадратов порядка [math]\displaystyle{ N }[/math] с фиксированной первой строкой определяется функцией Эйлера [math]\displaystyle{ \varphi(N) }[/math]. Данную особенность можно использовать при вычислении значения функции Эйлера путем подсчета соответствующего числа квадратов заданного порядка [math]\displaystyle{ N }[/math] используя алгоритм без умножений и делений, однако асимптотически это медленнее, чем расчет на базе факторизации аргумента [math]\displaystyle{ N }[/math]. Циклические диагональные латинские квадраты являются подмножеством циклических латинских квадратов, поэтому число циклических диагональных латинских квадратов с фиксированной первой строкой (последовательность A123565 в OEIS) является ограничением снизу на значение функции Эйлера [math]\displaystyle{ \varphi(N) }[/math][34].
Приложения и примеры
Функция Эйлера в RSA
На основе алгоритма, предложенного в 1978 году Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом, была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов — система RSA. Криптостойкость этой системы определяется сложностью разложения на сомножители целого [math]\displaystyle{ n }[/math]-разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом[35].
На этапе создания пары из секретного и открытого ключей вычисляется
- [math]\displaystyle{ \varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1), }[/math]
где [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] — простые. Затем выбираются случайные числа [math]\displaystyle{ d,\ e }[/math] так, чтобы
- [math]\displaystyle{ d \cdot e = 1 \;\bmod \;\varphi(n). }[/math]
Затем сообщение шифруется открытым ключом адресата:
- [math]\displaystyle{ c = m^e \;\bmod \;n. }[/math]
После этого расшифровать сообщение может только обладатель секретного ключа [math]\displaystyle{ d }[/math]:
- [math]\displaystyle{ m = c^d \;\bmod \;n. }[/math]
Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.
В силу выбора чисел на этапе создания ключей
- [math]\displaystyle{ e \cdot d = 1 + a \cdot \varphi(n). }[/math]
Если [math]\displaystyle{ (m,\,n)=1, }[/math] то, с учетом теоремы Эйлера,
- [math]\displaystyle{ c^d = m^{ed} = m^{1}m^{a\varphi(n)} = m \cdot 1^{a} = m \;\bmod \;n. }[/math]
В общем случае [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] могут иметь общие делители, но расшифрование всё равно оказывается верным. Пусть [math]\displaystyle{ m = 0 \;\bmod \;p. }[/math] По китайской теореме об остатках:
- [math]\displaystyle{ m = c^d \;\bmod \;n \;\Leftrightarrow \;\begin{cases} m = c^d \;\bmod \;p, \\ m = c^d \;\bmod \;q. \end{cases} }[/math]
Подставляя [math]\displaystyle{ c = m^e, }[/math] получаем тождество
- [math]\displaystyle{ \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} }[/math]
Следовательно,
- [math]\displaystyle{ m^{ed} = m \;\bmod \;pq. }[/math]
Вычисление обратного элемента
Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю [math]\displaystyle{ n }[/math], а именно[36]:
- [math]\displaystyle{ a^{-1} \equiv a^{\varphi(n)-1} \pmod n, }[/math] если [math]\displaystyle{ (a,\,n) = 1. }[/math]
Эта формула следует из теоремы Эйлера:
- [math]\displaystyle{ 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]\displaystyle{ 5^{-1} \;\bmod \;7 }[/math], то есть такое число [math]\displaystyle{ x }[/math], что
- [math]\displaystyle{ 5 \cdot x \equiv 1 \pmod 7. }[/math]
Очевидно, [math]\displaystyle{ 5 }[/math] и [math]\displaystyle{ 7 }[/math] не имеют общих делителей кроме единицы, [math]\displaystyle{ (5,7)=1 }[/math], при этом число [math]\displaystyle{ 7 }[/math] простое и
- [math]\displaystyle{ \varphi(7)=7-1=6, }[/math]
поэтому удобно воспользоваться формулой, приведенной выше:
- [math]\displaystyle{ 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. }[/math]
Легко проверить, что в самом деле
- [math]\displaystyle{ 5 \cdot 3 \equiv 1 \pmod 7. }[/math]
В общем случае для вычисления обратных значений алгоритм Евклида быстрее, чем использование теоремы Эйлера[37], так как битовая сложность вычисления по алгоритму Евклида имеет порядок [math]\displaystyle{ O(k^2), }[/math] в то время как вычисление по теореме Эйлера требует порядка [math]\displaystyle{ O(k^3) }[/math] битовых операций, где [math]\displaystyle{ k = \lceil \log_2{n} \rceil. }[/math] Однако, в случае, когда известно разложение [math]\displaystyle{ \varphi(n)-1 }[/math] на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм «возводи в квадрат и перемножай»[38].
Если [math]\displaystyle{ (a,\,n) \neq 1, }[/math] то обратного к [math]\displaystyle{ a }[/math] элемента не существует, или, иначе говоря, уравнение
- [math]\displaystyle{ a \cdot x \equiv 1 \pmod n }[/math]
не имеет решения на множестве натуральных чисел[39].
Доказательство. В самом деле, допустим
- [math]\displaystyle{ (a,\,n)=d \gt 1, }[/math]
и решение существует. Тогда по определению наибольшего общего делителя
- [math]\displaystyle{ a = d \cdot a',\ n = d \cdot n', }[/math] причем [math]\displaystyle{ (a',\,n')=1; }[/math]
поэтому можно записать:
- [math]\displaystyle{ d \cdot a' \cdot x = d \cdot n' \cdot t + 1, }[/math] где [math]\displaystyle{ t \in \N_0, x \in \N; }[/math]
или, перегруппировав слагаемые,
- [math]\displaystyle{ a' \cdot x - n' \cdot t = \frac{1}{d}. }[/math]
Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью
- [math]\displaystyle{ d = 1, }[/math]
что противоречит предположению.
Решение линейного сравнения
Метод вычисления обратного элемента можно использовать для решения сравнения
- [math]\displaystyle{ a \cdot x \equiv b \pmod n. }[/math]
Решение задаётся формулой[37]:
- [math]\displaystyle{ x \equiv b \cdot a^{\varphi(n)-1} \pmod n, }[/math] если [math]\displaystyle{ (a,\,n) = 1. }[/math]
Рассмотрим сравнение
- [math]\displaystyle{ 7 \cdot x \equiv 3 \pmod 9. }[/math]
Так как [math]\displaystyle{ (7,9)=1, }[/math] можно воспользоваться указанной формулой:
- [math]\displaystyle{ 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. }[/math]
Подстановкой убеждаемся, что
- [math]\displaystyle{ 7 \cdot 3 \equiv 3 \pmod 9. }[/math]
Если [math]\displaystyle{ (a,\,n) \neq 1 }[/math], сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение
- [math]\displaystyle{ 2 \cdot x \equiv 3 \pmod 4 }[/math]
не имеет решения на множестве натуральных чисел. В то же время сравнение
- [math]\displaystyle{ 4 \cdot x \equiv 6 \pmod {22} }[/math]
имеет два решения
- [math]\displaystyle{ x = 7, \; x = 18. }[/math]
Вычисление остатка от деления
Функции Эйлера позволяет вычислять остатки от деления больших чисел[40].
Найдем последние три цифры в десятичной записи числа [math]\displaystyle{ 2^{100}. }[/math] Замечая, что
- [math]\displaystyle{ \varphi(125) = \varphi(5^3) = 5^3 - 5^2 = 100, }[/math]
получаем
- [math]\displaystyle{ 2^{100} \;\bmod \;125 = 2^{125 - 25} \;\bmod \;125 = 2^{\varphi(125)} \;\bmod \;125 = 1 \;\bmod \;125. }[/math]
Переходя теперь от модуля [math]\displaystyle{ 125 }[/math] к модулю [math]\displaystyle{ 1000, }[/math] имеем:
- [math]\displaystyle{ 2^{100} \equiv 1 \pmod{125} \equiv 376 \pmod{1000}. }[/math]
Следовательно, десятичная запись числа [math]\displaystyle{ 2^{100} }[/math] оканчивается на [math]\displaystyle{ 376. }[/math]
Найдем остаток от деления [math]\displaystyle{ 729^{720} }[/math] на [math]\displaystyle{ 1001. }[/math] Легко видеть, что
- [math]\displaystyle{ (729,\;1001)=1. }[/math]
Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством
- [math]\displaystyle{ \varphi(p) = p - 1, }[/math] для всякого простого [math]\displaystyle{ p, }[/math]
получаем
- [math]\displaystyle{ \varphi(1001) = \varphi(7 \cdot 11 \cdot 13) = \varphi(7) \cdot \varphi(11) \cdot \varphi(13) = 6 \cdot 10 \cdot 12 = 720. }[/math]
- [math]\displaystyle{ 729^{720} \equiv 1 \pmod{1001}. }[/math]
Нахождение порядка мультипликативной группы кольца вычетов
Мультипликативная группа кольца вычетов по модулю [math]\displaystyle{ m }[/math] состоит из [math]\displaystyle{ \varphi(m) }[/math] классов вычетов[41].
Пример. Приведённая система вычетов по модулю 14 состоит из [math]\displaystyle{ \varphi(14) = 6 }[/math] классов вычетов: [math]\displaystyle{ [1]_{14},\ [3]_{14},\ [5]_{14},\ [9]_{14},\ [11]_{14},\ [13]_{14}. }[/math]
Приложения в теории групп
Число порождающих элементов в конечной циклической группе [math]\displaystyle{ G }[/math] равно [math]\displaystyle{ \varphi(|G|) }[/math]. В частности, если мультипликативная группа кольца вычетов по модулю [math]\displaystyle{ m }[/math] является циклической группой — что возможно только при [math]\displaystyle{ m = 2,\; 4,\; p^{n},\; 2p^{n} }[/math], где [math]\displaystyle{ p }[/math] — простое нечётное, [math]\displaystyle{ n }[/math] — натуральное[42], — то существует [math]\displaystyle{ \varphi(\varphi(m)) }[/math] генераторов группы (первообразных корней по модулю [math]\displaystyle{ m }[/math]).
Пример. Группа [math]\displaystyle{ \Z_{14}^{\times}, }[/math] рассмотренная в примере выше, имеет [math]\displaystyle{ \varphi(\varphi(14)) = \varphi(6) = 2 }[/math] генератора: [math]\displaystyle{ 3 }[/math] и [math]\displaystyle{ 5. }[/math]
Нерешенные вопросы
Задача Лемера
Как известно, если [math]\displaystyle{ p }[/math] — простое, то [math]\displaystyle{ \varphi(p) = p - 1. }[/math] В 1932 году Деррик Лемер задался вопросом, существует ли такое составное число [math]\displaystyle{ n }[/math], что [math]\displaystyle{ \varphi(n) }[/math] является делителем [math]\displaystyle{ n-1 }[/math]. Лемер рассматривал уравнение:
- [math]\displaystyle{ k\varphi(n) = n-1, }[/math]
где [math]\displaystyle{ k }[/math] — целое. Ему удалось доказать, что если [math]\displaystyle{ n }[/math] — решение уравнения, то либо [math]\displaystyle{ n }[/math] — простое, либо оно является произведением семи или более различных простых чисел[43]. Позже были доказаны и другие сильные утверждения. Так, в 1980 году Cohen и Hagis показали, что если [math]\displaystyle{ n }[/math] составное и [math]\displaystyle{ \varphi(n) }[/math] делит [math]\displaystyle{ n-1, }[/math] то [math]\displaystyle{ n \gt 10^{20} }[/math] и [math]\displaystyle{ \omega(n) \geqslant 14, }[/math] где [math]\displaystyle{ \omega(n) }[/math] — количество простых делителей. В 1970 году Lieuwens установил, что если [math]\displaystyle{ 3\mid n, }[/math] то [math]\displaystyle{ \omega(n) \geqslant 213 }[/math] и [math]\displaystyle{ n \gt 5{,}5 \cdot 10^{570}. }[/math] Wall в 1980 году доказал, что если [math]\displaystyle{ 30\mid n, }[/math] то [math]\displaystyle{ \omega(n) \geqslant 26 }[/math][44].
По сей день неизвестно, существуют ли составные решения задачи Лемера. Если предположить, что их не существует, то получается следующий критерий простоты: [math]\displaystyle{ n }[/math] — простое тогда и только тогда, когда [math]\displaystyle{ \varphi(n)\mid n-1 }[/math][43].
Гипотеза Кармайкла
Если посмотреть даже на первые десять значений функции Эйлера {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, бросается в глаза, что среди них много повторяющихся. Гипотеза Кармайкла состоит в том, что нет такого значения [math]\displaystyle{ m }[/math], которое функция Эйлера принимала бы только один раз.
В 1907 году Кармайкл предложил как упражнение доказать следующее утверждение[45]:
- Если [math]\displaystyle{ n }[/math] — натуральное число, то существует натуральное число [math]\displaystyle{ m \neq n }[/math] такое, что [math]\displaystyle{ \varphi(n)=\varphi(m). }[/math]
Иначе это утверждение можно сформулировать так[46]: не существует натурального числа [math]\displaystyle{ m }[/math] такого, что [math]\displaystyle{ \dim(\varphi^{-1}(m)) = 1. }[/math]
Однако в 1922 году Кармайкл обнаружил, что предложенное им доказательство содержит ошибку. В этом же году он показал, что если [math]\displaystyle{ \dim(\varphi^{-1}(m)) = 1, }[/math] то [math]\displaystyle{ m \gt 10^{37}. }[/math] Позже эта оценка неоднократно улучшалась, и современное значение нижней границы, с которой стоит начинать искать контрпример для гипотезы Кармайкла, есть [math]\displaystyle{ m = 10^{10^7}. }[/math] Это значение получили Schlafly и Wagon в 1994 году, используя метод Klee[45].
Стоит отметить, что в 1999 году Форд доказал следующую теорему[47]:
- [math]\displaystyle{ \forall k \geqslant 2 \;\exist m\colon \dim(\varphi^{-1}(m)) = k. }[/math]
Это означает, что, задавшись некоторым числом [math]\displaystyle{ k \geqslant 2, }[/math] можно найти среди множества значений функции Эйлера такое значение [math]\displaystyle{ m, }[/math] что оно принимается ровно [math]\displaystyle{ k }[/math] раз. Однако, доказать, что нет такого значения, которое функция Эйлера принимала бы только один раз, до сих пор никому не удалось[46].
См. также
Примечания
- ↑ Эйлера функция // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1985. — Т. 5. — С. 934.
- ↑ Sandifer, 2007, p. 203.
- ↑ Габидулин, 2011, Системы RSA.
- ↑ последовательность A000010 в OEIS
- ↑ Burton, 2007, Theorem 7.2, p. 133.
- ↑ Hardy, 1975, Theorem 59, p. 52.
- ↑ Hardy, 1975, Theorem 60, p. 53.
- ↑ 8,0 8,1 8,2 Сагалович, 2007, Вычисление функции Эйлера, p. 35—36.
- ↑ Burton, 2007, Euler's Phi-Function, p. 136.
- ↑ Weisstein, MathWorld, Totient Function
- ↑ Ruiz, S., A Congruence With the Euler Totient Function, 2004
- ↑ Виноградов, 1952, Функция Эйлера.
- ↑ Информация в этом разделе основана на статье: Coleman, Some remarks on Euler’s totient function
- ↑ Gupta H., 1981
- ↑ 15,0 15,1 15,2 Handbook, 2005, Elementary inequalities for φ.
- ↑ Kendall and Osborn 1965
- ↑ Sierpiński and Schinzel 1988
- ↑ Hardy, 1975, Theorem 326, p. 267.
- ↑ Hardy, 1975, Theorem 327, p. 267.
- ↑ 20,0 20,1 20,2 Ribenboim, 1996, Values of Euler's Function, p. 38.
- ↑ Hardy, 1975, Theorem 330, p. 268.
- ↑ Hardy, 1975, Theorem 332, p. 269.
- ↑ Hardy, 1975, Theorem 329, p. 267.
- ↑ Handbook, 2005, On the function n/φ(n).
- ↑ Hardy, 1975, Theorem 328, p. 267.
- ↑ Rosser, J. Barkley and Schoenfeld, Lowell. Approximate formulas for some functions of prime numbers (англ.) // Illinois J. Math. : journal. — 1962. — Vol. 6, no. 1. — P. 64—94. (Theorem 15)
- ↑ 27,0 27,1 Ribenboim, 1996, Distribution of Values of Euler's Function, p. 320.
- ↑ Nicolas, 1983
- ↑ Виноградов, 1952, с. 29—31.
- ↑ Rosica Dineva, The Euler Totient, the Möbius, and the Divisor Functions
- ↑ Hardy, 1975, Theorem 288, p. 250.
- ↑ Hardy, 1975, Theorem 309, p. 258.
- ↑ Schramm, 2008
- ↑ Ватутин Э.И. О перечислении циклических латинских квадратов и расчете значения функции Эйлера с их использованием // Высокопроизводительные вычислительные системы и технологии. 2020. Т. 4, № 2. С. 40–48.
- ↑ Габидулин, 2011, Система шифрования RSA, с. 96.
- ↑ Алфёров, 2002, p. 462—463.
- ↑ 37,0 37,1 Schneier, 1995, The Euler Totient Function.
- ↑ Габидулин, 2011, Нахождение мультипликативного обратного по модулю, с. 233.
- ↑ Schneier, 1995, Number Theory.
- ↑ Сагалович, 2014.
- ↑ Сагалович, 2014, Приведенная система вычетов.
- ↑ Виноградов, 1952, с. 106.
- ↑ 43,0 43,1 Lehmer, 1932
- ↑ Ribenboim, 1996, p. 36—37.
- ↑ 45,0 45,1 Ribenboim, 1996, p. 39—40.
- ↑ 46,0 46,1 Coleman, Some remarks on Euler’s totient function
- ↑ 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.
- Сагалович Ю. Л. Введение в алгебраические коды. — 3-е изд., испр. и доп. — М.: ИППИ РАН, 2014. — 310 с. — ISBN 978-5-901158-24-1.
- 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.
Ссылки
- Арнольд В. И., Группы Эйлера и арифметика геометрических прогрессий (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