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

Первая тысяча значений $φ (n)$ . Точки на верхней линии обозначают $φ (p),$ когда $p$ — простое число, то есть $p - 1.$ ^[1]

В теории чисел функция тотента Эйлера подсчитывает положительные целые числа до заданного целого числа $n$ , которые являются относительно простыми с $n$ . Она записывается с использованием греческой буквы «фи» как или и может также называться функцией «фи» Эйлера . Другими словами, это количество целых чисел $k$ в диапазоне $1 \leq$ $k$ $\leq$ $n$ , для которых наибольший общий делитель $НОД($ $n$ $,$ $k$ $)$ равен 1. ^[2]^[3] Целые числа $k$ этого вида иногда равны называются тотативами n . $_$ ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ фи (п)}$

Например, совокупные числа $n = 9$ — это шесть чисел 1, 2, 4, 5, 7 и 8. Все они взаимно просты с 9, но остальные три числа в этом диапазоне — 3, 6 и 9 — нет. , поскольку $НОД(9, 3) = НОД(9, 6) = 3$ и $НОД(9, 9) = 9$ . Следовательно, $φ (9) = 6$ . Другой пример: $φ (1) = 1$ , поскольку при $n = 1$ единственное целое число в диапазоне от 1 до $n$ равно 1, а $gcd(1, 1) = 1$ .

Функция тотента Эйлера является мультипликативной функцией , что означает, что если два числа $m$ и $n$ взаимно простые, то $φ (mn) = φ (m) φ (n)$ . ^[4]^[5] Эта функция определяет порядок мультипликативной группы целых чисел по модулю n ( группа единиц кольца ) . ^[6] Он также используется для определения системы шифрования RSA . $\mathbb {Z} / n\mathbb {Z}$

История, терминология и обозначения

Леонард Эйлер ввел эту функцию в 1763 году. ^[7]^[8]^[9] Однако в то время он не выбрал какой-либо конкретный символ для ее обозначения. В публикации 1784 года Эйлер изучил функцию дальше, выбрав для ее обозначения греческую букву $π : он написал$ $πD$ для «множества чисел, меньших $D$ и не имеющих с ним общего делителя». ^[10] Это определение отличается от текущего определения функции тотента при $D = 1$ , но в остальном остается тем же. Теперь стандартное обозначение ^[8]^[11] $φ (A)$ взято из трактата Гаусса 1801 года Disquisitiones Arithmeticae , ^[12]^[13] , хотя Гаусс не использовал круглые скобки вокруг аргумента и написал $φA$ . Поэтому ее часто называют фи-функцией Эйлера или просто фи-функцией .

В 1879 году Дж. Дж. Сильвестр ввел термин totient для этой функции, ^[14]^[15] , поэтому ее также называют функцией totient Эйлера , totient Эйлера или totient Эйлера . Тотент Джордана является обобщением Эйлера.

Кофактор n определяется как $n$ $-$ $φ$ $($ $n$ $)$ $.$ _ Он подсчитывает количество натуральных чисел, меньших или равных $n$ , которые имеют хотя бы один общий простой делитель с $n$ .

Вычисление функции Эйлера

Существует несколько формул для вычисления $φ (n)$ .

Формула произведения Эйлера

Говорится

\varphi (n)=n\prod _{p\mid n}\left(1- {\frac {1}{p}}\right),

где произведение находится на различных простых числах , делящих $n$ . (Обозначения см. в разделе «Арифметическая функция ».)

Эквивалентная формулировка

\varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{ 2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),

разложение простых

n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}

п

p_{1},p_{2},\ldots,p_{r}

Доказательство этих формул зависит от двух важных фактов.

Фи — мультипликативная функция

Это означает, что если $НОД(m, n) = 1$ , то $φ (m) φ (n) = φ (mn)$ . Схема доказательства: Пусть $A$ , $B$ , $C$ — множества натуральных чисел, которые взаимно просты и меньше $m$ , $n$ , $mn$ соответственно, так что $| А | = φ (m)$ и т. д. Тогда существует взаимно однозначное соответствие между $A \times B$ и $C$ согласно китайской теореме об остатках .

