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

от Уикипедия, свободната енциклопедия
Първите хиляда стойности на φ(n). Точките върху горната права представляват φ(p), когато p е просто число, като p − 1.[1]

В теорията на числата функцията на Ойлер, наричана още Тотиента и отбелязвана с φ(n) е функция, дефинирана за произволно положително цяло число n, като броя на естествените числа, ненадминаващи n и взаимно прости с n. Например φ(8) = 4, защото нечетните числа 1, 3, 5 и 7 са взаимно прости с 8, а φ(9) = 6, защото числата 1, 2, 4, 5, 7 и 8 са взаимно прости с 9. Функцията е наречена на швейцарския математик Леонард Ойлер, който е изследвал много от нейните свойства.

Изчисляване на функцията на Ойлер[редактиране | редактиране на кода]

Непосредствено от определението на функцията следва, че φ(1) = 1, а φ(n) = (p − 1)pk−1, когато n е k-та степен на просто число pk. Също така функцията е мултипликативна, т.е. когато m и n са взаимно прости φ(mn) = φ(m)φ(n). Следователно стойността на φ(n) може да бъде изчислена посредством разлагане на прости множители (което съгласно основната теорема на аритметиката е единствено):

,

където pi са различни прости числа, и следователно

.

Последната формула се нарича произведение на Ойлер и често се записва като:

където произведението се извършва по простите числа pi с ненулева степен в разлагането на n на прости множители.

Алгоритмичен начин за намиране на всички стойности на φ(x) за x=1..n е така нареченото Тотиентно решето, подобно на решетото на Ератостен.

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

Числото φ(n) също се равнява на броя на генераторите на цикличната група Cn. Тъй като всеки елемент от Cn генерира циклична подгрупа и подгрупите на Cn са от вида Cd, където d дели n (означава се като d|n), получаваме

където сумата е върху всички положителни делители d на n.

Прилагайки формулата на Мьобиус за обръщане, може да се „обърне“ сумата и да се получи друга формула за φ(n):

където μ е обикновената функция на Мьобиус, дефинирана за положителни цели числа.

Ако a е взаимно просто с n, т.е. НОД(a,n) = 1, то

Пораждаща функция|Пораждащи функции[редактиране | редактиране на кода]

Ред на Дирихле, включващ φ(n), е

Функция, пораждаща ред на Ламберт, e

за |q|<1.

Нарастване на функцията[редактиране | редактиране на кода]

Нарастването на φ(n) като функция на n е интересен въпрос, тъй като първото впечатление при малки n, че φ(n) би могла да бъде значително по-малка от n, е донякъде подвеждащо. Асимптотично

за всяко ε > 0 и n > N(ε). Всъщност за

това може да се запише от горната формула като произведение на множители от типа

взети за простите числа p, които са делители на n. Следователно стойностите на n, съответстващи на особено малки стойности на съотношението, са тези n, които са произведение на един начален сегмент от редицата от всички прости числа. От теоремата за простите числа може да се види, че константата ε в горната формула може следователно да се замени с

.

Това поведение е валидно и за средната оценка

където главното O е символът на Ландау.

Неравенства[редактиране | редактиране на кода]

Някои неравенства, включващи φ-функцията, са:

за n > 2, където γ е Ойлеровата константа,

за n > 0, и

за n > 6.

За прости n очевидно φ(n) = n−1. За съставно n имаме

.

Двойка неравенства, комбиниращи φ-функцията и σ-функцията, са

за n > 1.

Някои стойности[редактиране | редактиране на кода]

φ(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0 1 1 2 2 4 2 6 4 6 4 10
12 4 12 6 8 8 16 6 18 8 12 10 22
24 8 20 12 18 12 28 8 30 16 20 16 24
36 12 36 18 24 16 40 12 42 20 24 22 46
48 16 42 20 32 24 52 18 40 24 36 28 58
60 16 60 30 36 32 48 20 66 32 44 24 70
72 24 72 36 40 36 60 24 78 32 54 40 82

Източници[редактиране | редактиране на кода]

  1. Euler's totient function // Khan Academy.