Как найти значение функции эйлера – Сайт, где вы сможете решить свои вопросы

Первая тысяча значений $varphi (n)$

Фу́нкция Э́йлера $varphi (n)$ — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных $n$ и взаимно простых с ним^[1].

Например, для числа 36 существует 12 меньших его и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), поэтому ${displaystyle varphi (36)=12}$ .

Названа в честь Эйлера, который впервые использовал её в 1763 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования», вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение $varphi (n)$ ^[2].

Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов (см. сравнение по модулю), теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA^[3].

Вычисление[править | править код]

Первые 99 значений функции Эйлера^[4]

$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

Общие сведения[править | править код]

Функция Эйлера $varphi (n)$ показывает, сколько натуральных чисел из отрезка $[1,;n-1]$ имеют c $n$ только один общий делитель — единицу. Функция Эйлера определена на множестве натуральных чисел, и значения её лежат во множестве натуральных чисел.

Как следует из определения, чтобы вычислить $varphi (n)$ , нужно перебрать все числа от $1$ до $n-1$ , и для каждого проверить, имеет ли оно общие делители с $n$ , а затем подсчитать, сколько чисел оказались взаимно простыми с $n$ . Эта процедура для больших чисел $n$ весьма трудоёмка, поэтому для вычисления $varphi (n)$ используют другие методы, которые основываются на специфических свойствах функции Эйлера.

В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение $varphi (n)$ не превосходит $n-1$ , и в точности ему равно, если $n$ — простое. Таким образом, если в координатах $(n,;y)$ провести прямую $y=n-1$ , то значения $y=varphi(n)$ будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения $varphi (n)$ снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число $n$ , такое, что $varphi (n)$ лежит ниже этой прямой. Ещё одной интересной особенностью графика является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой $y=n-1$ , на которой лежат значения $varphi(n)=n-1$ , где $n$ — простое, выделяется прямая, примерно соответствующая $y=n/2$ , на которую попадают значения $varphi(2n)=varphi(n)=n-1$ , где $n$ — простое.

Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.

Мультипликативность функции Эйлера[править | править код]

Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел $m$ и $n$ ^[5]

$varphi(mn)=varphi(m)varphi(n).$

Доказательство мультипликативности

Функция Эйлера от простого числа[править | править код]

Для простого $p$ значение функции Эйлера задаётся явной формулой^[8]:

$varphi(p)=p-1,$

которая следует из определения. Действительно, если $p$ — простое, то все числа, меньшие $p$ , взаимно просты с ним, а их ровно $p-1$ штук.

Для вычисления функции Эйлера от степени простого числа используют следующую формулу^[8]:

$varphi(p^n)=p^n-p^{n-1}.$

Это равенство обосновывается следующим образом. Подсчитаем количество чисел от $1$ до $p^{n}$ , которые не взаимно просты с $p^{n}$ . Все они, очевидно, кратны $p$ , то есть, имеют вид: ${displaystyle p,;2p,;3p,;ldots ,;p^{n-1}p.}$ Всего таких чисел ${displaystyle p^{n-1}}$ . Поэтому количество чисел, взаимно простых с $p^{n}$ , равно ${displaystyle p^{n}-p^{n-1}}$ .

Функция Эйлера от натурального числа[править | править код]

Вычисление $varphi (n)$ для произвольного натурального $n$ основывается на мультипликативности функции Эйлера, выражении для $varphi(p^{n})$ , а также на основной теореме арифметики.
Для произвольного натурального числа значение $varphi (n)$ представляется в виде^[8]:

$varphi(n)=nprod_{pmid n}left(1-frac{1}{p}right),;;n>1,$

где $p$ — простое число и пробегает все значения, участвующие в разложении $n$ на простые сомножители.

Доказательство

Как следует из основной теоремы арифметики, всякое натуральное число $n>1$ единственным образом представляется в виде:

$n=p_1^{alpha_1}cdotldotscdot p_k^{alpha_k},$

где $p_1<ldots<p_k$ — простые числа, $alpha_1,;ldots,;alpha_k$ — натуральные числа.

Используя мультипликативность функции Эйлера и выражение для $varphi(p^{k})$ , получаем: ${displaystyle {begin{aligned}varphi (n)&=varphi (p_{1}^{alpha _{1}})varphi (p_{2}^{alpha _{2}})cdot ldots cdot varphi (p_{k}^{alpha _{k}})=\&=p_{1}^{alpha _{1}}left(1-{frac {1}{p_{1}}}right)p_{2}^{alpha _{2}}left(1-{frac {1}{p_{2}}}right)cdot ldots cdot p_{k}^{alpha _{k}}left(1-{frac {1}{p_{k}}}right)=\&=p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}cdot ldots cdot p_{k}^{alpha _{k}}left(1-{frac {1}{p_{1}}}right)left(1-{frac {1}{p_{2}}}right)cdot ldots cdot left(1-{frac {1}{p_{k}}}right)=\&=nleft(1-{frac {1}{p_{1}}}right)left(1-{frac {1}{p_{2}}}right)cdot ldots cdot left(1-{frac {1}{p_{k}}}right).end{aligned}}}$

Пример применения: ${displaystyle varphi (36)=varphi (2^{2}cdot 3^{2})=varphi (2^{2})varphi (3^{2})=(2^{2}-2)(3^{2}-3)=2cdot 6=12.}$

Свойства[править | править код]

Обобщённая мультипликативность[править | править код]

Функция Эйлера является мультипликативной арифметической функцией, то есть

${displaystyle varphi (mn)=varphi (m)varphi (n);;;forall m,,nin mathbb {N} colon (m,,n)=1.}$

Здесь существенно, что наибольший общий делитель $m$ и $n$ равен единице. Оказывается, существует обобщение этой формулы на случай, когда $m$ и $n$ имеют общие делители, отличные от единицы. А именно, для любых натуральных $m$ и $n$ ^[9]:

$varphi(m cdot n) = varphi(m) cdot varphi(n)cdotfrac{d}{varphi(d)},$

где $d$ — наибольший общий делитель $m$ и $n.$ Это свойство является естественным обобщением мультипликативности.

Доказательство обобщённой мультипликативности

Некоторые частные случаи:

Теорема Эйлера[править | править код]

Наиболее часто на практике используется свойство, установленное Эйлером:

$a^{varphi(m)}equiv 1pmod m,$

если $a$ и $m$ взаимно просты.

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

В качестве следствия теоремы Эйлера можно получить малую теорему Ферма. Для этого нужно взять не произвольное $m,$ а простое. Тогда:

$a^{m - 1}equiv 1pmod m.$

Последняя формула находит применение в различных тестах простоты.

Другие свойства[править | править код]

Исходя из представимости $varphi (n)$ произведением Эйлера, несложно получить следующее полезное утверждение:

$amid b Rightarrow varphi(a)midvarphi(b).$

Следующее равенство^[10]^[11] является следствием теоремы Зигмонди^[en]:

${displaystyle varphi (a^{n}+b^{n})equiv 0{pmod {n}},;a>bgeqslant 1.}$

Всякое натуральное число представимо в виде суммы значений функции Эйлера от его натуральных делителей^[12]:

$sum_{dmid n}varphi(d)=n.$

Сумма всех чисел, меньших данного, и взаимно простых с ним, выражается через функцию Эйлера:

$sum_{1leqslant kleqslant natop(k,;n)=1}k=frac{1}{2}nvarphi(n), ; n > 1.$

Множество значений[править | править код]

Исследование структуры множества значений функции Эйлера является отдельной сложной задачей. Здесь представлены лишь некоторые результаты, полученные в этой области^[13].

Доказательство (функция Эйлера принимает только чётные значения при n > 2)

В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции. Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду следующее.

Значения функции Эйлера повторяются (например, $varphi(1) = varphi(2) = 1$ ), следовательно обратная функция является многозначной.
Функция Эйлера принимает лишь чётные значения при $n > 2,$ то есть ${displaystyle varphi ^{-1}(m)=varnothing ,}$ если $m$ нечётно и ${displaystyle mneq 1.}$

В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза $varphi$ является следующая теорема^[14].

Если $n in varphi^{-1}(m),$ то ${displaystyle m<nleqslant A(m).}$

Эта теорема показывает, что прообраз элемента ${displaystyle min mathbb {N} }$ всегда представляет собой конечное множество. Также она даёт следующий практический способ нахождения прообраза:

1) вычислить $A(m)$ ;

2) вычислить $varphi (n)$ для всех $n$ из полуинтервала ${displaystyle (m,,A(m)]}$ ;

3) все числа $n,$ для которых $varphi(n)=m,$ образуют прообраз элемента $m$ .

Может оказаться, что в указанном промежутке нет такого числа $n,$ что $varphi(n)=m;$ в этом случае прообраз является пустым множеством.