Значение фи для аргумента простой степени

Если $p$ простое число и $k \geq 1$ , то

\varphi \left(p^{k}\right)=p^{k}-p^{k-1} = p^{k-1}(p-1)=p^{k}\ left(1-{\tfrac {1}{p}}\right).

Доказательство : поскольку $p$ — простое число, единственными возможными значениями $НОД(p k, m)$ являются $1, p, p 2, ..., p k$ , и единственный способ иметь $НОД(p k, m) > 1$ - это если $m$ кратно $p$ , то есть $m \in {p, 2 p, 3 p, ..., p k - 1 p = p k}$ , и существует $p k - 1$ таких кратных, не превышающих $пк$ . $_$ Следовательно, все остальные числа $p k - p k - 1$ взаимно просты с $p k$ .

Доказательство формулы произведения Эйлера

Основная теорема арифметики гласит, что если $n > 1,$ существует единственное выражение , где $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $r$ — простые числа и каждое $k$ $i$ $\geq 1$ . (Случай $n$ $= 1$ соответствует пустому произведению.) Многократное использование мультипликативного свойства $φ$ и формулы для $φ$ $($ $p$ $k$ $)$ дает $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},$

{\begin{array}{rcl}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\[.1em]&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}

Это дает обе версии формулы произведения Эйлера.

Альтернативное доказательство, которое не требует мультипликативного свойства, вместо этого использует принцип включения-исключения, применяемый к множеству , исключая наборы целых чисел, делящихся на простые делители. $\{1,2,\ldots ,n\}$

Пример

\varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.

Другими словами: отдельные простые делители числа 20 — это 2 и 5; половина из двадцати целых чисел от 1 до 20 делится на 2, остается десять; пятая часть из них делится на 5, в результате чего восемь чисел взаимно просты с 20; это: 1, 3, 7, 9, 11, 13, 17, 19.

Альтернативная формула использует только целые числа:

\varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.

преобразование Фурье

Тотент — это дискретное преобразование Фурье НОД , оцененное как 1. ^[16] Пусть

{\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}

где $x k = НОД(k, n)$ для $k \in {1, ..., n}$ . Затем

\varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.

Действительная часть этой формулы

\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.

Например, используя и : $\cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}$ $\cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}$

{\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}

n

n

n

Делитель суммы

Установленное Гауссом свойство ^[17] о том, что

\sum _{d\mid n}\varphi (d)=n,

где сумма вычисляется по всем положительным делителям $d$ числа $n$ , можно доказать несколькими способами. ( Условия обозначений см. в разделе «Арифметическая функция ».)

Одним из доказательств является то, что $φ (d)$ также равно числу возможных образующих $циклической$ группы $Cd$ ; в частности, если $C d = ⟨ g ⟩$ с $g d = 1$ , то $g k$ является генератором для каждого $k$ , взаимно простого с $d$ . Поскольку каждый элемент $Cn$ порождает циклическую подгруппу , а все подгруппы $Cd$ $\subseteq$ $Cn порождены ровно$ φ $($ $d) элементами Cn$ , $формула$ следующая $.$ ^[18] Эквивалентно, формула может быть получена с помощью того же аргумента, примененного к мультипликативной группе корней $n$ -й степени из единицы и примитивных корней $d-$ й степени из единицы .

Формулу также можно вывести из элементарной арифметики. ^[19] Например, пусть $n = 20$ и рассмотрим положительные дроби до 1 со знаменателем 20:

