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

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

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

Например, тотативы числа 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 ) . [4] [5] Эта функция определяет порядок мультипликативной группы целых чисел по модулю n ( группы единиц кольца ) . [6] Она также используется для определения системы шифрования RSA . З / н З {\displaystyle \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 году Дж. Дж. Сильвестр ввел термин тотиент для этой функции, [14] [15] поэтому ее также называют функцией тотиента Эйлера , тотиентом Эйлера или тотиентом Эйлера . Тотиент Жордана является обобщением тотиента Эйлера.

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

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

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

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

В нем говорится:

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

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

Эквивалентная формулировка имеет вид: где — разложение на простые множители (то есть — различные простые числа). φ ( н ) = п 1 к 1 1 ( п 1 1 ) п 2 к 2 1 ( п 2 1 ) п г к г 1 ( п г 1 ) , {\displaystyle \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),} н = п 1 к 1 п 2 к 2 п г к г {\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}} н {\displaystyle n} п 1 , п 2 , , п г {\displaystyle p_{1},p_{2},\ldots ,p_{r}}

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

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

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

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

Если p — простое число и k ≥ 1 , то

φ ( п к ) = п к п к 1 = п к 1 ( п 1 ) = п к ( 1 1 п ) . {\displaystyle \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 k , m ) являются 1, p , p 2 , ..., p k , и единственный способ получить gcd( p k , m ) > 1 — это если m кратно p , то есть m ∈ { p , 2 p , 3 p , ..., p k − 1 p = p k } , и существует p k − 1 таких кратных, не больших p k . Следовательно, все остальные числа p kp k − 1 взаимно просты с p k .

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

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

φ ( н ) = φ ( п 1 к 1 ) φ ( п 2 к 2 ) φ ( п г к г ) = п 1 к 1 ( 1 1 п 1 ) п 2 к 2 ( 1 1 п 2 ) п г к г ( 1 1 п г ) = п 1 к 1 п 2 к 2 п г к г ( 1 1 п 1 ) ( 1 1 п 2 ) ( 1 1 п г ) = н ( 1 1 п 1 ) ( 1 1 п 2 ) ( 1 1 п г ) . {\displaystyle {\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 , , н } {\displaystyle \{1,2,\ldots ,n\}}

Пример

φ ( 20 ) = φ ( 2 2 5 ) = 20 ( 1 1 2 ) ( 1 1 5 ) = 20 1 2 4 5 = 8. {\displaystyle \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.

Альтернативная формула использует только целые числа: φ ( 20 ) = φ ( 2 2 5 1 ) = 2 2 1 ( 2 1 ) 5 1 1 ( 5 1 ) = 2 1 1 4 = 8. {\displaystyle \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] Пусть

Ф { х } [ м ] = к = 1 н х к е 2 π я м к н {\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}

где x k = gcd( k , n ) для k ∈ {1, ..., n } . Тогда

φ ( н ) = Ф { х } [ 1 ] = к = 1 н gcd ( к , н ) е 2 π я к н . {\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}

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

φ ( н ) = к = 1 н gcd ( к , н ) потому что 2 π к н . {\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.}

Например, используя и : В отличие от произведения Эйлера и формулы суммы делителей, эта не требует знания множителей n . Однако она включает вычисление наибольшего общего делителя n и каждого положительного целого числа, меньшего n , чего в любом случае достаточно для факторизации. cos π 5 = 5 + 1 4 {\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}} cos 2 π 5 = 5 1 4 {\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}} φ ( 10 ) = gcd ( 1 , 10 ) cos 2 π 10 + gcd ( 2 , 10 ) cos 4 π 10 + gcd ( 3 , 10 ) cos 6 π 10 + + gcd ( 10 , 10 ) cos 20 π 10 = 1 ( 5 + 1 4 ) + 2 ( 5 1 4 ) + 1 ( 5 1 4 ) + 2 ( 5 + 1 4 ) + 5 ( 1 ) +   2 ( 5 + 1 4 ) + 1 ( 5 1 4 ) + 2 ( 5 1 4 ) + 1 ( 5 + 1 4 ) + 10 ( 1 ) = 4. {\displaystyle {\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}}}

Сумма делителей

Установленное Гауссом свойство [17] заключается в том, что

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

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

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

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

1 20 , 2 20 , 3 20 , 4 20 , 5 20 , 6 20 , 7 20 , 8 20 , 9 20 , 10 20 , 11 20 , 12 20 , 13 20 , 14 20 , 15 20 , 16 20 , 17 20 , 18 20 , 19 20 , 20 20 . {\displaystyle {\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}}.}

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