Стоит отметить, что для вычисления $A(m)$ нужно знать разложение $m$ на простые сомножители, что для больших $m$ является вычислительно сложной задачей. Затем нужно $A(m)-m$ раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.

Пример 1 (Вычисление прообраза)

Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 — простые числа. Вычисляем

$A(4) = 4 cdot frac{2}{1} cdot frac{3}{2} cdot frac{5}{4} = 15.$

Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:

${displaystyle varphi ^{-1}(4)={5,;8,;10,;12}.}$

Пример 2 (Не все чётные числа являются значениями функции Эйлера)

Не существует, например, такого числа $m,$ что $varphi(m) = 14.$ То есть:

${displaystyle varphi ^{-1}(14)=varnothing .}$

В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа — простые. Поэтому

$A(14) = 14 cdot frac{2}{1} cdot frac{3}{2} = 42.$

Перебрав все числа от 15 до 42, несложно убедиться, что

${displaystyle varphi (n)neq 14,;nin (15,,42].}$

Асимптотические соотношения[править | править код]

Простейшие неравенства[править | править код]

Оценка снизу значений функции Эйлера^[15]^[16]:

${displaystyle varphi (n)geqslant {sqrt {n}},}$

для всех $n,$ кроме $n = 2$ и $n = 6.$

для всякого составного $n.$

Сравнение φ(n) с n[править | править код]

Отношение последовательных значений[править | править код]

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

плотно в множестве действительных положительных чисел.

В том же году они установили^[20], что множество

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

плотно на интервале ${displaystyle (0,;1).}$

Асимптотики для сумм[править | править код]

Точное выражение для суммы последовательных значений функции Эйлера^[21]:

$sum_{nleqslant x}varphi(n)=frac{3}{pi^2}x^2+O(xln x).$

Отсюда вытекает, что средний порядок^[en] функции Эйлера равно ${displaystyle 6n/pi ^{2}}$ . Этот результат интересен тем, что позволяет получить вероятность события, состоящего в том, что два наугад выбранных натуральных числа являются взаимно простыми. А именно, эта вероятность равна ${displaystyle 6/pi ^{2}}$ ^[22].

Порядок функции Эйлера[править | править код]

В 1909 году Ландау получил равенство^[24]^[25]:

$liminffrac{varphi(n)}{n}loglog n = e^{-gamma},$

где $gamma$ — постоянная Эйлера — Маскерони.

Этот результат можно уточнить. В 1962 году была получена оценка снизу для функции Эйлера^[26]:

${displaystyle varphi (n)geqslant {frac {n}{e^{gamma }log log n+{frac {2{,}5}{log log n}}}},}$

для всех $ngeqslant 3$ , с одним исключением ${displaystyle n=2cdot 5cdot 7cdot 11cdot 13cdot 17cdot 19cdot 23;}$ в указанном случае следует заменить ${displaystyle 2{,}5}$ на ${displaystyle 2{,}50637.}$ Это одна из наиболее точных оценок снизу для $varphi (n)$ ^[27].

Как отмечает Пауло Рибенбойм^[en] по поводу доказательства этого неравенства^[27]: «Способ доказательства интересен тем, что неравенство сначала устанавливается в предположении, что гипотеза Римана верна, а затем в предположении, что она не верна».

Связь с другими функциями[править | править код]

Функция Мёбиуса[править | править код]

где $mu(m)$ — функция Мёбиуса.

Ряд Дирихле[править | править код]

Ряд Ламберта[править | править код]

Наибольший общий делитель[править | править код]

Функция Эйлера является дискретным преобразованием Фурье наибольшего общего делителя^[33]:

${displaystyle varphi (n)=sum limits _{k=1}^{n}gcd(k,,n)e^{{-2pi i}{tfrac {k}{n}}}.}$

Действительная часть:

${displaystyle varphi (n)=sum limits _{k=1}^{n}gcd(k,,n)cos {2pi {frac {k}{n}}}.}$

В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей $n.$

Связь с латинскими квадратами[править | править код]

Приложения и примеры[править | править код]

Функция Эйлера в RSA[править | править код]

На основе алгоритма, предложенного в 1978 году Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом, была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов — система RSA. Криптостойкость этой системы определяется сложностью разложения на сомножители целого $n$ -разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом^[35].

На этапе создания пары из секретного и открытого ключей вычисляется

$varphi(n) = varphi(p cdot q) = (p-1) cdot (q-1),$

где $p$ и $q$ — простые. Затем выбираются случайные числа ${displaystyle d, e}$ так, чтобы

$d cdot e = 1 ;bmod ;varphi(n).$

Затем сообщение шифруется открытым ключом адресата:

$c = m^e ;bmod ;n.$

После этого расшифровать сообщение может только обладатель секретного ключа $d$ :

$m = c^d ;bmod ;n.$

Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.

Доказательство корректности расшифрования

В силу выбора чисел на этапе создания ключей

$e cdot d = 1 + a cdot varphi(n).$

Если ${displaystyle (m,,n)=1,}$ то, с учетом теоремы Эйлера,

$c^d = m^{ed} = m^{1}m^{avarphi(n)} = m cdot 1^{a} = m ;bmod ;n.$

В общем случае $m$ и $n$ могут иметь общие делители, но расшифрование всё равно оказывается верным. Пусть $m = 0 ;bmod ;p.$ По китайской теореме об остатках:

$m = c^d ;bmod ;n ;Leftrightarrow ;begin{cases} m = c^d ;bmod ;p, \ m = c^d ;bmod ;q. end{cases}$

Подставляя $c = m^e,$ получаем тождество

$begin{cases} m^{ed} = 0 = m ;bmod ;p, \ m^{ed} = m(m^{q-1})^{a(p-1)} = m cdot 1^{a(p-1)} = m ;bmod ;q. end{cases}$

Следовательно,

$m^{ed} = m ;bmod ;pq.$

Вычисление обратного элемента[править | править код]

Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю $n$ , а именно^[36]:

$a^{-1} equiv a^{varphi(n)-1} pmod n,$ если ${displaystyle (a,,n)=1.}$

Эта формула следует из теоремы Эйлера:

$1 = (a cdot a^{-1}) cdot a^{varphi(n)} ;bmod ;n = a cdot (a^{-1} cdot a^{varphi(n)}) ;bmod ;n = a cdot a^{varphi(n) - 1} ;bmod ;n.$

Пример (Вычисление обратного элемента)

Замечание 1 (Оценка сложности вычисления)

В общем случае для вычисления обратных значений алгоритм Евклида быстрее, чем использование теоремы Эйлера^[37], так как битовая сложность вычисления по алгоритму Евклида имеет порядок $O(k^2),$ в то время как вычисление по теореме Эйлера требует порядка $O(k^3)$ битовых операций, где $k = lceil log_2{n} rceil.$ Однако, в случае, когда известно разложение $varphi(n)-1$ на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм «возводи в квадрат и перемножай»^[38].

Замечание 2 (Отсутствие решения в случае (a, n) ≠ 1)

Если ${displaystyle (a,,n)neq 1,}$ то обратного к $a$ элемента не существует, или, иначе говоря, уравнение

$a cdot x equiv 1 pmod n$

не имеет решения на множестве натуральных чисел^[39].

Доказательство. В самом деле, допустим

${displaystyle (a,,n)=d>1,}$

и решение существует. Тогда по определению наибольшего общего делителя

${displaystyle a=dcdot a', n=dcdot n',}$ причем ${displaystyle (a',,n')=1;}$

поэтому можно записать:

$d cdot a' cdot x = d cdot n' cdot t + 1,$ где ${displaystyle tin mathbb {N} _{0},xin mathbb {N} ;}$

или, перегруппировав слагаемые,

$a' cdot x - n' cdot t = frac{1}{d}.$

Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью

$d = 1,$

что противоречит предположению.

Решение линейного сравнения[править | править код]

Метод вычисления обратного элемента можно использовать для решения сравнения

$a cdot x equiv b pmod n.$

Решение задаётся формулой^[37]:

$x equiv b cdot a^{varphi(n)-1} pmod n,$ если ${displaystyle (a,,n)=1.}$

Пример (Решение линейного сравнения)

Рассмотрим сравнение

$7 cdot x equiv 3 pmod 9.$

Так как $(7,9)=1,$ можно воспользоваться указанной формулой:

$x = 3 cdot 7^{varphi(3^{2})-1} ;bmod ;9 = 3 cdot 7^{3 cdot (3-1) - 1} ;bmod ;9 = 3 cdot 7^{5} ;bmod ;9 = 3 cdot 49 cdot 49 cdot 7 ;bmod ;9 = 3 cdot 4 cdot 4 cdot 7 ;bmod ;9 = 3.$

Подстановкой убеждаемся, что

