Funkcja φ

Funkcja φ (Eulera) lub tocjent – funkcja przypisująca każdej liczbie naturalnej liczbę liczb względnie pierwszych z nią i nie większych od niej. Nazwa pochodzi od nazwiska Leonharda Eulera.

Kilka początkowych wartości funkcji $\varphi (n)$:

$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

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

Własności

• Dla każdej liczby naturalnej $n>1$:

$\varphi (n)\leq n-1.$

• 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 $p$ jest liczbą pierwszą, to

$\varphi (p^{k})=p^{k-1}\cdot (p-1).$

• Jeżeli $p_{1},p_{2},\dots ,p_{k}$ są wszystkimi czynnikami pierwszymi liczby $n$ liczonymi bez powtórzeń, to

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

• 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}}).$

Zobacz też

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

Bibliografia

• Wacław Sierpiński: Arytmetyka Teoretyczna. Warszawa: Państwowe Wydawnictwo Naukowe, 1969, s. 133–135, seria: Biblioteka Matematyczna t. 7.
• Władysław Narkiewicz: Teoria Liczb. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 33, 68, 71–72, seria: Biblioteka Matematyczna t. 50.