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

«φ(n)» перенаправляется сюда. Чтобы узнать о других значениях, см. Phi . Не путать с функцией Эйлера .

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

В чисел теории функция тотента Эйлера подсчитывает положительные целые числа до заданного целого числа n, которые являются относительно простыми с n . Оно пишется греческой буквой фи как $\varphi (n)$ или $\phi (n)$, а также может быть названа фи-функцией Эйлера . Другими словами, это количество целых чисел k в диапазоне 1 ≤ k ≤ n , для которых наибольший общий делитель НОД( n , k ) равен 1. Целые числа k этой формы иногда называют совокупными n числами .

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

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

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

Леонард Эйлер ввел эту функцию в 1763 году. Однако в то время он не выбрал для его обозначения какого-либо конкретного символа. В публикации 1784 года Эйлер изучил функцию дальше, выбрав для ее обозначения греческую букву π : он написал πD для «множества чисел, меньших D и не имеющих с ним общего делителя». Это определение отличается от текущего определения функции тотента при D = 1, но в остальном остается тем же. Теперь стандартные обозначения φ ( A ) взято из трактата Гаусса 1801 года «Арифметические рассуждения» : хотя Гаусс не стал заключать аргумент в круглые скобки и написал φA . Поэтому ее часто называют фи-функцией Эйлера или просто фи-функцией .

В 1879 году Дж. Дж. Сильвестр термин 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}}$ является основной факторизацией $n$ (то есть, $p_{1},p_{2},\ldots ,p_{r}$ являются различными простыми числами).

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

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

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

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

Если p простое число и k ≥ 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 — простое число, единственные возможные значения gcd( p ^к , m ) равны 1, p , p ² , ..., п ^к и единственный способ получить gcd( p ^к , m ) > 1 , если m кратно p , то есть m ∈ { p , 2 p , 3 p , ..., p ^{к - 1} р = р ^к } , и есть p ^{к - 1} такие кратные не превосходят p ^к . Следовательно, другой п ^к − п ^{к - 1} все числа относительно просты с p ^к .

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

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

${\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. Позволять

${\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 ∈ {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 , чего в любом случае достаточно для факторизации.

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

Свойство, установленное Гауссом, что

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

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

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

Формулу также можно вывести из элементарной арифметики. Например, пусть 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}}$

Все эти двадцать дробей положительные. ⁠ k / d ⁠ ≤ 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}},$

где µ — функция Мёбиуса , мультипликативная функция , определяемая формулой $\mu (p)=-1$ и $\mu (p^{k})=0$ для каждого простого числа p и k ≥ 2 . Эту формулу также можно получить из формулы произведения путем умножения ${\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 ) показаны в таблице и на графике ниже:

График первых 100 значений

φ ( n ) для 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	16	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	16	20	16	24	12	36	18	24	16
40	40	12	42	20	24	22	46	16	42	20
50	32	24	52	18	40	24	36	28	58	16
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

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

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

Основная статья: теорема Эйлера

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

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

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

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

Криптосистема RSA основана на этой теореме: из нее следует, что обратная функция a ↦ a ^и mod n , где e — (публичный) показатель шифрования, — это функция b ↦ b ^д 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 ≥ 3 .

  Более того, если n имеет r различных нечетных простых делителей, 2 ^р | φ ( п )

• Для любых a > 1 и n > 6 таких, что 4 ∤ n, существует l ≥ 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)}}$ 
• $\sum _{1\leq k\leq n-1 \atop gcd(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)$ ( цитируется в )
• $\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)$ [Лю (2016)]
• $\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)$ 
• $\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)$ 
• $\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)$ 

  (где γ — постоянная Эйлера–Машерони ).

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

Основная статья: Личность Менона

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Темпы роста

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

Первый

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

но когда n стремится к бесконечности, для всех δ > 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 , доказано.

У нас также есть

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

Здесь γ — постоянная Эйлера , γ = 0,577215665... , поэтому e ^с = 1,7810724... и е ^{− с} = 0.56145948... .

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

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

На самом деле, правда больше.

$\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.$

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

Для среднего заказа у нас есть

$\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 ² ).

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

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

В 1950 году Сомаяджулу доказал