{\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.

Изложите их в самых низких терминах:

{\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}

Все эти двадцать дробей положительные.к/д≤ 1, знаменателями которого являются делители $d = 1, 2, 4, 5, 10, 20$ . Дроби со знаменателем 20 – это дроби, числители которых относительно просты с 20, а именно:1/20,3/20,7/20,9/20,11/20,13/20,17/20,19/20; по определению это $φ (20)$ дроби. Точно так же существуют дроби $φ (10)$ со знаменателем 10, дроби $φ (5)$ со знаменателем 5 и т. д. Таким образом, набор из двадцати дробей разбивается на подмножества размера $φ (d)$ для каждого $d,$ делящего 20. Аналогичный аргумент применяется для любого n.

Обращение Мёбиуса , примененное к формуле суммы делителей, дает

\varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},

где $µ$ — функция Мёбиуса , мультипликативная функция , определяемая формулами и для каждого простого числа $p$ и $k$ $\geq 2$ . Эту формулу также можно вывести из формулы произведения путем умножения, чтобы получить $\mu (p)=-1$ $\mu (p^{k})=0$ ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

Пример:

{\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\[.5em]&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}

Некоторые значения

Первые 100 значений (последовательность A000010 в OEIS ) показаны в таблице и на графике ниже:

На графике справа верхняя линия $y = n - 1$ представляет собой верхнюю границу, действительную для всех $n,$ кроме единицы, и достигается тогда и только тогда, когда $n$ — простое число. Простая нижняя граница — , которая довольно расплывчата: на самом деле нижняя граница графика пропорциональна $\varphi (n)\geq {\sqrt {n/2}}$ $н / войти в журнал н$ . ^[20]

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

Это означает, что если $a$ и $n$ взаимно простые , то

a^{\varphi (n)}\equiv 1\mod n.

Особый случай, когда $n$ — простое число, известен как малая теорема Ферма .

Это следует из теоремы Лагранжа и того факта, что $φ (n)$ — это порядок мультипликативной группы целых чисел по модулю $n$ .

Криптосистема RSA основана на этой теореме: она подразумевает, что обратная функция $a \mapsto a e mod n$ , где $e$ — (публичный) показатель шифрования, является функцией $b \mapsto b d mod n$ , где $d$ — (частный) показатель шифрования. ) показатель дешифрования является мультипликативным обратным значением $e$ по модулю $φ (n)$ . Таким образом, сложность вычисления $φ (n)$ без знания факторизации $n$ представляет собой сложность вычисления $d$ : это известно как проблема RSA , которую можно решить путем факторизации $n$ . Владелец закрытого ключа знает факторизацию, поскольку закрытый ключ RSA создается путем выбора $n$ как произведения двух (случайно выбранных) больших простых чисел $p$ и $q$ . Публично раскрыто только $n , и, учитывая$ сложность факторизации больших чисел, у нас есть гарантия, что никто больше не знает факторизации.

Другие формулы

$a\mid b\implies \varphi (a)\mid \varphi (b)$
$m\mid \varphi (a^{m}-1)$
$\varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)$
В частности:
- $\varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}$
- $\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$
$\varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)$
Сравните это с формулой (см. наименьшее общее кратное ). ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$
$φ (n)$ четно для $n \geq 3$ .
Более того, если $n$ имеет $r$ различных нечетных простых делителей, $2 r | φ (п)$
Для любых $a > 1$ и $n > 6$ таких, что $4 ∤ n$ , существует $l \geq 2 n$ такое, что $l | φ (а п - 1)$ .
${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$
где $rad(n)$ — радикал числа $n$ (произведение всех различных простых чисел, делящих $n$ ).
$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ ^[21]
$\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1$
$\sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ ( ^[22] цитируется в ^[23] )
$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ ^[22]
$\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)$ ^[24]
$\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)$ ^[24]
(где $γ$ — постоянная Эйлера–Машерони ).
$\sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)$
где $m > 1$ — целое положительное число, а $ω (m)$ — количество различных простых множителей числа $m$ . ^{[ нужна цитата ]}

Личность Менона

В 1965 году П. Кесава Менон доказал

\sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),

где $d (n) знак равно σ 0 (n)$ количество делителей $n$ .

Делимость на любое фиксированное положительное целое число

