Funkcja φ

Funkcja φ (Eulera) lub tocjent – funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych nie większych od niej samej.

Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.

Funkcja $\varphi$ Eulera dana jest dla każdej liczby naturalnej $n$ wzorem

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

gdzie $p_1, p_2, \dots, p_k$ są wszystkimi czynnikami pierwszymi liczby $n$ liczonymi bez powtórzeń.

Własności

• 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 $n = p^k$, to

  $\varphi(n) = p^{k - 1}*(p-1)$

• 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 przebiega wszystkie dzielniki liczby $n$).

• Jeżeli

  $n=\prod_{i=1}^kp_i^{k_i}$

jest rozkładem liczby $n$ na czynniki pierwsze to

$\varphi(n)=\prod_{i=1}^k \varphi(p_i^{k_i})$

Przykład

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4	10	4

Zobacz też

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