$7 cdot 3 equiv 3 pmod 9.$

Замечание (Неединственность решения или отсутствие решения в случае (a, n) ≠ 1)

Если ${displaystyle (a,,n)neq 1}$ , сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение

$2 cdot x equiv 3 pmod 4$

не имеет решения на множестве натуральных чисел. В то же время сравнение

$4 cdot x equiv 6 pmod {22}$

имеет два решения

$x = 7, ; x = 18.$

Вычисление остатка от деления[править | править код]

Функции Эйлера позволяет вычислять остатки от деления больших чисел^[40].

Пример 1 (Последние три цифры в десятичной записи числа)

Найдем последние три цифры в десятичной записи числа $2^{100}.$ Замечая, что

$varphi(125) = varphi(5^3) = 5^3 - 5^2 = 100,$

получаем

$2^{100} ;bmod ;125 = 2^{125 - 25} ;bmod ;125 = 2^{varphi(125)} ;bmod ;125 = 1 ;bmod ;125.$

Переходя теперь от модуля $125$ к модулю $1000,$ имеем:

$2^{100} equiv 1 pmod{125} equiv 376 pmod{1000}.$

Следовательно, десятичная запись числа $2^{100}$ оканчивается на $376.$

Пример 2 (Остаток от деления на 1001)

Найдем остаток от деления $729^{720}$ на $1001.$ Легко видеть, что

${displaystyle (729,;1001)=1.}$

Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством

$varphi(p) = p - 1,$ для всякого простого $p,$

получаем

$varphi(1001) = varphi(7 cdot 11 cdot 13) = varphi(7) cdot varphi(11) cdot varphi(13) = 6 cdot 10 cdot 12 = 720.$

По теореме Эйлера

$729^{720} equiv 1 pmod{1001}.$

Нахождение порядка мультипликативной группы кольца вычетов[править | править код]

Мультипликативная группа кольца вычетов по модулю $m$ состоит из $varphi(m)$ классов вычетов^[41].

Пример. Приведённая система вычетов по модулю 14 состоит из $varphi(14) = 6$ классов вычетов: ${displaystyle [1]_{14}, [3]_{14}, [5]_{14}, [9]_{14}, [11]_{14}, [13]_{14}.}$

Приложения в теории групп[править | править код]

Число порождающих элементов в конечной циклической группе $G$ равно $varphi(|G|)$ . В частности, если мультипликативная группа кольца вычетов по модулю $m$ является циклической группой — что возможно только при ${displaystyle m=2,;4,;p^{n},;2p^{n}}$ , где $p$ — простое нечётное, $n$ — натуральное^[42], — то существует $varphi(varphi(m))$ генераторов группы (первообразных корней по модулю $m$ ).

Пример. Группа ${displaystyle mathbb {Z} _{14}^{times },}$ рассмотренная в примере выше, имеет $varphi(varphi(14)) = varphi(6) = 2$ генератора: $3$ и $5.$

Нерешенные вопросы[править | править код]

Задача Лемера[править | править код]

Как известно, если $p$ — простое, то $varphi(p) = p - 1.$ В 1932 году Деррик Лемер^[en] задался вопросом, существует ли такое составное число $n$ , что $varphi (n)$ является делителем $n-1$ . Лемер рассматривал уравнение:

$kvarphi(n) = n-1,$

где $k$ — целое. Ему удалось доказать, что если $n$ — решение уравнения, то либо $n$ — простое, либо оно является произведением семи или более различных простых чисел^[43]. Позже были доказаны и другие сильные утверждения. Так, в 1980 году Cohen и Hagis показали, что если $n$ составное и $varphi (n)$ делит $n-1,$ то $n > 10^{20}$ и ${displaystyle omega (n)geqslant 14,}$ где $omega(n)$ — количество простых делителей. В 1970 году Lieuwens установил, что если $3mid n,$ то ${displaystyle omega (n)geqslant 213}$ и ${displaystyle n>5{,}5cdot 10^{570}.}$ Wall в 1980 году доказал, что если $30mid n,$ то ${displaystyle omega (n)geqslant 26}$ ^[44].

По сей день неизвестно, существуют ли составные решения задачи Лемера. Если предположить, что их не существует, то получается следующий критерий простоты: $n$ — простое тогда и только тогда, когда ${displaystyle varphi (n)mid n-1}$ ^[43].

Гипотеза Кармайкла[править | править код]