Следующее свойство, которое является частью «фольклора» (т.е., по-видимому, неопубликованным как конкретный результат: ^[25] см. введение к этой статье, в котором говорится, что оно «давно известно») имеет важные последствия. Например, он исключает равномерное распределение значений в арифметических прогрессиях по модулю для любого целого числа . $\varphi (n)$ $q$ $q>1$

Для каждого фиксированного положительного целого числа это соотношение справедливо почти для всех , то есть для всех, кроме значений as . $q$ $q|\varphi (n)$ $n$ $o(x)$ $n\leq x$ $x\rightarrow \infty$

Это элементарное следствие того факта, что сумма обратных чисел простых чисел, совпадающих с 1 по модулю , расходится, что само по себе является следствием доказательства теоремы Дирихле об арифметических прогрессиях . $q$

Генерирующие функции

Ряд Дирихле для $φ (n)$ можно записать через дзета-функцию Римана как: ^[26]

\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}

где левая часть сходится при . $\Re (s)>2$

Производящая функция ряда Ламберта равна [ ^27]

\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}

который сходится для $| д | < 1$ .

Оба они доказываются манипуляциями с элементарными рядами и формулами для $φ (n)$ .

Темпы роста

По словам Харди и Райта, порядок $φ (n)$ «всегда «почти $n$ ». ^[28]

Первый ^[29]

\lim \sup {\frac {\varphi (n)}{n}}=1,

но при стремлении n к бесконечности ^[30] для всех $δ > 0$

{\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .

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

Действительно, при доказательстве второй формулы выполнено неравенство

{\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,

верно для $n > 1$ , доказано.

У нас также есть ^[20]

\lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.

Здесь $γ$ — постоянная Эйлера , $γ = 0,577215665...$ , поэтому $e γ = 1,7810724...$ и $e - γ = 0,56145948...$ .

Для доказательства этого не требуется теорема о простых числах . ^[31]^[32] Поскольку $log log n$ стремится к бесконечности, эта формула показывает, что

\lim \inf {\frac {\varphi (n)}{n}}=0.

На самом деле, правда больше. ^[33]^[34]^[35]

\varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2

\varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.

Второе неравенство было показано Жаном-Луи Николя . Рибенбойм говорит: «Метод доказательства интересен тем, что неравенство сначала показывается в предположении, что гипотеза Римана верна, а во-вторых, в противоположном предположении». ^[35]^{: 173}

Для среднего порядка имеем ^[22]^[36]

\varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,

принадлежит Арнольду Вальфису , доказательство с использованием оценок экспоненциальных сумм принадлежит И. М. Виноградову и Н. М. Коробову . Комбинируя методы Ван дер Корпута и Виноградова, Х.-К. Лю (О функции Эйлера. Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), № 4, 769–775) улучшил член ошибки до

O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)

(на данный момент это самая известная оценка такого типа). «Большой О » обозначает величину, которая ограничена константой, умноженной на функцию $n$ внутри круглых скобок (которая мала по сравнению с $n 2$ ).

Этот результат можно использовать для доказательства ^[37] , что вероятность того, что два случайно выбранных числа окажутся относительно простыми, равна6/ $π$ ².

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

В 1950 году Сомаяджулу доказал ^[38]^[39]

{\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}

В 1954 г. Шинцель и Серпинский усилили это утверждение, доказав ^[38]^[39] , что множество

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

плотно в положительных действительных числах. Они также доказали ^[38] , что множество

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

плотно в интервале (0,1).

Тотентные числа

Тотент -число — это значение тотент-функции Эйлера: то есть $m$ , для которого существует хотя бы одно $n$ , для которого $φ (n) = m$ . Валентность или кратность общего числа m $—$ это количество решений этого уравнения. ^[40] Нетонциентное число — это натуральное число, которое не является тотентным числом. Каждое нечетное целое число, превышающее 1, тривиально является нетотиентом. Существует также бесконечно много четных нетоентов ^[41] , и действительно, каждое положительное целое число имеет кратное, которое является четным нетоентом. ^[42]