${\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 году Шинцель и Серпинский усилили это, доказав что набор

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

плотно . в положительных действительных числах Они также доказали что набор

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

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

Так много цифр

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

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

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

для константы C = 0,8178146... .

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

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

где член ошибки R имеет порядок не более ⁠ х / (логарифм х ) ^к ⁠ для любого положительного k .

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

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

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

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

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

Основная статья: Идеальное число

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

Приложения

Циклопомия

Основная статья: Сборный многоугольник

В последнем разделе Disquisitiones Гаусс доказывает что правильный n -угольник можно построить с помощью линейки и циркуля, если φ ( n ) является степенью 2. Если n является степенью нечетного простого числа, формула для тотента говорит, что его тотент может быть степенью двойки, только если n — первая степень, а n − 1 — степень 2. Простые числа, которые на единицу больше степени 2, называются простыми числами Ферма , и известны только пять: 3, 5, 17, 257 и 65537. Ферма и Гаусс знал об этом. Никто не смог доказать, есть ли еще.

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

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

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

Основная статья: Теорема о простых числах § Теорема о простых числах для арифметических прогрессий

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

Основная статья: RSA (алгоритм)

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

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

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

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

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

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

Основная статья: проблема Лемера

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

В 1933 году он доказал, что если такое n существует, то оно должно быть нечетным, свободным от квадратов и делиться как минимум на семь простых чисел (т.е. ω ( n ) ≥ 7 ). В 1980 году Коэн и Хагис доказали, что n > 10. ²⁰ и что ω ( n ) ≥ 14 . Далее Хагис показал, что если 3 делит n , то n > 10. ^1937042 и ω ( n ) ≥ 298848 .

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

Основная статья: Гипотеза Кармайкла о полной функции

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

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

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

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

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

верно для всех n ≥ p ₁₂₀₅₆₉ # , где γ — константа Эйлера , а p ₁₂₀₅₆₉ # — произведение первых 120569 простых чисел.

См. также

• Функция Кармайкла (λ)
• Пси-функция Дедекинда (𝜓)
• Функция делителя (σ)

• Гипотеза Даффина – Шеффера
• Обобщения малой теоремы Ферма.
• Высоко составное число

• Мультипликативная группа целых чисел по модулю n
• Сумма Рамануджана
• Сумматорная функция Тотента (𝛷)

Ссылки

Disquisitiones Arithmeticae переведена с латыни на английский и немецкий языки. Немецкое издание включает все статьи Гаусса по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратной взаимности и неопубликованные заметки.

Ссылки на Disquisitiones имеют форму Gauss, DA, art. ннн .

• Абрамовиц, М .; Стегун, И.А. (1964), Справочник по математическим функциям , Нью-Йорк: Dover Publications , ISBN  0-486-61272-4 . См. параграф 24.3.2.
• Бах, Эрик ; Шалит, Джеффри (1996), Алгоритмическая теория чисел (Том I: Эффективные алгоритмы) , Серия MIT Press по основам вычислений, Кембридж, Массачусетс: MIT Press , ISBN  0-262-02405-5 , Збл   0873.11070
• Диксон, Леонард Юджин, «История теории чисел», том 1, глава 5 «Функция Эйлера, обобщения; ряд Фарея», Chelsea Publishing, 1952 г.
• Форд, Кевин (1999), «Число решений φ( x ) = m », Annals of Mathematics , 150 (1): 283–311, doi : 10.2307/121103 , ISSN   0003-486X , JSTOR   121103 , MR   1715326 , Збл   0978.11053 .
• Гаусс, Карл Фридрих (1986), Disquisitiones Arithmeticae (второе, исправленное издание) , перевод Кларка, Артура А., Нью-Йорк: Springer , ISBN  0-387-96254-9
• Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике (второе издание) , перевод Мазера Х., Нью-Йорк: Челси, ISBN  0-8284-0191-8
• Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994), Конкретная математика : основа информатики (2-е изд.), Ридинг, Массачусетс: Аддисон-Уэсли, ISBN  0-201-55802-5 , Збл   0836.00001
• Гай, Ричард К. (2004), Нерешенные проблемы теории чисел , Сборники задач по математике (3-е изд.), Нью-Йорк, Нью-Йорк: Springer-Verlag , ISBN  0-387-20860-7 , Збл   1058.11001
• Харди, штат Джорджия ; Райт, Э.М. (1979), Введение в теорию чисел (пятое изд.), Оксфорд: Oxford University Press , ISBN  978-0-19-853171-5
• Лю, H.-Q. (2016), «О функции Эйлера», Тр. Рой. Соц. Эдинбургская секта. А , 146 (4) .
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN   77-171950
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN   77-81766
• Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел (3-е изд.), Нью-Йорк: Springer , ISBN  0-387-94457-5 , Збл   0856.11001
• Сандифер, Чарльз (2007), Ранняя математика Леонарда Эйлера , MAA, ISBN  978-0-88385-559-1
• Шандор, Джозеф; Митринович, Драгослав С.; Крстичи, Борислав, ред. (2006), Справочник по теории чисел I , Дордрехт: Springer-Verlag , стр. 9–36, ISBN  1-4020-4215-9 , Збл   1151.11300
• Шандор, Джозеф; Крстичи, Борислав (2004). Справочник по теории чисел II . Дордрехт: Клювер Академик. стр. 179 –327. ISBN  1-4020-2546-7 . Збл   1079.11001 .
• Шрамм, Вольфганг (2008), «Преобразование Фурье функций наибольшего общего делителя» , Электронный журнал комбинаторной теории чисел , A50 (8 (1)) .

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

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