Funkcja φ

Funkcja φ (Eulera) lub tocjent – funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej ilość 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}-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:

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

(sumowanie przebiega wszystkie dzielniki liczby $n$).

• Jeżeli

  $n=\prod _{i=1}^{k}p_{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ż

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