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

от Уикипедия, свободната енциклопедия

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

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

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

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

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

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

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

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

Числото φ(n) също се равнява на броя на генераторите на цикличната група C_n. Тъй като всеки елемент от C_n генерира циклична подгрупа и подгрупите на C_n са от вида C_d, където 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.$

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

Ред на Дирихле, включващ φ(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.

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

Нарастването на φ(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 е символът на Ландау.

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

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

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

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

$\varphi(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

Взето от „http://bg.wikipedia.org../../../%D1%84/%D1%83/%D0%BD/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%BD%D0%B0_%D0%9E%D0%B9%D0%BB%D0%B5%D1%80_67d7.html“.

Категории: Аритметични функции

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

от Уикипедия, свободната енциклопедия

Съдържание

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

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

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

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

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

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

Views

Навигация

Търсене

На други езици

$\varphi(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

$\varphi(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

$\varphi(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