Funkcja φ

Funkcja φ (Eulera) lub tocjent – funkcja przypisująca każdej liczbie naturalnej liczbę (ilość) liczb które są z nią względnie pierwsze i nie większe od niej (liczymy również 1). Nazwa pochodzi od nazwiska Leonharda Eulera. Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.

Pierwsze 100 wartości funkcji φ(n):

+ 12345678910
0 1122426464
10 10412688166188
20 121022820121812288
30 30162016241236182416
40 40124220242246164220
50 32245218402436285816
60 60303632482066324424
70 70247236403660247832
80 54408224644256408824
90 72446046723296426040

Obliczanie

Jeśli p1α1p2α2⋅…⋅pkαk jest rozkładem liczby n na czynniki pierwsze pi o nietrywialnych wykładnikach, αi⩾1, to

φ(n)=φ(p1α1p2α2⋅…⋅pkαk)=φ(p1α1)φ(p2α2)⋅…⋅φ(pkαk)=p1α1−1(p1−1)⋅p2α2−1(p2−1)⋅…⋅pkαk−1(pk−1),

co wynika z wymienionych niżej własności tej funkcji.

Własności

φ(n)⩽n−1.
φ(p)=p−1.
φ(mn)=φ(m)φ(n).
φ(pk)=pk−1⋅(p−1).
φ(n)=n(1−1p1)(1−1p2)…(1−1pk).
n=p1p2…pk,
gdzie liczby pi są pierwsze i parami różne (i=1,…,k), to
φ(n)=(p1−1)(p2−1)…(pk−1).
∑m|nφ(m)=n
(sumowanie obejmuje wszystkie dzielniki liczby n).

Zobacz też