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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

n=p_{1}^{k_1} \ldots p_{r}^{k_r},

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

\varphi(n)=(p_{1}-1) p_{1}^{k_{1}-1} \ldots (p_{r}-1)p_{r}^{k_{r}-1}.

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

\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

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

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

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

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

\sum_{d\mid n}\varphi(d)=n

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

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

\varphi(n)=\sum_{d\mid n} d \mu(n/d)

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

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

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

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

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

\sum_{n=1}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

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

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

за |q|<1.

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

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

n^{1-\varepsilon}<\varphi(n)<n

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

\varphi(n) \over n

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

1-p^{-1} \,

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

C\frac{\log \log n}{\log n}.

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

\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\ln n }{n}\right)

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

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

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

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

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

\varphi(n) \ge \sqrt{\frac {n} {2} }

за n > 0, и

\varphi(n) \ge \sqrt{n}

за n > 6.

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

\varphi(n) \le n-\sqrt{n}.

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

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

за n > 1.

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

φ(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