Если посмотреть даже на первые десять значений функции Эйлера {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, бросается в глаза, что среди них много повторяющихся. Гипотеза Кармайкла состоит в том, что нет такого значения $m$ , которое функция Эйлера принимала бы только один раз.

В 1907 году Кармайкл предложил как упражнение доказать следующее утверждение^[45]:

Если $n$ — натуральное число, то существует натуральное число ${displaystyle mneq n}$ такое, что $varphi(n)=varphi(m).$

Иначе это утверждение можно сформулировать так^[46]: не существует натурального числа $m$ такого, что $dim(varphi^{-1}(m)) = 1.$

Однако в 1922 году Кармайкл обнаружил, что предложенное им доказательство содержит ошибку. В этом же году он показал, что если $dim(varphi^{-1}(m)) = 1,$ то ${displaystyle m>10^{37}.}$ Позже эта оценка неоднократно улучшалась, и современное значение нижней границы, с которой стоит начинать искать контрпример для гипотезы Кармайкла, есть ${displaystyle m=10^{10^{7}}.}$ Это значение получили Schlafly и Wagon в 1994 году, используя метод Klee^[45].

Стоит отметить, что в 1999 году Форд доказал следующую теорему^[47]:

${displaystyle forall kgeqslant 2;exists mcolon dim(varphi ^{-1}(m))=k.}$

Это означает, что, задавшись некоторым числом ${displaystyle kgeqslant 2,}$ можно найти среди множества значений функции Эйлера такое значение $m,$ что оно принимается ровно $k$ раз. Однако, доказать, что нет такого значения, которое функция Эйлера принимала бы только один раз, до сих пор никому не удалось^[46].

См. также[править | править код]

Список объектов, названных в честь Леонарда Эйлера

Примечания[править | править код]

↑ Эйлера функция // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1985. — Т. 5. — С. 934.
↑ Sandifer, 2007, p. 203.
↑ Габидулин, 2011, Системы RSA.
↑ последовательность A000010 в OEIS
↑ Burton, 2007, Theorem 7.2, p. 133.
↑ Hardy, 1975, Theorem 59, p. 52.
↑ Hardy, 1975, Theorem 60, p. 53.
↑ ¹ ² ³ Сагалович, 2007, Вычисление функции Эйлера, p. 35—36.
↑ Burton, 2007, Euler’s Phi-Function, p. 136.
↑ Weisstein, MathWorld, Totient Function
↑ Ruiz, S., A Congruence With the Euler Totient Function, 2004
↑ Виноградов, 1952, Функция Эйлера.
↑ Информация в этом разделе основана на статье: Coleman, Some remarks on Euler’s totient function
↑ Gupta H., 1981
↑ ¹ ² ³ Handbook, 2005, Elementary inequalities for φ.
↑ Kendall and Osborn 1965
↑ Sierpiński and Schinzel 1988
↑ Hardy, 1975, Theorem 326, p. 267.
↑ Hardy, 1975, Theorem 327, p. 267.
↑ ¹ ² ³ Ribenboim, 1996, Values of Euler’s Function, p. 38.
↑ Hardy, 1975, Theorem 330, p. 268.
↑ Hardy, 1975, Theorem 332, p. 269.
↑ Hardy, 1975, Theorem 329, p. 267.
↑ Handbook, 2005, On the function n/φ(n).
↑ Hardy, 1975, Theorem 328, p. 267.
↑ Rosser, J. Barkley and Schoenfeld, Lowell. Approximate formulas for some functions of prime numbers (англ.) // Illinois J. Math. : journal. — 1962. — Vol. 6, no. 1. — P. 64—94. (Theorem 15)
↑ ¹ ² Ribenboim, 1996, Distribution of Values of Euler’s Function, p. 320.
↑ Nicolas, 1983
↑ Виноградов, 1952, с. 29—31.
↑ Rosica Dineva, The Euler Totient, the Möbius, and the Divisor Functions
↑ Hardy, 1975, Theorem 288, p. 250.
↑ Hardy, 1975, Theorem 309, p. 258.
↑ Schramm, 2008
↑ Ватутин Э.И. О перечислении циклических латинских квадратов и расчете значения функции Эйлера с их использованием // Высокопроизводительные вычислительные системы и технологии. 2020. Т. 4, № 2. С. 40–48.
↑ Габидулин, 2011, Система шифрования RSA, с. 96.
↑ Алфёров, 2002, p. 462—463.
↑ ¹ ² Schneier, 1995, The Euler Totient Function.
↑ Габидулин, 2011, Нахождение мультипликативного обратного по модулю, с. 233.
↑ Schneier, 1995, Number Theory.
↑ Сагалович, 2007, с. 36.
↑ Сагалович, 2007, Приведенная система вычетов.
↑ Виноградов, 1952, с. 106.
↑ ¹ ² Lehmer, 1932
↑ Ribenboim, 1996, p. 36—37.
↑ ¹ ² Ribenboim, 1996, p. 39—40.
↑ ¹ ² Coleman, Some remarks on Euler’s totient function
↑ Ford, 1999

Литература[править | править код]

Charles Sandifer. The early mathematics of Leonhard Euler. — MAA, 2007. — С. 391. — ISBN 0-88385-559-3.
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici. Euler’s φ-function // Handbook of Number Theory I. — Springer, 2005. — 622 с.
Виноградов И. М. Основы теории чисел. — 5-е изд. — М.—Л.: Гостехиздат, 1952. — 180 с. — 100 000 экз.
G. H. Hardy, E. M. Wright. An Introduction to the Theory of Numbers. — fourth edition. — Oxford: Oxford University Press, 1975. — 421 с.
Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Элементы алгебры и теории чисел // Основы криптографии. — 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — 480 с. — ISBN 5-85438-025-0.
Bruce Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C. — Australia: John Wiley & Sons, 1995. — ISBN 0-471-12845-7.
Сагалович Ю. Л. Введение в алгебраические коды — М.: МФТИ, 2007. — 262 с. — ISBN 978-5-7417-0191-1
Paulo Ribenboim. The New Book of Prime Number Records. — New York: Springer, 1996. — ISBN 0-387-94457-5.
Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. — ISBN 5-7417-0377-9.
David M. Burton. Elementary Number Theory. — Sixth Edition. — University of New Hampshire: McGraw-Hill, 2007. — 512 с. — ISBN 978-0-07-305188-8.
Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. — М.: МЦНМО, 2003. — 44 с. — ISBN 5-94057-141-7.

Ссылки[править | править код]

Арнольд В. И., Группы Эйлера и арифметика геометрических прогрессий (2003)
Coleman R., Some remarks on Euler’s totient function (2012)
Dineva R., The Euler Totient, the Möbius, and the Divisor Functions (2005)
Ford K., The number of solutions of φ(x) = m (1999)
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I (2005)
Gupta H., Euler’s totient function and its inverse (1981)
Hardy, Wright An Introduction to the Theory of Numbers (2008)
Lehmer D. H., On Euler’s Totient Function (1932)
Ruiz S., A Congruence With the Euler Totient Function (2004)
Schramm, Wolfgang, The Fourier Transform of Functions of the Greatest Common Divisor (2008)
Weisstein, Eric W. «Totient Function.» From MathWorld — A Wolfram Web Resource. http://mathworld.wolfram.com/TotientFunction.html

Источник

Интересное и простое из комбинаторики. Функция Эйлера

Время на прочтение
2 мин

Количество просмотров 7.7K

Предисловие

Прежде всего хочу сказать, мне всего 14 лет. Я надеюсь, что информация, которой поделюсь, будет для кого-то интересна.
Речь пойдет о некоторых задачах комбинаторики.

Сколько вариантов расставить n предметов?

Способ №1

Первое, что приходит на ум обычному человеку: «Возьму-ка я 3 предмета и начну их расставлять в ряд. Сколько разных комбинаций получится — столько вариантов расстановок и есть». Да, это так. Но есть способ, который по своей простоте опережает приведенный ранее способ.

Способ №2

Факториал — количество способов расставить n предметов.
Факториал высчитывается перемножением чисел от 1 до n.
Обозначается n! (читать как факториал n).

Допустим, нам нужно узнать, сколько вариантов в расстановке 10 предметов. Умножаем: 1x2x3..x10
Получим: 10! = 3628800

Как из n предметов выбрать k предметов?

Способ №1

Допустим, вы — организатор лотереи. Из 10 участников вам нужно выбрать 2 победителя. Вы можете узнать количество способов сделать это.
Так же как и в случае с факториалом, можно посчитать вручную. Выбирать n предметов, пока не иссякнут все варианты.
Цитирую: но есть способ, который по своей простоте опережает приведенный ранее способ.

Способ №2

Число сочетаний — это количество способов из n предметов выбрать k предметов.
Обозначается так: $binom{n}{k}$

Высчитывается по формуле: $binom{n}{k}= frac{!n}{k!(n-k)!}$
Итак, сколько же способов из 10 участников выбрать 2 победителя?

Ответ вполне себе простой – $binom{10}{2}= frac{10!}{2!(10-2)!}= frac{3628800}{2cdot40320 } = frac{3628800}{80640}=45$

Числа Фибоначчи

Стоит отдать должное человеку, который «придумал» эти числа. Леонардо Пизанский. Думаю достаточно, чтобы Вы запомнили имя этого великого человека.

Приступим. Числа Фибоначчи применяются в Теории Чисел. Если сказать честно, я знаю не слишком много об этих числах.
Числа Фибоначчи — это последовательность чисел, в котором каждое последующее числовое значение равно сумме двух предыдущих. Первые два числа Фибоначии — единицы. Соответственно, 3-е число = 2.

Первые 22 числа Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.

Еще раз повторюсь — я знаю не слишком много об этих числах. Если я еще не слишком вас утомил/отпугнул/надоел — идем дальше.

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

В этом пункте я попытаюсь выложить все, что знаю об этом. Я потратил достаточно времени и сил, чтобы изучить эту, между прочим абсолютно простою вещь.

По правде говоря, я очень горжусь тем, что такой человек как Леонард Эйлер жил в России.

К делу. Есть три разных способа посчитать функцию Эйлера. На выбор одного из способов влияют некоторые факторы.
Функция Эйлера обозначается $varphi (n)$ (читать как фи от n).

Способ №1

$varphi (n)=n-1$
Увы, но этот способ применять следует для высчитывания функции простых чисел.
Например, функция Эйлера для 3 = $varphi (3)=3-1=2$

Способ №2

Данный способ следует применять если число можно представить как степень какого-то числа. Например, 9 — это $3^2$
Посчитаем функцию для 9.
$varphi(9)=3^2-3^2^-^1$
$varphi(9)=9-3=6$
Получаем: $varphi(9)=6$

Способ №3

Если число нельзя представить как степень, но можно представить как два множителя — этот способ нам и нужен.
Тут немного сложнее. Нужно разложить число на два множителя, посчитать функцию для каждого из множителей и полученные результаты перемножить.
Также хочу отметить, что если число можно представить и как степень и как два множителя, то в преимуществе всегда степень какого-то числа (о как, в рифму).
$varphi(6)=varphi(2)varphi(3)$
$varphi(2)=2-1=1$
$varphi(3)=3-1=2$
$varphi(2)varphi(3)=1*2=2$
Таким образом получаем: $varphi(6)=2$

Спасибо за внимание.

Источник

Расчет значения функции Эйлера

Целое положительное число

Функция Эйлера – такая функция от целого положительного числа, значение которой равно количеству натуральных чисел, меньших заданного числа и взаимно простых с ним.

При этом полагают, что число 1 взаимно просто со всеми натуральными числами.

Если заданное число N является простым то логично предложить что функция Эйлера будет равна N-1, так как все числа меньше N, являются взаимно простыми к заданному.

Например, значение функции Эйлера числа 33 равно 20. Как такое получилось?

Разложим 33 на множители получим 3*11. Запомним их и будем сравнивать с рядом чисел от 1 до 32.

Напомним, что взаимно простыми числами являются таки числа, которые не имеют общих делителей.

Считаем взаимно простые числа: 1,2 ,3(не учитываем),4,5,6(делится на 3),7,8,9,10,11(делится на 11),12,13,14,15,16,17,18,19,20,21(делится на три),22(делится на 11),23,24,25,26,27,28,29,30,31,32

Посчитаем сколько получилось зачеркнутых чисел?

Их 12, ряд чисел содержит 32 элемента ( от 1 до 33) тогда количество не зачёркнутых (взаимно простых) чисел будет 32-12 =20

Есть еще простой способ рассчитывать значения функции

Разложим произвольное число например 4832 на простые множители.

Получим $Простые множители заданного числа$

Функция Эйлера равна $(2^{5}-2^{4})*(151^{1}-151^{0}=(32-16)(151-1)=2400$

То есть, если у вас число N представлено в виде простых сомножителей вида $P_1^{B_1}P_2^{B_2}.....P_m^{B_m}$

то функция Эйлера будет равна

$(P_1^{B_1}-P_1^{B_1-1})(P_2^{B_2}-P_2^{B_2-1}).....(P_m^{B_m}-P_m^{B_m-1})$

Вот еще пример

Рассчитаем значение фунции числа 100

$Простые множители заданного числа$

тогда значение функции Эйлера равно $функция эйлера$

Применимость числа Эйлера в теории чисел и криптографии достаточно велико, но мы будем её использовать для расчета линейных диофантовых уравнений с двумя неизвестными.

Напоследок, представляем таблицу значений функции Эйлера для первых 500 чисел

1	1	101	100	201	132	301	252	401	400
2	1	102	32	202	100	302	150	402	132
3	2	103	102	203	168	303	200	403	360
4	2	104	48	204	64	304	144	404	200
5	4	105	48	205	160	305	240	405	216
6	2	106	52	206	102	306	96	406	168
7	6	107	106	207	132	307	306	407	360
8	4	108	36	208	96	308	120	408	128
9	6	109	108	209	180	309	204	409	408
10	4	110	40	210	48	310	120	410	160
11	10	111	72	211	210	311	310	411	272
12	4	112	48	212	104	312	96	412	204
13	12	113	112	213	140	313	312	413	348
14	6	114	36	214	106	314	156	414	132
15	8	115	88	215	168	315	144	415	328
16	8	116	56	216	72	316	156	416	192
17	16	117	72	217	180	317	316	417	276
18	6	118	58	218	108	318	104	418	180
19	18	119	96	219	144	319	280	419	418
20	8	120	32	220	80	320	128	420	96
21	12	121	110	221	192	321	212	421	420
22	10	122	60	222	72	322	132	422	210
23	22	123	80	223	222	323	288	423	276
24	8	124	60	224	96	324	108	424	208
25	20	125	100	225	120	325	240	425	320
26	12	126	36	226	112	326	162	426	140
27	18	127	126	227	226	327	216	427	360
28	12	128	64	228	72	328	160	428	212
29	28	129	84	229	228	329	276	429	240
30	8	130	48	230	88	330	80	430	168
31	30	131	130	231	120	331	330	431	430
32	16	132	40	232	112	332	164	432	144
33	20	133	108	233	232	333	216	433	432
34	16	134	66	234	72	334	166	434	180
35	24	135	72	235	184	335	264	435	224
36	12	136	64	236	116	336	96	436	216
37	36	137	136	237	156	337	336	437	396
38	18	138	44	238	96	338	156	438	144
39	24	139	138	239	238	339	224	439	438
40	16	140	48	240	64	340	128	440	160
41	40	141	92	241	240	341	300	441	252
42	12	142	70	242	110	342	108	442	192
43	42	143	120	243	162	343	294	443	442
44	20	144	48	244	120	344	168	444	144
45	24	145	112	245	168	345	176	445	352
46	22	146	72	246	80	346	172	446	222
47	46	147	84	247	216	347	346	447	296
48	16	148	72	248	120	348	112	448	192
49	42	149	148	249	164	349	348	449	448
50	20	150	40	250	100	350	120	450	120
51	32	151	150	251	250	351	216	451	400
52	24	152	72	252	72	352	160	452	224
53	52	153	96	253	220	353	352	453	300
54	18	154	60	254	126	354	116	454	226
55	40	155	120	255	128	355	280	455	288
56	24	156	48	256	128	356	176	456	144
57	36	157	156	257	256	357	192	457	456
58	28	158	78	258	84	358	178	458	228
59	58	159	104	259	216	359	358	459	288
60	16	160	64	260	96	360	96	460	176
61	60	161	132	261	168	361	342	461	460
62	30	162	54	262	130	362	180	462	120
63	36	163	162	263	262	363	220	463	462
64	32	164	80	264	80	364	144	464	224
65	48	165	80	265	208	365	288	465	240
66	20	166	82	266	108	366	120	466	232
67	66	167	166	267	176	367	366	467	466
68	32	168	48	268	132	368	176	468	144
69	44	169	156	269	268	369	240	469	396
70	24	170	64	270	72	370	144	470	184
71	70	171	108	271	270	371	312	471	312
72	24	172	84	272	128	372	120	472	232
73	72	173	172	273	144	373	372	473	420
74	36	174	56	274	136	374	160	474	156
75	40	175	120	275	200	375	200	475	360
76	36	176	80	276	88	376	184	476	192
77	60	177	116	277	276	377	336	477	312
78	24	178	88	278	138	378	108	478	238
79	78	179	178	279	180	379	378	479	478
80	32	180	48	280	96	380	144	480	128
81	54	181	180	281	280	381	252	481	432
82	40	182	72	282	92	382	190	482	240
83	82	183	120	283	282	383	382	483	264
84	24	184	88	284	140	384	128	484	220
85	64	185	144	285	144	385	240	485	384
86	42	186	60	286	120	386	192	486	162
87	56	187	160	287	240	387	252	487	486
88	40	188	92	288	96	388	192	488	240
89	88	189	108	289	272	389	388	489	324
90	24	190	72	290	112	390	96	490	168
91	72	191	190	291	192	391	352	491	490
92	44	192	64	292	144	392	168	492	160
93	60	193	192	293	292	393	260	493	448
94	46	194	96	294	84	394	196	494	216
95	72	195	96	295	232	395	312	495	240
96	32	196	84	296	144	396	120	496	240
97	96	197	196	297	180	397	396	497	420
98	42	198	60	298	148	398	198	498	164
99	60	199	198	299	264	399	216	499	498
100	40	200	80	300	80	400	160	500	200

Удачных расчетов!

Источник

“φ(n)” redirects here. For other uses, see Phi.

The first thousand values of φ(n). The points on the top line represent φ(p) when p is a prime number, which is p − 1.^[1]

In number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as $varphi (n)$ or $phi (n)$ , and may also be called Euler’s phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.^[2]^[3] The integers k of this form are sometimes referred to as totatives of n.

For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.

Euler’s totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime, then φ(mn) = φ(m)φ(n).^[4]^[5]
This function gives the order of the multiplicative group of integers modulo n (the group of units of the ring ${displaystyle mathbb {Z} /nmathbb {Z} }$ ).^[6] It is also used for defining the RSA encryption system.

History, terminology, and notation[edit]

Leonhard Euler introduced the function in 1763.^[7]^[8]^[9] However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter π to denote it: he wrote πD for “the multitude of numbers less than D, and which have no common divisor with it”.^[10] This definition varies from the current definition for the totient function at D = 1 but is otherwise the same. The now-standard notation^[8]^[11] φ(A) comes from Gauss’s 1801 treatise Disquisitiones Arithmeticae,^[12]^[13] although Gauss didn’t use parentheses around the argument and wrote φA. Thus, it is often called Euler’s phi function or simply the phi function.

In 1879, J. J. Sylvester coined the term totient for this function,^[14]^[15] so it is also referred to as Euler’s totient function, the Euler totient, or Euler’s totient. Jordan’s totient is a generalization of Euler’s.

The cototient of n is defined as n − φ(n). It counts the number of positive integers less than or equal to n that have at least one prime factor in common with n.

Computing Euler’s totient function[edit]

There are several formulae for computing φ(n).

Euler’s product formula[edit]

It states

${displaystyle varphi (n)=nprod _{pmid n}left(1-{frac {1}{p}}right),}$

where the product is over the distinct prime numbers dividing n. (For notation, see Arithmetical function.)

An equivalent formulation is

${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),}$

where ${displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}}}$ is the prime factorization of $n$ (that is, ${displaystyle p_{1},p_{2},ldots ,p_{r}}$ are distinct prime numbers).

