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 φ 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:

  φ(p) = p − 1

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

  φ(mn) = φ(m)φ(n)

• Jeżeli n = p^k, to

  φ(n) = p^k − p^{k − 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:

∑	φ(m) = n,
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
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4

Zobacz też

• chińskie twierdzenie o resztach
• małe twierdzenie Fermata
• RSA
• funkcja Carmichaëla
• funkcja π