Меню Главная Случайная статья Настройки Функция Эйлера Материал из https://ru.wikipedia.org Функция Эйлера ${\displaystyle \varphi (n)}$ — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших или равных ${\displaystyle n}$ и взаимно простых с ним[1]. Например, для числа 36 существует 12 меньших его и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), поэтому ${\displaystyle \varphi (36)=12}$. Названа в честь Эйлера, который впервые использовал её в 1763 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования», вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение ${\displaystyle \varphi (n)}$[2]. Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов (см. сравнение по модулю), теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA[3]. Содержание 1 Вычисление 1.1 Общие сведения 1.2 Мультипликативность функции Эйлера 1.3 Функция Эйлера от простого числа 1.4 Функция Эйлера от натурального числа 2 Свойства 2.1 Обобщённая мультипликативность 2.2 Теорема Эйлера 2.3 Другие свойства 3 Множество значений 4 Асимптотические соотношения 4.1 Простейшие неравенства 4.2 Сравнение (n) с n 4.3 Отношение последовательных значений 4.4 Асимптотики для сумм 4.5 Порядок функции Эйлера 5 Связь с другими функциями 5.1 Функция Мёбиуса 5.2 Ряд Дирихле 5.3 Ряд Ламберта 5.4 Наибольший общий делитель 5.5 Связь с латинскими квадратами 6 Приложения и примеры 6.1 Функция Эйлера в RSA 6.2 Вычисление обратного элемента 6.3 Решение линейного сравнения 6.4 Вычисление остатка от деления 6.5 Нахождение порядка мультипликативной группы кольца вычетов 6.6 Приложения в теории групп 7 Нерешенные вопросы 7.1 Задача Лемера 7.2 Гипотеза Кармайкла 8 См. также 9 Примечания 10 Литература 11 Ссылки Вычисление Первые 99 значений функции Эйлера[4] ${\displaystyle \varphi (n)}$ +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 0+ 1 1 2 2 4 2 6 4 6 10+ 4 10 4 12 6 8 8 16 6 18 20+ 8 12 10 22 8 20 12 18 12 28 30+ 8 30 16 20 16 24 12 36 18 24 40+ 16 40 12 42 20 24 22 46 16 42 50+ 20 32 24 52 18 40 24 36 28 58 60+ 16 60 30 36 32 48 20 66 32 44 70+ 24 70 24 72 36 40 36 60 24 78 80+ 32 54 40 82 24 64 42 56 40 88 90+ 24 72 44 60 46 72 32 96 42 60 Общие сведения Функция Эйлера ${\displaystyle \varphi (n)}$ показывает, сколько натуральных чисел из отрезка ${\displaystyle [1,\;n]}$ имеют c ${\displaystyle n}$ только один общий делитель — единицу. Функция Эйлера определена на множестве натуральных чисел, и значения её лежат во множестве натуральных чисел. Как следует из определения, чтобы вычислить ${\displaystyle \varphi (n)}$, нужно перебрать все числа от ${\displaystyle 1}$ до ${\displaystyle n-1}$, и для каждого проверить, имеет ли оно общие делители с ${\displaystyle n}$, а затем подсчитать, сколько чисел оказались взаимно простыми с ${\displaystyle n}$. Эта процедура для больших чисел ${\displaystyle n}$ весьма трудоёмка, поэтому для вычисления ${\displaystyle \varphi (n)}$ используют другие методы, которые основываются на специфических свойствах функции Эйлера. В таблице справа представлены первые 99 значений функции Эйлера. Значение ${\displaystyle \varphi (n)}$ при ${\displaystyle n>1}$ не превосходит ${\displaystyle n-1}$, и в точности ему равно, если ${\displaystyle n}$ — простое. Таким образом, если в координатах ${\displaystyle (n,\;y)}$ провести прямую ${\displaystyle y=n-1}$, то значения ${\displaystyle y=\varphi (n)}$ будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения ${\displaystyle \varphi (n)}$ снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число ${\displaystyle n}$, такое, что ${\displaystyle \varphi (n)}$ лежит ниже этой прямой. Ещё одной интересной особенностью графика является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой ${\displaystyle y=n-1}$, на которой лежат значения ${\displaystyle \varphi (n)=n-1}$, где ${\displaystyle n}$ — простое, выделяется прямая, примерно соответствующая ${\displaystyle y=n/2}$, на которую попадают значения ${\displaystyle \varphi (2n)=\varphi (n)=n-1}$, где ${\displaystyle n}$ — простое. Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения. Мультипликативность функции Эйлера Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел ${\displaystyle m}$ и ${\displaystyle n}$ [5] ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}$ Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема[6]. Теорема 1. Пусть ${\displaystyle (m,\;m')=1}$ и ${\displaystyle a}$ пробегает полную систему вычетов по модулю ${\displaystyle m}$, в то время как ${\displaystyle a'}$ пробегает полную систему вычетов по модулю ${\displaystyle m'}$. Тогда числа ${\displaystyle a'm+am'}$ образуют полную систему вычетов по модулю ${\displaystyle mm'}$. Доказательство. Если ${\displaystyle a_{1}'m+a_{1}m'\equiv a_{2}'m+a_{2}m'{\pmod {mm'}},}$ тогда ${\displaystyle a_{1}m'\equiv a_{2}m'{\pmod {m}},}$ поэтому ${\displaystyle a_{1}\equiv a_{2}{\pmod {m}};}$ аналогично ${\displaystyle a_{1}'\equiv a_{2}'{\pmod {m'}}.}$ Поэтому существует ${\displaystyle mm'}$ несравнимых по модулю чисел, которые образуют полную систему вычетов по модулю ${\displaystyle mm'}$. Теперь можно доказать основное утверждение[7]. Теорема 2. Функция Эйлера мультипликативна. Доказательство. Если ${\displaystyle (m,\;m')=1}$, то по Теореме 1 достаточно найти все значения ${\displaystyle a'm+am'}$ которые взаимно просты с ${\displaystyle mm'}$: ${\displaystyle (a'm+am',\;mm')=1}$ ${\displaystyle \Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1}$ ${\displaystyle \Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1}$ ${\displaystyle \Leftrightarrow (a,\;m)=1,\;(a',\;m')=1.}$ Функция Эйлера от простого числа Для простого ${\displaystyle p}$ значение функции Эйлера задаётся явной формулой[8]: ${\displaystyle \varphi (p)=p-1,}$ которая следует из определения. Действительно, если ${\displaystyle p}$ — простое, то все числа, меньшие ${\displaystyle p}$, взаимно просты с ним, а их ровно ${\displaystyle p-1}$ штук. Для вычисления функции Эйлера от степени простого числа используют следующую формулу[8]: ${\displaystyle \varphi (p^{n})=p^{n}-p^{n-1}.}$ Это равенство обосновывается следующим образом. Подсчитаем количество чисел от ${\displaystyle 1}$ до ${\displaystyle p^{n}}$, которые не взаимно просты с ${\displaystyle p^{n}}$. Все они, очевидно, кратны ${\displaystyle p}$, то есть, имеют вид: ${\displaystyle p,\;2p,\;3p,\;\ldots ,\;p^{n-1}p.}$ Всего таких чисел ${\displaystyle p^{n-1}}$. Поэтому количество чисел, взаимно простых с ${\displaystyle p^{n}}$, равно ${\displaystyle p^{n}-p^{n-1}}$. Функция Эйлера от натурального числа Вычисление ${\displaystyle \varphi (n)}$ для произвольного натурального ${\displaystyle n}$ основывается на мультипликативности функции Эйлера, выражении для ${\displaystyle \varphi (p^{n})}$, а также на основной теореме арифметики. Для произвольного натурального числа значение ${\displaystyle \varphi (n)}$ представляется в виде[8]: ${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),\;\;n>1,}$ где ${\displaystyle p}$ — простое число и пробегает все значения, участвующие в разложении ${\displaystyle n}$ на простые сомножители.