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 $\varphi (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}\geq 1$, to

$\varphi (n)=\prod _{i=1}^{k}\varphi \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{:}$

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

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

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

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

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

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

$\varphi (n)=n\left(1-{\tfrac {1}{p_{1}}}\right)\left(1-{\tfrac {1}{p_{2}}}\right)\dots \left(1-{\tfrac {1}{p_{k}}}\right).$

• 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

$\varphi (n)=(p_{1}-1)(p_{2}-1)\dots (p_{k}-1).$

• Dla dowolnej liczby całkowitej $n$ zachodzi

$\sum _{m|n}\varphi (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

• Wacław Sierpiński: Arytmetyka Teoretyczna. Warszawa: Państwowe Wydawnictwo Naukowe, 1969, s. 133–135, seria: Biblioteka Matematyczna t. 7.
• Władysław Narkiewicz: Teoria Liczb. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 33, 68, 71–72, seria: Biblioteka Matematyczna t. 50.

Linki zewnętrzne

• Witold Bednarek: Funkcja Eulera. „Delta”, październik 2019. [dostęp 2019-10-02]. (pol.).