The proof of these formulae depends on two important facts.

Phi is a multiplicative function[edit]

This means that if gcd(m, n) = 1, then φ(m) φ(n) = φ(mn). Proof outline: Let A, B, C be the sets of positive integers which are coprime to and less than m, n, mn, respectively, so that |A| = φ(m), etc. Then there is a bijection between A × B and C by the Chinese remainder theorem.

Value of phi for a prime power argument[edit]

If p is prime and k ≥ 1, then

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

Proof: Since p is a prime number, the only possible values of gcd(p^k, m) are 1, p, p², …, p^k, and the only way to have gcd(p^k, m) > 1 is if m is a multiple of p, that is, m ∈ {p, 2p, 3p, …, p^{k − 1}p = p^k}, and there are p^{k − 1} such multiples not greater than p^k. Therefore, the other p^k − p^{k − 1} numbers are all relatively prime to p^k.

Proof of Euler’s product formula[edit]

The fundamental theorem of arithmetic states that if n > 1 there is a unique expression ${displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}},}$ where p₁ < p₂ < … < p_r are prime numbers and each k_i ≥ 1. (The case n = 1 corresponds to the empty product.) Repeatedly using the multiplicative property of φ and the formula for φ(p^k) gives

${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}-1}(p_{1}-1),p_{2}^{k_{2}-1}(p_{2}-1)cdots p_{r}^{k_{r}-1}(p_{r}-1)\[.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]&=&nleft(1-{frac {1}{p_{1}}}right)left(1-{frac {1}{p_{2}}}right)cdots left(1-{frac {1}{p_{r}}}right).end{array}}}$

