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]}. 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

Obliczanie

Jeśli ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{k}^{\alpha _{k}}}$ jest rozkładem liczby ${\displaystyle n}$ na czynniki pierwsze ${\displaystyle p_{i}}$, przy czym ${\displaystyle \alpha _{i}\geqslant 1}$, to

${\displaystyle \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^[6].

Własności

• 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^[7]

${\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^[7]

${\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^[8]

${\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.^[8]

${\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^[9]

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

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

Zobacz też

Zobacz w Wikiźródłach tabelę wartości funkcji φ

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

Uwagi

1. W Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę funkcja Gaussa.