Число тотентных чисел до заданного предела $x$ равно

{\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}

для константы $C = 0,8178146...$ . ^[43]

Если считать в соответствии с кратностью, количество общих чисел до заданного предела $x$ равно

{\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)

где член ошибки $R$ имеет порядок не более $Икс / (логарифм x) k$ для любого положительного $k$ . ^[44]

Известно, что кратность $m$ бесконечно часто превышает $m δ$ для любого $δ < 0,55655$ . ^[45]^[46]

Теорема Форда

Форд (1999) доказал, что для каждого целого числа $k \geq 2$ существует общее число $m$ кратности $k$ : то есть, для которого уравнение $φ (n) = m$ имеет ровно $k$ решений; этот результат ранее был высказано Вацлавом Серпинским ^[47] и получен как следствие гипотезы Шинцеля H . ^[43] Действительно, каждая возникающая множественность происходит бесконечно часто. ^[43]^[46]

Однако число $m$ с кратностью $k = 1$ неизвестно . Гипотеза Кармайкла о полной функции — это утверждение, что такого $m$ не существует . ^[48]

Идеальные числа

Совершенное числовое число — это целое число, равное сумме его повторяющихся частей. То есть мы применяем функцию totient к числу n , применяем ее снова к полученному totient и так далее, пока не будет достигнуто число 1, и складываем полученную последовательность чисел; если сумма равна n , то n — совершенное число.

Приложения

Циклопомия

В последнем разделе «Рассуждений »^[49]^[50] Гаусс доказывает ^[51] , что правильный $n$ -угольник можно построить с помощью линейки и циркуля, если $φ (n)$ является степенью 2. Если $n$ является степенью нечетного числа простое число, формула для тотента говорит, что его тотент может быть степенью двойки, только если $n$ является первой степенью, а $n - 1$ является степенью 2. Простые числа, которые на единицу больше, чем степень 2, называются простыми числами Ферма , и известны только пять: 3, 5, 17, 257 и 65537. Ферма и Гаусс знали о них. Никто не смог доказать, есть ли еще.

Таким образом, правильный $n$ -угольник имеет конструкцию циркуля и линейки, если n является произведением различных простых чисел Ферма и любой степени двойки. Первые несколько таких $n$ равны ^[52]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (последовательность A003401 в OEIS ) .

Теорема о простых числах для арифметических прогрессий

Криптосистема RSA

Настройка системы RSA включает выбор больших простых чисел $p$ и $q$ , вычисление $n = pq$ и $k = φ (n)$ и поиск двух чисел $e$ и $d$ таких, что $ed \equiv 1 (mod k)$ . Числа $n$ и $e$ («ключ шифрования») публикуются, а $d$ («ключ дешифрования») остается конфиденциальным.

Сообщение, представленное целым числом $m$ , где $0 < m < n$ , шифруется путем вычисления $S = m e (mod n)$ .

Он расшифровывается путем вычисления $t = S d (mod n)$ . Теорему Эйлера можно использовать, чтобы показать, что если $0 < t < n$ , то $t = m$ .

Безопасность системы RSA была бы поставлена под угрозу, если бы число $n$ можно было эффективно разложить на множители или если $φ (n)$ можно было бы эффективно вычислить без факторизации $n$ .

Нерешенные проблемы

Гипотеза Лемера

Если $p$ простое число, то $φ (p) = p - 1$ . В 1932 году Д. Х. Лемер спросил, существуют ли составные числа $n$ такие, что $φ (n)$ делит $n -1$ . Ни один из них не известен. ^[53]

В 1933 году он доказал, что если такое $n$ существует, то оно должно быть нечетным, свободным от квадратов и делиться как минимум на семь простых чисел (т.е. $ω (n) \geq 7$ ). В 1980 году Коэн и Хагис доказали, что $n > 10 20$ и что $ω (n) \geq 14$ . ^[54] Кроме того, Хагис показал, что если 3 делит $n$ , то $n > 10 1937042$ и $ω (n) \geq 298848$ . ^[55]^[56]

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