This gives both versions of Euler’s product formula.

An alternative proof that does not require the multiplicative property instead uses the inclusion-exclusion principle applied to the set ${1,2,ldots ,n}$ , excluding the sets of integers divisible by the prime divisors.

Example[edit]

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

In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.

The alternative formula uses only integers:

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

Fourier transform[edit]

The totient is the discrete Fourier transform of the gcd, evaluated at 1.^[16] Let

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

where x_k = gcd(k,n) for k ∈ {1, …, n}. Then

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

The real part of this formula is

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

For example, using ${displaystyle cos {tfrac {pi }{5}}={tfrac {{sqrt {5}}+1}{4}}}$ and ${displaystyle cos {tfrac {2pi }{5}}={tfrac {{sqrt {5}}-1}{4}}}$ :

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

Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of n. However, it does involve the calculation of the greatest common divisor of n and every positive integer less than n, which suffices to provide the factorization anyway.

Divisor sum[edit]

The property established by Gauss,^[17] that

${displaystyle sum _{dmid n}varphi (d)=n,}$

where the sum is over all positive divisors d of n, can be proven in several ways. (See Arithmetical function for notational conventions.)

One proof is to note that φ(d) is also equal to the number of possible generators of the cyclic group C_d ; specifically, if C_d = ⟨g⟩ with g^d = 1, then g^k is a generator for every k coprime to d. Since every element of C_n generates a cyclic subgroup, and all subgroups C_d ⊆ C_n are generated by precisely φ(d) elements of C_n, the formula follows.^[18] Equivalently, the formula can be derived by the same argument applied to the multiplicative group of the nth roots of unity and the primitive dth roots of unity.

The formula can also be derived from elementary arithmetic.^[19] For example, let n = 20 and consider the positive fractions up to 1 with denominator 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}}.}$

Put them into lowest terms:

${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}}}$

These twenty fractions are all the positive k/d ≤ 1 whose denominators are the divisors d = 1, 2, 4, 5, 10, 20. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20; by definition this is φ(20) fractions. Similarly, there are φ(10) fractions with denominator 10, and φ(5) fractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of size φ(d) for each d dividing 20. A similar argument applies for any n.

Möbius inversion applied to the divisor sum formula gives

${displaystyle varphi (n)=sum _{dmid n}mu left(dright)cdot {frac {n}{d}}=nsum _{dmid n}{frac {mu (d)}{d}},}$

where μ is the Möbius function, the multiplicative function defined by ${displaystyle mu (p)=-1}$ and ${displaystyle mu (p^{k})=0}$ for each prime p and k ≥ 2. This formula may also be derived from the product formula by multiplying out ${textstyle prod _{pmid n}(1-{frac {1}{p}})}$ to get ${textstyle sum _{dmid n}{frac {mu (d)}{d}}.}$

An example:

${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]&=1cdot 20-1cdot 10+0cdot 5-1cdot 4+1cdot 2+0cdot 1=8.end{aligned}}}$

Some values[edit]

The first 100 values (sequence A000010 in the OEIS) are shown in the table and graph below:

Graph of the first 100 values

φ(n) for 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

In the graph at right the top line y = n − 1 is an upper bound valid for all n other than one, and attained if and only if n is a prime number. A simple lower bound is ${displaystyle varphi (n)geq {sqrt {n/2}}}$ , which is rather loose: in fact, the lower limit of the graph is proportional to n/log log n.^[20]

Euler’s theorem[edit]

This states that if a and n are relatively prime then

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

The special case where n is prime is known as Fermat’s little theorem.

This follows from Lagrange’s theorem and the fact that φ(n) is the order of the multiplicative group of integers modulo n.

The RSA cryptosystem is based on this theorem: it implies that the inverse of the function a ↦ a^e mod n, where e is the (public) encryption exponent, is the function b ↦ b^d mod n, where d, the (private) decryption exponent, is the multiplicative inverse of e modulo φ(n). The difficulty of computing φ(n) without knowing the factorization of n is thus the difficulty of computing d: this is known as the RSA problem which can be solved by factoring n. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing n as the product of two (randomly chosen) large primes p and q. Only n is publicly disclosed, and given the difficulty to factor large numbers we have the guarantee that no one else knows the factorization.

Other formulae[edit]

Menon’s identity[edit]

In 1965 P. Kesava Menon proved

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

where d(n) = σ₀(n) is the number of divisors of n.

Generating functions[edit]

The Dirichlet series for φ(n) may be written in terms of the Riemann zeta function as:^[26]

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

where the left-hand side converges for ${displaystyle Re (s)>2}$ .

The Lambert series generating function is^[27]

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

which converges for |q| < 1.

Both of these are proved by elementary series manipulations and the formulae for φ(n).

Growth rate[edit]

In the words of Hardy & Wright, the order of φ(n) is “always ‘nearly n‘.”^[28]

First^[29]

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

but as n goes to infinity,^[30] for all δ > 0

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

These two formulae can be proved by using little more than the formulae for φ(n) and the divisor sum function σ(n).

In fact, during the proof of the second formula, the inequality

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

true for n > 1, is proved.

We also have^[20]

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

Here γ is Euler’s constant, γ = 0.577215665…, so e^γ = 1.7810724… and e^−γ = 0.56145948….

Proving this does not quite require the prime number theorem.^[31]^[32] Since log log n goes to infinity, this formula shows that

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

In fact, more is true.^[33]^[34]^[35]

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

and

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

The second inequality was shown by Jean-Louis Nicolas. Ribenboim says “The method of proof is interesting, in that the inequality is shown first under the assumption that the Riemann hypothesis is true, secondly under the contrary assumption.”^[35]^: 173

For the average order, we have^[22]^[36]

${displaystyle varphi (1)+varphi (2)+cdots +varphi (n)={frac {3n^{2}}{pi ^{2}}}+Oleft(n(log n)^{frac {2}{3}}(log log n)^{frac {4}{3}}right)quad {text{as }}nrightarrow infty ,}$

due to Arnold Walfisz, its proof exploiting estimates on exponential sums due to I. M. Vinogradov and N. M. Korobov.
By a combination of van der Corput’s and Vinogradov’s methods, H.-Q. Liu (On Euler’s function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775)
improved the error term to

${displaystyle Oleft(n(log n)^{frac {2}{3}}(log log n)^{frac {1}{3}}right)}$

(this is currently the best known estimate of this type). The “Big O” stands for a quantity that is bounded by a constant times the function of n inside the parentheses (which is small compared to n²).

This result can be used to prove^[37] that the probability of two randomly chosen numbers being relatively prime is 6/π².

Ratio of consecutive values[edit]

In 1950 Somayajulu proved^[38]^[39]

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

In 1954 Schinzel and Sierpiński strengthened this, proving^[38]^[39] that the set

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

is dense in the positive real numbers. They also proved^[38] that the set

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

is dense in the interval (0,1).

Totient numbers[edit]

A totient number is a value of Euler’s totient function: that is, an m for which there is at least one n for which φ(n) = m. The valency or multiplicity of a totient number m is the number of solutions to this equation.^[40] A nontotient is a natural number which is not a totient number. Every odd integer exceeding 1 is trivially a nontotient. There are also infinitely many even nontotients,^[41] and indeed every positive integer has a multiple which is an even nontotient.^[42]

The number of totient numbers up to a given limit x is

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

for a constant C = 0.8178146….^[43]

If counted accordingly to multiplicity, the number of totient numbers up to a given limit x is

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

where the error term R is of order at most x/(log x)^k for any positive k.^[44]

It is known that the multiplicity of m exceeds m^δ infinitely often for any δ < 0.55655.^[45]^[46]

Ford’s theorem[edit]

Ford (1999) proved that for every integer k ≥ 2 there is a totient number m of multiplicity k: that is, for which the equation φ(n) = m has exactly k solutions; this result had previously been conjectured by Wacław Sierpiński,^[47] and it had been obtained as a consequence of Schinzel’s hypothesis H.^[43] Indeed, each multiplicity that occurs, does so infinitely often.^[43]^[46]

However, no number m is known with multiplicity k = 1. Carmichael’s totient function conjecture is the statement that there is no such m.^[48]

Perfect totient numbers[edit]

A perfect totient number is an integer that is equal to the sum of its iterated totients. That is, we apply the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number.

Applications[edit]

Cyclotomy[edit]

