Funkcja φ

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Funkcja φ (Eulera) lub tocjentfunkcja 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[edytuj | edytuj kod]

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)
(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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]