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$$\varphi$ Eulera dana jest dla każdej liczby naturalnej $n$$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),$$\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}$$p_1, p_2, \dots, p_k$ są wszystkimi czynnikami pierwszymi liczby $n$$n$ liczonymi bez powtórzeń.

Własności

• Jeżeli $p$$p$ jest pierwsza, to każda z liczb $1,2,\dots ,p-1$$1, 2, \dots, p-1$ jest względnie pierwsza z $p$$p$, więc:

  $\varphi (p)=p-1$$\varphi(p)=p-1$

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

  $\varphi (mn)=\varphi (m)\varphi (n)$$\varphi(mn)=\varphi(m)\varphi(n)$

• Jeżeli $n=p^{k}$$n = p^k$, to

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

• Jeżeli $n$$n$ nie ma wielokrotnych dzielników pierwszych, tj.

  $n=p_{1}p_{2}\dots p_{k}$$n=p_1 p_2 \dots p_k$

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

$\varphi (n)=(p_{1}-1)(p_{2}-1)\dots (p_{k}-1)$$\varphi(n)=(p_1-1) (p_2-1) \dots (p_k-1)$

• Dla dowolnej liczby całkowitej $n$$n$ zachodzi:

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

(sumowanie przebiega wszystkie dzielniki liczby $n$$n$).

• Jeżeli

  $n=\prod _{i=1}^{k}p_{i}^{k_{i}}$$n=\prod_{i=1}^kp_i^{k_i}$

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

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

Przykład

$n$$n$	1	2	3	4	5	6	7	8	9	10	11	12
$\varphi (n)$$\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 π