In the last section of the Disquisitiones^[49]^[50] Gauss proves^[51] that a regular n-gon can be constructed with straightedge and compass if φ(n) is a power of 2. If n is a power of an odd prime number the formula for the totient says its totient can be a power of two only if n is a first power and n − 1 is a power of 2. The primes that are one more than a power of 2 are called Fermat primes, and only five are known: 3, 5, 17, 257, and 65537. Fermat and Gauss knew of these. Nobody has been able to prove whether there are any more.

Thus, a regular n-gon has a straightedge-and-compass construction if n is a product of distinct Fermat primes and any power of 2. The first few such n are^[52]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,… (sequence A003401 in the OEIS).

Prime number theorem for arithmetic progressions[edit]

The RSA cryptosystem[edit]

Setting up an RSA system involves choosing large prime numbers p and q, computing n = pq and k = φ(n), and finding two numbers e and d such that ed ≡ 1 (mod k). The numbers n and e (the “encryption key”) are released to the public, and d (the “decryption key”) is kept private.

A message, represented by an integer m, where 0 < m < n, is encrypted by computing S = m^e (mod n).

It is decrypted by computing t = S^d (mod n). Euler’s Theorem can be used to show that if 0 < t < n, then t = m.

The security of an RSA system would be compromised if the number n could be efficiently factored or if φ(n) could be efficiently computed without factoring n.

Unsolved problems[edit]

Lehmer’s conjecture[edit]

If p is prime, then φ(p) = p − 1. In 1932 D. H. Lehmer asked if there are any composite numbers n such that φ(n) divides n − 1. None are known.^[53]

In 1933 he proved that if any such n exists, it must be odd, square-free, and divisible by at least seven primes (i.e. ω(n) ≥ 7). In 1980 Cohen and Hagis proved that n > 10²⁰ and that ω(n) ≥ 14.^[54] Further, Hagis showed that if 3 divides n then n > 10^1937042 and ω(n) ≥ 298848.^[55]^[56]

Carmichael’s conjecture[edit]

This states that there is no number n with the property that for all other numbers m, m ≠ n, φ(m) ≠ φ(n). See Ford’s theorem above.

As stated in the main article, if there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.^[40]

Riemann hypothesis[edit]

The Riemann hypothesis is true if and only if the inequality

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

is true for all n ≥ p₁₂₀₅₆₉# where γ is Euler’s constant and p₁₂₀₅₆₉# is the product of the first 120569 primes.^[57]

Notes[edit]

^ “Euler’s totient function”. Khan Academy. Retrieved 2016-02-26.
^ Long (1972, p. 85)
^ Pettofrezzo & Byrkit (1970, p. 72)
^ Long (1972, p. 162)
^ Pettofrezzo & Byrkit (1970, p. 80)
^ See Euler’s theorem.
^ L. Euler “Theoremata arithmetica nova methodo demonstrata” (An arithmetic theorem proved by a new method), Novi commentarii academiae scientiarum imperialis Petropolitanae (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: Ferdinand Rudio, ed., Leonhardi Euleri Commentationes Arithmeticae, volume 1, in: Leonhardi Euleri Opera Omnia, series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), pages 531–555. On page 531, Euler defines n as the number of integers that are smaller than N and relatively prime to N (… aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, …), which is the phi function, φ(N).
^ ^a ^b Sandifer, p. 203
^ Graham et al. p. 133 note 111
^ L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).
^ Both φ(n) and ϕ(n) are seen in the literature. These are two forms of the lower-case Greek letter phi.
^ Gauss, Disquisitiones Arithmeticae article 38
^ Cajori, Florian (1929). A History Of Mathematical Notations Volume II. Open Court Publishing Company. §409.
^ J. J. Sylvester (1879) “On certain ternary cubic-form equations”, American Journal of Mathematics, 2 : 357-393; Sylvester coins the term “totient” on page 361.
^ “totient”. Oxford English Dictionary (2nd ed.). Oxford University Press. 1989.
^ Schramm (2008)
^ Gauss, DA, art 39
^ Gauss, DA art. 39, arts. 52-54
^ Graham et al. pp. 134-135
^ ^a ^b Hardy & Wright 1979, thm. 328
^ Dineva (in external refs), prop. 1
^ ^a ^b ^c Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (in German). Vol. 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.
^ Lomadse, G. (1964), “The scientific work of Arnold Walfisz” (PDF), Acta Arithmetica, 10 (3): 227–237, doi:10.4064/aa-10-3-227-237
^ ^a ^b Sitaramachandrarao, R. (1985). “On an error term of Landau II”. Rocky Mountain J. Math. 15 (2): 579–588. doi:10.1216/RMJ-1985-15-2-579.
^ Bordellès in the external links
^ Hardy & Wright 1979, thm. 288
^ Hardy & Wright 1979, thm. 309
^ Hardy & Wright 1979, intro to § 18.4
^ Hardy & Wright 1979, thm. 326
^ Hardy & Wright 1979, thm. 327
^ In fact Chebyshev’s theorem (Hardy & Wright 1979, thm.7) and
Mertens’ third theorem is all that is needed.
^ Hardy & Wright 1979, thm. 436
^ Theorem 15 of Rosser, J. Barkley; Schoenfeld, Lowell (1962). “Approximate formulas for some functions of prime numbers”. Illinois J. Math. 6 (1): 64–94. doi:10.1215/ijm/1255631807.
^ Bach & Shallit, thm. 8.8.7
^ ^a ^b Ribenboim (1989). “How are the Prime Numbers Distributed? §I.C The Distribution of Values of Euler’s Function”. The Book of Prime Number Records (2nd ed.). New York: Springer-Verlag. pp. 172–175. doi:10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5.
^ Sándor, Mitrinović & Crstici (2006) pp.24–25
^ Hardy & Wright 1979, thm. 332
^ ^a ^b ^c Ribenboim, p.38
^ ^a ^b Sándor, Mitrinović & Crstici (2006) p.16
^ ^a ^b Guy (2004) p.144
^ Sándor & Crstici (2004) p.230
^ Zhang, Mingzhi (1993). “On nontotients”. Journal of Number Theory. 43 (2): 168–172. doi:10.1006/jnth.1993.1014. ISSN 0022-314X. Zbl 0772.11001.
^ ^a ^b ^c Ford, Kevin (1998). “The distribution of totients”. Ramanujan J. Developments in Mathematics. 2 (1–2): 67–151. arXiv:1104.3264. doi:10.1007/978-1-4757-4507-8_8. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053.
^ Sándor et al (2006) p.22
^ Sándor et al (2006) p.21
^ ^a ^b Guy (2004) p.145
^ Sándor & Crstici (2004) p.229
^ Sándor & Crstici (2004) p.228
^ Gauss, DA. The 7th § is arts. 336–366
^ Gauss proved if n satisfies certain conditions then the n-gon can be constructed. In 1837 Pierre Wantzel proved the converse, if the n-gon is constructible, then n must satisfy Gauss’s conditions
^ Gauss, DA, art 366
^ Gauss, DA, art. 366. This list is the last sentence in the Disquisitiones
^ Ribenboim, pp. 36–37.
^ Cohen, Graeme L.; Hagis, Peter Jr. (1980). “On the number of prime factors of n if φ(n) divides n − 1“. Nieuw Arch. Wiskd. III Series. 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.
^ Hagis, Peter Jr. (1988). “On the equation M·φ(n) = n − 1“. Nieuw Arch. Wiskd. IV Series. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
^ Guy (2004) p.142
^ Broughan, Kevin (2017). Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents (First ed.). Cambridge University Press. ISBN 978-1-107-19704-6. Corollary 5.35

References[edit]

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of Gauss’ papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

References to the Disquisitiones are of the form Gauss, DA, art. nnn.

Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4. See paragraph 24.3.2.
Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press, ISBN 0-262-02405-5, Zbl 0873.11070
Dickson, Leonard Eugene, “History Of The Theory Of Numbers”, vol 1, chapter 5 “Euler’s Function, Generalizations; Farey Series”, Chelsea Publishing 1952
Ford, Kevin (1999), “The number of solutions of φ(x) = m“, Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326, Zbl 0978.11053.
Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae (Second, corrected edition), translated by Clarke, Arthur A., New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), translated by Maser, H., New York: Chelsea, ISBN 0-8284-0191-8
Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994), Concrete Mathematics: a foundation for computer science (2nd ed.), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl 0836.00001
Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics (3rd ed.), New York, NY: Springer-Verlag, ISBN 0-387-20860-7, Zbl 1058.11001
Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 0-387-94457-5, Zbl 0856.11001
Sandifer, Charles (2007), The early mathematics of Leonhard Euler, MAA, ISBN 978-0-88385-559-1
Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Handbook of number theory I, Dordrecht: Springer-Verlag, pp. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300
Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
Schramm, Wolfgang (2008), “The Fourier transform of functions of the greatest common divisor”, Electronic Journal of Combinatorial Number Theory, A50 (8(1)).

External links[edit]

