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^[1]. Nazwa pochodzi od nazwiska Leonharda Eulera^{[a][2][3][4][5.1]}. 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 ${\displaystyle \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

Jeśli ${\displaystyle p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}}$ jest rozkładem liczby ${\displaystyle n}$ na czynniki pierwsze ${\displaystyle p_{i}}$ o nietrywialnych wykładnikach, ${\displaystyle \alpha _{i}\geqslant 1}$, to

${\displaystyle \varphi (n)=\varphi \left(p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\right)=\varphi \left(p_{1}^{\alpha _{1}}\right)\varphi \left(p_{2}^{\alpha _{2}}\right)\cdot \ldots \cdot \varphi \left(p_{k}^{\alpha _{k}}\right)=p_{1}^{\alpha _{1}-1}(p_{1}-1)\cdot p_{2}^{\alpha _{2}-1}(p_{2}-1)\cdot \ldots \cdot p_{k}^{\alpha _{k}-1}(p_{k}-1)}$,

co wynika z wymienionych niżej własności tej funkcji^[6].

• Dla każdej liczby naturalnej ${\displaystyle n>1{:}}$

${\displaystyle \varphi (n)\leqslant n-1.}$

• Jeżeli ${\displaystyle p}$ jest pierwsza, to każda z liczb ${\displaystyle 1,2,\dots ,p-1}$ jest względnie pierwsza z ${\displaystyle p,}$ więc^[5.2]

${\displaystyle \varphi (p)=p-1}$^[2].

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

${\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}$

• Jeżeli ${\displaystyle p}$ jest liczbą pierwszą, to^[5.2]

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

• Jeżeli ${\displaystyle p_{1},p_{2},\dots ,p_{k}}$ są wszystkimi czynnikami pierwszymi liczby ${\displaystyle n}$ liczonymi bez powtórzeń, to^[5.3]

${\displaystyle \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 ${\displaystyle n}$ nie ma wielokrotnych dzielników pierwszych, tj.^[5.3]

${\displaystyle n=p_{1}p_{2}\dots p_{k},}$

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

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

• Dla dowolnej liczby całkowitej ${\displaystyle n}$ zachodzi^[5.4]

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

(sumowanie obejmuje wszystkie dzielniki liczby ${\displaystyle n}$).

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

• 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.

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