Это означает, что не существует числа $n$ , обладающего свойством, которое для всех других чисел $m$ , $m \neq n$ , $φ (m) \neq φ (n)$ . См. теорему Форда выше.

Как сказано в основной статье, если существует единственный контрпример к этой гипотезе, то контрпримеров должно быть бесконечно много, и самый маленький из них имеет не менее десяти миллиардов цифр по основанию 10. ^[40]

Гипотеза Римана

Гипотеза Римана верна тогда и только тогда, когда выполнено неравенство

{\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}

верно для всех $n \geq p 120569 #$ , где $γ$ — константа Эйлера , а $p 120569 #$ — произведение первых $120569$ простых чисел. ^[57]

Смотрите также

Примечания

^ "Тотентная функция Эйлера" . Ханская академия . Проверено 26 февраля 2016 г.
^ Лонг (1972, стр. 85)
^ Петтофреззо и Биркит (1970, стр. 72)
^ Лонг (1972, стр. 162)
^ Петтофреззо и Биркит (1970, стр. 80)
^ См. теорему Эйлера.
^ Л. Эйлер «Theoremata arithmetica nova Methodo Demonstrata» (Арифметическая теорема, доказанная новым методом), Novi commentarii academiae scientiarum Imperialis Petropolitanae (Новые мемуары Санкт-Петербургской Императорской Академии наук), 8 (1763), 74–104 . (Работа была представлена в Петербургской Академии 15 октября 1759 года. Одноименная работа была представлена в Берлинской Академии 8 июня 1758 года). Доступно в Интернете: Фердинанд Рудио , изд. , Leonhardi Euleri Commentationes Arithmeticae , том 1, в: Leonhardi Euleri Opera Omnia , серия 1, том 2 (Лейпциг, Германия, Б. Г. Тойбнер, 1915), страницы 531–555. На странице 531 Эйлер определяет $n$ как количество целых чисел, меньших $N$ и взаимно простых с $N$ (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), что является фи функция φ(N).
^ аб Сандифер, с. 203
^ Грэм и др. п. 133 примечание 111
^ Л. Эйлер, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), стр. 18–30, или Opera Omnia, серия 1, том 4, стр. 105–115. (Работа была представлена в Петербургской Академии 9 октября 1775 г.).
^ И $φ (n)$ , и $φ (n)$ встречаются в литературе. Это две формы строчной греческой буквы фи .
^ Гаусс, Disquisitiones Arithmeticae, статья 38
^ Каджори, Флориан (1929). История математических обозначений, том II . Издательство «Открытый суд». §409.
^ Дж. Дж. Сильвестр (1879) «О некоторых троичных уравнениях кубической формы», Американский журнал математики , 2 : 357-393; Сильвестр вводит термин «тотиент» на странице 361.
Ссылки _ Оксфордский словарь английского языка (2-е изд.). Издательство Оксфордского университета . 1989.
^ Шрамм (2008)
^ Гаусс, Д.А., арт 39.
^ Гаусс, Д.А. ст. 39, ст. 52-54
^ Грэм и др. стр. 134-135
^ ab Hardy & Wright 1979, thm. 328
^ Динева (во внешних ссылках), подп. 1
^ abc Уолфиш, Арнольд (1963). Экспоненциальные суммы Вейля в neueren Zahlentheorie . Mathematische Forschungsberichte (на немецком языке). Том. 16. Берлин: VEB Deutscher Verlag der Wissenschaften . Збл 0146.06003.
^ Ломадсе, Г. (1964), «Научная работа Арнольда Уолфиса» (PDF) , Acta Arithmetica , 10 (3): 227–237, doi : 10.4064/aa-10-3-227-237
^ аб Ситарамачандрарао, Р. (1985). «Об ошибочном термине Ландау II». Роки Маунтин Дж. Математика . 15 (2): 579–588. дои : 10.1216/RMJ-1985-15-2-579 .
^ Поллак, П. (2023), «Две задачи о распределении лямбда-функции Кармайкла», Mathematika , 69 : 1195–1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222
^ Харди и Райт 1979, thm. 288
^ Харди и Райт 1979, thm. 309
^ Харди и Райт 1979, введение к § 18.4.
^ Харди и Райт 1979, thm. 326
^ Харди и Райт 1979, thm. 327
^ Фактически, теорема Чебышева (Hardy & Wright 1979, thm.7) и третья теорема Мертенса — это все, что нужно.
^ Харди и Райт 1979, thm. 436
^ Теорема 15 Россера, Дж. Баркли; Шенфельд, Лоуэлл (1962). «Приближенные формулы для некоторых функций простых чисел». Иллинойс Дж. Математика . 6 (1): 64–94. дои : 10.1215/ijm/1255631807 .
^ Бах и Шалит, thm. 8.8.7
^ аб Рибенбойм (1989). «Как распределяются простые числа? §IC Распределение значений функции Эйлера». Книга рекордов простых чисел (2-е изд.). Нью-Йорк: Springer-Verlag. стр. 172–175. дои : 10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5.
^ Шандор, Митринович и Крстичи (2006), стр. 24–25.
^ Харди и Райт 1979, thm. 332
^ abc Рибенбойм, стр.38
^ аб Шандор, Митринович и Крстичи (2006), стр.16
^ Аб Гай (2004) стр.144
^ Шандор и Крстичи (2004) стр.230
^ Чжан, Минчжи (1993). «О нетотентах». Журнал теории чисел . 43 (2): 168–172. дои : 10.1006/jnth.1993.1014 . ISSN 0022-314X. Збл 0772.11001.
^ abc Форд, Кевин (1998). «Распределение вещей». Рамануджан Дж . Развитие математики. 2 (1–2): 67–151. arXiv : 1104.3264 . дои : 10.1007/978-1-4757-4507-8_8. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Збл 0914.11053.
^ Шандор и др. (2006) стр.22
^ Шандор и др. (2006) стр.21
^ Аб Гай (2004) стр.145
^ Шандор и Крстичи (2004) стр.229
^ Шандор и Крстичи (2004) стр.228
^ Гаусс, Д.А. 7-й § – искусство. 336–366
^ Гаусс доказал, что если $n$ удовлетворяет определенным условиям, то $n$ -угольник можно построить. В 1837 году Пьер Ванцель доказал обратное: если $n$ -угольник конструктивен, то $n$ должно удовлетворять условиям Гаусса.
^ Гаусс, Д.А., арт 366.
^ Гаусс Д.А., ст. 366. Этот список является последним предложением в «Рассуждениях» .
^ Рибенбойм, стр. 36–37.
^ Коэн, Грэм Л.; Хагис, Питер младший (1980). «О количестве простых делителей числа $n$ , если $φ$ $($ $n$ $)$ делит $n$ $- 1$ ». Нью-Арк. Вискд . III серия. 28 : 177–185. ISSN 0028-9825. Збл 0436.10002.
^ Хагис, Питер младший (1988). «Об уравнении $M$ $\cdotφ($ $n$ $) =$ $n$ $- 1$ ». Нью-Арк. Вискд . IV серия. 6 (3): 255–261. ISSN 0028-9825. Збл 0668.10006.
^ Гай (2004) стр.142
^ Броган, Кевин (2017). Эквиваленты гипотезы Римана, Том первый: Арифметические эквиваленты (Первое изд.). Издательство Кембриджского университета. ISBN 978-1-107-19704-6.Следствие 5.35.

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

«Тотиент-функция», Математическая энциклопедия , EMS Press , 2001 [1994]
Фи-функция Эйлера и китайская теорема об остатках - доказательство того, что φ(n) мультипликативна
Калькулятор функции Эйлера на JavaScript — до 20 цифр
Динева, Росика, коэффициент Эйлера, Мёбиуса и функции делителя.
Плитейдж, Лумис, Полхилл суммируют фи-функцию Эйлера