“Totient function”, Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Euler’s Phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative
Euler’s totient function calculator in JavaScript — up to 20 digits
Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions
Plytage, Loomis, Polhill Summing Up The Euler Phi Function

Источник

Что такое Тотиентная функция Эйлера?

Общая функция Эйлера — это математическая мультипликативная функция, которая подсчитывает положительные целые числа до заданного целого числа, обычно называемого «n», которое является простым числом до «n». Можно использовать эту функцию, чтобы узнать количество простых чисел, которые существуют до заданного целого числа n.

Оглавление

Что такое Тотиентная функция Эйлера?
- Объяснение
- История
- Свойства функции Тотиента Эйлера
- Вычислите функцию Эйлера Тотиент
  - Пример №1
  - Пример #2
  - Пример №3
  - Пример №4
- Приложения
- Заключение
- Рекомендуемые статьи

Объяснение

Тотальную функцию Эйлера можно использовать, чтобы узнать, сколько простых чисел подходит к заданному целому числу n. Ее также называют арифметической функцией. Две вещи важны для приложения или использования функции Эйлера totient. Во-первых, НОД, образованный из заданного целого числа «n», должен быть мультипликативным. Во-вторых, числа gcd должны быть только простыми числами. Целое число n в этом случае должно быть больше 1. Вычисление общей функции Эйлера из отрицательного целого числа невозможно. Принцип в этом случае состоит в том, что для ϕ(n) мультипликаторы с именами m и n должны быть больше 1. Следовательно, обозначается как 1

История

Эйлер ввел эту функцию в 1763 году. Первоначально Эйлер использовал греческую Пи для обозначения функции, но из-за некоторых проблем его обозначение греческого π не получить признание. И он не смог дать ему правильный знак записи, т. е. ϕ. Следовательно, он не может ввести функцию. Кроме того, ϕ был взят из «Арифметических исследований» Гаусса 1801 года. Эта функция также известна как фи-функция. Но Дж. Дж. Сильвестр в 1879 году включил термин totient для этой функции из-за ее свойств и использования. Различные правила имеют дело с различными типами целых чисел, например, если целое число p является простым числом, то какое правило следует применять и т. д. Эйлер формулирует все правила как практически выполнимые. Поэтому его можно использовать и сегодня, имея дело с тем же самым.

Свойства функции Тотиента Эйлера

Есть несколько разных свойств. Некоторые из свойств тотиентной функции Эйлера:

Φ — символ, используемый для обозначения функции.
Функция имеет дело с теорией простых чисел.
Функция применима только в случае положительных целых чисел.
Для ϕ (n) можно найти два мультипликативных простых числа для вычисления функции.
Функция является математической функцией и полезна во многих отношениях.
Если целое число n — простое число, то НОД (m, n) = 1.
Функция работает по формуле 1< m< n, где m и n — простые и мультипликативные числа.
В общем, уравнение такое:

Φ(mn) = ϕ(m) * ϕ(n) (1- 1/m) (1 – 1/ n)

Функция Эйлера-Тотиента

Функция подсчитывает количество положительных целых чисел меньше заданного целого числа, которое является относительно простым числом к заданному целому числу.
Если заданное целое число p простое, то ϕ (p) = p – 1
Если степень p простая, то если a = pn — степень простого числа, то ϕ (pn) = pn — p ( n-1)
ϕ(n) не один – один
ϕ (n) не на.
ϕ (n), n > 3, всегда четно.
ϕ( 10n) = 4 * 10n-1

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

Пример №1

Рассчитать ϕ (7)?

Решение:

ф ( 7 ) = (1,2,3,4,5,6) = 6

Поскольку все числа являются простыми до 7, это упростило вычисление ϕ.

Пример #2

Рассчитать ϕ ( 100 )?

Решение:

Поскольку 100 — большое число, требуется много времени, чтобы вычислить от 1 до 100 простых чисел, которые являются простыми числами со 100. Следовательно, мы применяем следующую формулу:

ϕ (100) = ϕ (м) * ϕ (n) (1- 1 / m) (1 – 1/ n)
ϕ (100) = 2 2 * 2 5
ϕ (100) = 2 2 * 2 5 * (1 – 1/2) * ( 1 – 1/5)
= 100 * 1/2 * 4/5
= 40

Пример №3

Рассчитать ϕ (240)?

Число, кратное 240, равно 16*5*3, т.е. 2 4 * 5 * 3.

ϕ (240) = ϕ (м) * ϕ (n) (1- 1 / m) (1 – 1/ n)
ϕ (240) = 2 4 * 5 * 3

если nM не является простым числом, мы используем nm – nm-1

= (2 4 – 2 (4-1) ) * (51 – 5 (1-1)) * (3 1 – 3 (1-1))
= (2 4 – 2 3) * (5 – 1) * (3 – 1)
= 64

Пример №4

Рассчитать ϕ ( 49 )?

ϕ (49) = ϕ (м) * ϕ (n) (1- 1 / m) (1 – 1/ n)
ϕ (49) = ϕ (7) * ϕ (7)
= (71 – 7(1-1)) * (71 – 7(1-1))
= (7-1) * (7-1)
= 6 * 6
= 36

Приложения

Различные приложения, как показано ниже:

Можно использовать эту функцию для определения системы шифрования RSA, используемой для шифрования безопасности в Интернете.
Его можно использовать в теории простых чисел.
Его можно использовать и в больших вычислениях.
Его можно использовать в приложениях элементарной теории чисел.

Заключение

Тотиентная функция Эйлера полезна во многих отношениях. Его можно использовать в системе шифрования RSA в целях безопасности. Функция имеет дело с теорией простых чисел, а также полезна при расчете больших вычислений. Эту функцию также можно использовать в алгебраических вычислениях и элементарных числах. Для обозначения функции используется символ ϕ, также называемый фи-функцией. Функция состоит больше из теоретического использования, а не практического использования. Практическое использование функции ограничено. Функцию можно понять на различных практических примерах, а не на теоретических объяснениях. Существуют разные правила вычисления функции Эйлера, и к разным числам применяются разные правила. Впервые функция была введена в 1763 году. Из-за некоторых проблем она получила признание в 1784 году, а название было изменено в 1879 году. Функция универсальна и может применяться повсеместно.

Вычисление[править | править код]

Общие сведения[править | править код]

Мультипликативность функции Эйлера[править | править код]

Функция Эйлера от простого числа[править | править код]

Функция Эйлера от натурального числа[править | править код]

Свойства[править | править код]

Обобщённая мультипликативность[править | править код]

Теорема Эйлера[править | править код]

Другие свойства[править | править код]

Множество значений[править | править код]

Асимптотические соотношения[править | править код]

Простейшие неравенства[править | править код]

Сравнение φ(n) с n[править | править код]

Отношение последовательных значений[править | править код]

Асимптотики для сумм[править | править код]

Порядок функции Эйлера[править | править код]

Связь с другими функциями[править | править код]

Функция Мёбиуса[править | править код]

Ряд Дирихле[править | править код]

Ряд Ламберта[править | править код]

Наибольший общий делитель[править | править код]

Связь с латинскими квадратами[править | править код]

Приложения и примеры[править | править код]

Функция Эйлера в RSA[править | править код]

Вычисление обратного элемента[править | править код]

Решение линейного сравнения[править | править код]

Вычисление остатка от деления[править | править код]

Нахождение порядка мультипликативной группы кольца вычетов[править | править код]

Приложения в теории групп[править | править код]

Нерешенные вопросы[править | править код]

Задача Лемера[править | править код]

Гипотеза Кармайкла[править | править код]

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]

Интересное и простое из комбинаторики. Функция Эйлера

Предисловие

Сколько вариантов расставить n предметов?

Способ №1

Способ №2

Как из n предметов выбрать k предметов?

Способ №1

Способ №2

Числа Фибоначчи

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

Способ №1

Способ №2

Способ №3

Расчет значения функции Эйлера

History, terminology, and notation[edit]

Computing Euler’s totient function[edit]

Euler’s product formula[edit]

Phi is a multiplicative function[edit]

Value of phi for a prime power argument[edit]

Proof of Euler’s product formula[edit]

Example[edit]

Fourier transform[edit]

Divisor sum[edit]

Some values[edit]

Euler’s theorem[edit]

Other formulae[edit]

Menon’s identity[edit]

Generating functions[edit]

Growth rate[edit]

Ratio of consecutive values[edit]

Totient numbers[edit]

Ford’s theorem[edit]

Perfect totient numbers[edit]

Applications[edit]

Cyclotomy[edit]

Prime number theorem for arithmetic progressions[edit]

The RSA cryptosystem[edit]

Unsolved problems[edit]

Lehmer’s conjecture[edit]

Carmichael’s conjecture[edit]

Riemann hypothesis[edit]

See also[edit]

Notes[edit]

References[edit]