1 20 , 1 10 , 3 20 , 1 5 , 1 4 , 3 10 , 7 20 , 2 5 , 9 20 , 1 2 , 11 20 , 3 5 , 13 20 , 7 10 , 3 4 , 4 5 , 17 20 , 9 10 , 19 20 , 1 1 {\displaystyle {\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.

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

φ ( n ) = d n μ ( d ) n d = n d n μ ( d ) d , {\displaystyle \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 ≥ 2. Эту формулу можно также вывести из формулы произведения, умножив ее, чтобы получить μ ( p ) = 1 {\displaystyle \mu (p)=-1} μ ( p k ) = 0 {\displaystyle \mu (p^{k})=0} p n ( 1 1 p ) {\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})} d n μ ( d ) d . {\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}

Пример: φ ( 20 ) = μ ( 1 ) 20 + μ ( 2 ) 10 + μ ( 4 ) 5 + μ ( 5 ) 4 + μ ( 10 ) 2 + μ ( 20 ) 1 = 1 20 1 10 + 0 5 1 4 + 1 2 + 0 1 = 8. {\displaystyle {\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
+12345678910
01122426464
1010412688166188
20121022820121812288
3030162016241236182416
4040124220242246164220
5032245218402436285816
6060303632482066324424
7070247236403660247832
8054408224644256408824
9072446046723296426040

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

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

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

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

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

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

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

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

  • a b φ ( a ) φ ( b ) {\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}
  • m φ ( a m 1 ) {\displaystyle m\mid \varphi (a^{m}-1)}
  • φ ( m n ) = φ ( m ) φ ( n ) d φ ( d ) where  d = gcd ( m , n ) {\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}

    В частности:

    • φ ( 2 m ) = { 2 φ ( m )  if  m  is even φ ( m )  if  m  is odd {\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}
    • φ ( n m ) = n m 1 φ ( n ) {\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}
  • φ ( lcm ( m , n ) ) φ ( gcd ( m , n ) ) = φ ( m ) φ ( n ) {\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}

    Сравните это с формулой (см. наименьшее общее кратное ). lcm ( m , n ) gcd ( m , n ) = m n {\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}

  • φ ( n ) четно для n ≥ 3 .

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

  • Для любых a > 1 и n > 6 , таких что 4 ∤ n, существует l ≥ 2 n, такое что l | φ ( a n − 1) .
  • φ ( n ) n = φ ( rad ( n ) ) rad ( n ) {\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}

    где rad( n )радикал числа n (произведение всех различных простых чисел, делящих n ).

  • d n μ 2 ( d ) φ ( d ) = n φ ( n ) {\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}  [21]
  • 1 k n 1 g c d ( k , n ) = 1 k = 1 2 n φ ( n ) for  n > 1 {\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}
  • k = 1 n φ ( k ) = 1 2 ( 1 + k = 1 n μ ( k ) n k 2 ) = 3 π 2 n 2 + O ( n ( log n ) 2 3 ( log log n ) 4 3 ) {\displaystyle \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] )
  • k = 1 n φ ( k ) = 3 π 2 n 2 + O ( n ( log n ) 2 3 ( log log n ) 1 3 ) {\displaystyle \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)]
  • k = 1 n φ ( k ) k = k = 1 n μ ( k ) k n k = 6 π 2 n + O ( ( log n ) 2 3 ( log log n ) 4 3 ) {\displaystyle \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]
  • k = 1 n k φ ( k ) = 315 ζ ( 3 ) 2 π 4 n log n 2 + O ( ( log n ) 2 3 ) {\displaystyle \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]
  • k = 1 n 1 φ ( k ) = 315 ζ ( 3 ) 2 π 4 ( log n + γ p  prime log p p 2 p + 1 ) + O ( ( log n ) 2 3 n ) {\displaystyle \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]

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

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

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

gcd ( k , n ) = 1 1 k n gcd ( k 1 , n ) = φ ( n ) d ( n ) , {\displaystyle \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] см. введение к этой статье, в котором оно указано как «давно известное»), имеет важные последствия. Например, оно исключает равномерное распределение значений в арифметических прогрессиях по модулю для любого целого числа . φ ( n ) {\displaystyle \varphi (n)} q {\displaystyle q} q > 1 {\displaystyle q>1}

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

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

Генерация функций

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

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

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

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

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

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

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

Темпы роста

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

Первый [29]

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

но когда n стремится к бесконечности, [30] для всех δ > 0

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

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

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

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

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

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

lim inf φ ( n ) n log log n = e γ . {\displaystyle \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 φ ( n ) n = 0. {\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}

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

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

и

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

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

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

φ ( 1 ) + φ ( 2 ) + + φ ( n ) = 3 n 2 π 2 + O ( n ( log n ) 2 3 ( log log n ) 4 3 ) as  n , {\displaystyle \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 ,}

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

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

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

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

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

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

lim inf φ ( n + 1 ) φ ( n ) = 0 and lim sup φ ( n + 1 ) φ ( n ) = . {\displaystyle {\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] , что множество

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

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

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

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

Числа тотиентов

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

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

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

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

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

| { n : φ ( n ) x } | = ζ ( 2 ) ζ ( 3 ) ζ ( 6 ) x + R ( x ) {\displaystyle {\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 ≥ 2 существует тотиентное число m кратности k : то есть, для которого уравнение φ ( n ) = m имеет ровно k решений; этот результат ранее был выдвинут Вацлавом Серпинским [47] и был получен как следствие гипотезы Шинцеля H. [ 43] Действительно, каждая встречающаяся кратность встречается бесконечно часто. [43] [46]

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

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

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

Приложения

Циклотомия

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

Таким образом, правильный n -угольник имеет конструкцию с помощью циркуля и линейки, если n является произведением различных простых чисел Ферма и любой степени числа 2. Первые несколько таких 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 ≡ 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 ) ≥ 7 ). В 1980 году Коэн и Хагис доказали, что n > 10 20 и что ω ( n ) ≥ 14 . [54] Кроме того, Хагис показал, что если 3 делит n , то n > 10 1937042 и ω ( n ) ≥ 298848 . [55] [56]

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

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

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

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

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

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

верно для всех np 120569 # где γпостоянная Эйлера , а p 120569 #произведение первых 120569 простых чисел. [57]

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

Примечания

  1. ^ "Эйлерова функция тотиента". Khan Academy . Получено 2016-02-26 .
  2. ^ Лонг (1972, стр. 85)
  3. ^ Петтофреццо и Биркит (1970, стр. 72)
  4. ^ Лонг (1972, стр. 162)
  5. ^ Петтофреццо и Биркит (1970, стр. 80)
  6. ^ См. теорему Эйлера.
  7. L. Euler "Theoremata arithmetica nova methodo demonstrata" (Арифметическая теорема, доказанная новым методом), Novi commentarii academiae scientiarum imperialis Petropolitanae (Новые записки Санкт-Петербургской Императорской Академии наук), 8 (1763), 74–104. (Работа была представлена ​​в Санкт-Петербургской Академии 15 октября 1759 года. Работа с тем же названием была представлена ​​в Берлинской Академии 8 июня 1758 года). Доступно в сети в: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , том 1, в: Leonhardi Euleri Opera Omnia , серия 1, том 2 (Лейпциг, Германия, BG Teubner, 1915), страницы 531–555. На странице 531 Эйлер определяет n как количество целых чисел, меньших N и взаимно простых с N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), что является фи-функцией φ(N).
  8. ^ ab Sandifer, стр. 203
  9. ^ Грэм и др., стр. 133, примечание 111.
  10. ^ Л. Эйлер, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), стр. 18–30, или Opera Omnia, серия 1, том 4, стр. 105–115. (Работа была представлена ​​в Петербургской Академии 9 октября 1775 г.).
  11. ^ В литературе встречаются как φ ( n ), так и ϕ ( n ) . Это две формы строчной греческой буквы фи .
  12. ^ Гаусс, Disquisitiones Arithmeticae, статья 38
  13. ^ Каджори, Флориан (1929). История математических обозначений. Том II . Open Court Publishing Company. §409.
  14. ^ Дж. Дж. Сильвестр (1879) «О некоторых уравнениях тернарной кубической формы», American Journal of Mathematics , 2  : 357-393; Сильвестр вводит термин «totient» на странице 361.
  15. ^ "totient". Оксфордский словарь английского языка (2-е изд.). Oxford University Press . 1989.
  16. ^ Шрамм (2008)
  17. ^ Гаусс, DA, ст. 39
  18. ^ Гаусс, Д.А. ст. 39, ст. 52-54
  19. ^ Грэм и др., стр. 134-135.
  20. ^ ab Hardy & Wright 1979, том 328
  21. ^ Динева (во внешних ссылках), предложение 1
  22. ^ abc Уолфиш, Арнольд (1963). Экспоненциальные суммы Вейля в neueren Zahlentheorie . Mathematische Forschungsberichte (на немецком языке). Том. 16. Берлин: VEB Deutscher Verlag der Wissenschaften . Збл  0146.06003.
  23. ^ Ломадсе, Г. (1964), «Научная работа Арнольда Вальфиса» (PDF) , Acta Arithmetica , 10 (3): 227– 237, doi :10.4064/aa-10-3-227-237
  24. ^ ab Sitaramachandrarao, R. (1985). «Об ошибке члена Ландау II». Rocky Mountain J. Math . 15 (2): 579– 588. doi : 10.1216/RMJ-1985-15-2-579 .
  25. ^ Поллак, П. (2023), «Две проблемы распределения лямбда-функции Кармайкла», Mathematika , 69 (4): 1195– 1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222
  26. Харди и Райт 1979, том 288.
  27. Харди и Райт 1979, том 309.
  28. Харди и Райт 1979, введение к § 18.4.
  29. ^ Харди и Райт 1979, том 326
  30. Харди и Райт 1979, том 327.
  31. ^ Фактически, теорема Чебышева (Hardy & Wright 1979, thm.7) и третья теорема Мертенса — это все, что нужно.
  32. Харди и Райт 1979, том 436.
  33. Теорема 15 Россера, Дж. Баркли; Шенфельда, Лоуэлла (1962). «Приближенные формулы для некоторых функций простых чисел». Illinois J. Math . 6 (1): 64– 94. doi : 10.1215/ijm/1255631807 .
  34. ^ Бах и Шаллит, том 8.8.7
  35. ^ ab Ribenboim (1989). «Как распределены простые числа? §IC Распределение значений функции Эйлера». Книга рекордов простых чисел (2-е изд.). Нью-Йорк: Springer-Verlag. С.  172– 175. doi :10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5.
  36. ^ Шандор, Митринович и Крстичи (2006), стр. 24–25.
  37. Харди и Райт 1979, том 332.
  38. ^ abc Рибенбойм, стр.38
  39. ^ аб Шандор, Митринович и Крстичи (2006), стр.16
  40. ^ ab Guy (2004) стр.144
  41. ^ Шандор и Крстичи (2004) стр.230
  42. ^ Чжан, Минчжи (1993). «О не-тотиентах». Журнал теории чисел . 43 (2): 168– 172. doi : 10.1006/jnth.1993.1014 . ISSN  0022-314X. Zbl  0772.11001.
  43. ^ abc Ford, Kevin (1998). «Распределение тотиентов». Ramanujan J . 2 ( 1– 2): 67– 151. doi :10.1023/A:1009761909132. ISSN  1382-4090. Zbl  0914.11053.Перепечатано в Analytic and Elementary Number Theory: A Tribute to Mathematical Legend Paul Erdos , Developments in Mathematics, т. 1, 1998, doi :10.1007/978-1-4757-4507-8_8, ISBN 978-1-4419-5058-1 . Обновлено и исправлено в arXiv :1104.3264, 2011. 
  44. ^ Шандор и др. (2006) стр.22
  45. ^ Шандор и др. (2006) стр.21
  46. ^ ab Guy (2004) стр.145
  47. ^ Шандор и Крстичи (2004) стр.229
  48. ^ Шандор и Крстичи (2004) стр.228
  49. ^ Гаусс, ДА. 7-й § — это статьи 336–366.
  50. ^ Гаусс доказал, что если n удовлетворяет определенным условиям, то n -угольник может быть построен. В 1837 году Пьер Ванцель доказал обратное: если n -угольник конструируем, то n должно удовлетворять условиям Гаусса
  51. ^ Гаусс, DA, ст. 366
  52. ^ Гаусс, DA, ст. 366. Этот список является последним предложением в Disquisitiones
  53. Рибенбойм, стр. 36–37.
  54. ^ Коэн, Грэм Л.; Хагис, Питер младший (1980). «О количестве простых делителей числа n , если φ ( n ) делит n − 1 ». Нью-Арк. Вискд . III серия. 28 : 177–185 . ISSN  0028-9825. Збл  0436.10002.
  55. ^ Хагис, Питер младший (1988). «Об уравнении M ·φ( n ) = n − 1 ». Нью-Арк. Вискд . IV серия. 6 (3): 255–261 . ISSN  0028-9825. Збл  0668.10006.
  56. ^ Гай (2004) стр.142
  57. ^ Броган, Кевин (2017). Эквиваленты гипотезы Римана, том первый: арифметические эквиваленты (первое издание). Cambridge University Press. ISBN 978-1-107-19704-6.Следствие 5.35

Ссылки

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

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

  • "Функция Totient", Энциклопедия математики , EMS Press , 2001 [1994]
  • Фи-функция Эйлера и китайская теорема об остатках — доказательство того, что φ(n) мультипликативна. Архивировано 28.02.2021 на Wayback Machine
  • Калькулятор функции тотиента Эйлера на JavaScript — до 20 цифр
  • Динева, Росица, Эйлеров тотиент, Мёбиус и функции делителей Архивировано 2021-01-16 на Wayback Machine
  • Плитадж, Лумис, Полхилл подводят итоги по функции Эйлера Фи
Retrieved from "https://en.wikipedia.org/w/index.php?title=Euler%27s_totient_function&oldid=1268962551"