Funkcja φ

Funkcja φ (Eulera) lub tocjent – funkcja przypisująca każdej liczbie naturalnej liczbę liczb względnie pierwszych z nią i nie większych od niej. Nazwa pochodzi od nazwiska Leonharda Eulera. Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.

Pierwsze 100 wartości funkcji $\phi (n):$

+	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

Obliczanie

Jeśli $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}...p_k^{{\alpha }_k}$ jest rozkładem liczby $n$ na czynniki pierwsze $p_i$, przy czym ${\alpha }_i\ge 1$, to

$\phi (n)=\prod _{i=1}^k\phi \left(p_i^{{\alpha }_i}\right)=\prod _{i=1}^k{p}_i^{{\alpha }_i-1}\cdot (p_i-1)$,

co wynika z multiplikatywności tej funkcji.

Własności

• Dla każdej liczby naturalnej $n>1:$

$\phi (n)⩽n-1.$

• Jeżeli $p$ jest pierwsza, to każda z liczb $1,2,\dots ,p-1$ jest względnie pierwsza z $p,$ więc

$\phi (p)=p-1$.

• Jeżeli liczby całkowite $m,n$ są względnie pierwsze, to

$\phi (mn)=\phi (m)\phi (n).$

• Jeżeli $p$ jest liczbą pierwszą, to

$\phi (p^k)=p^{k-1}\cdot (p-1).$

• Jeżeli $p_1,p_2,\dots ,p_k$ są wszystkimi czynnikami pierwszymi liczby $n$ liczonymi bez powtórzeń, to

$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k}).$

• Jeżeli $n$ nie ma wielokrotnych dzielników pierwszych, tj.

$n=p_1{p}_2\dots p_k,$

gdzie liczby $p_i$ są pierwsze i parami różne $(i=1,\dots ,k),$ to

$\phi (n)=(p_1-1)(p_2-1)\dots (p_k-1).$

• Dla dowolnej liczby całkowitej $n$ zachodzi

$\sum _{m|n}\phi (m)=n$

(sumowanie obejmuje wszystkie dzielniki liczby $n$).

Zobacz też

• chińskie twierdzenie o resztach
• funkcja Carmichaela
• funkcja π
• małe twierdzenie Fermata
• RSA
• twierdzenie Eulera

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:Otwarty dostęp Szablon:Cytuj stronę