Funkcja φ

Z Wikipedii

Funkcje matematyczne

dziedzina • obraz • przeciwobraz

Funkcje elementarne

Funkcje algebraiczne:
wymierna • wielomian
stała • liniowa • kwadratowa
homograficzna

Funkcje przestępne:
trygonometryczne • cyklometryczne
hiperboliczne • area
wykładnicza • logarytmiczna
potęgowa

Funkcje specjalne

błędu • Γ • Β (beta) • η • W Lamberta Bessela • ζ

Funkcje teorioliczbowe

Möbiusa • φ • π • λ

Własności

Przebieg zmienności:
parzystość • monotoniczność ograniczoność • okresowość różnowartościowość • suriektywność • wzajemna jednoznaczność

ciągłość • różniczkowalność
całkowalność

Funkcja φ Eulera (inaczej tocjent) – funkcja matematyczna, która każdej liczbie naturalnej n przypisuje liczbę tych liczb względnie pierwszych z n, które są mniejsze od n. Na przykład, φ(6)=2, bo spośród liczb naturalnych mniejszych od 6 tylko liczby 1 i 5 są względnie pierwsze z 6.

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

Spis treści

1 Własności
2 Wartości funkcji φ(n) dla kilku początkowych n
3 Zobacz też

[edytuj] Własności

[edytuj] Wzór ogólny

Można udowodnić, że dla każdej liczby naturalnej n prawdziwy jest wzór:

$\varphi(n)=n\cdot\left(1-\frac{1}{p_1}\right)\cdot\left(1-\frac{1}{p_2}\right)\cdot\ldots\cdot\left(1-\frac{1}{p_k}\right)$

gdzie $p_1, p_2,\ldots,p_k$ są wszystkimi dzielnikami pierwszymi n.

[edytuj] Wartość dla liczb pierwszych

Jeżeli p jest liczbą pierwszą to każda z liczb 1,2,...p-1 jest względnie pierwsza z p, więc:

$\varphi(p)=p-1$

[edytuj] Wartość dla liczb względnie pierwszych

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

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

[edytuj] Wartość dla potęg liczb pierwszych

Jeżeli n=p^k to

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

[edytuj] Wartość dla liczb bez wielokrotnych dzielników

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

$n=p_1\cdot p_2\cdot\ldots\cdot p_k\cdot$

gdzie liczby p_i są pierwsze i parami różne, to

$\varphi(n)=(p_1-1)\cdot (p_2-1)\cdot\ldots\cdot (p_k-1)\cdot$

[edytuj] Zależność od wartości funkcji dla podzielników

Dla dowolnej liczby całkowitej n zachodzi:

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

gdzie sumowanie przebiega przez wszystkie dzielniki liczby n.

[edytuj] Dowód

Niech

$n=\prod_{i=1}^k p_i^{k_i}$

będzie rozkładem n na czynniki pierwsze. Rozważmy następujący iloczyn:

$\prod_{i=1}^k \sum_{j=0}^{k_i} \varphi(p_i^{j})=\prod_{i=1}^k (\varphi(1)+\varphi(p_i)+...+\varphi(p_i^{k_i}))$

Zgodnie z podaną wyżej własnością funkcji Eulera dla liczb będących potęgami liczb pierwszych iloczyn ten jest równy

$\prod_{i=1}^k (1+(p_i-1)+...+(p_i^{k_i}-p_i^{k_i-1}))=\prod_{i=1}^k p_i^{k_i}=n$

Z drugiej strony jeśli wymnożymy ów iloczyn dostaniemy długą sumę, w której dla każdego podzielnika n znajdzie się jeden składnik. Istotnie, podzielnikowi

$m=\prod_{i=1}^k p_i^{k'_i}$

gdzie dla każdego i k'_i<k_i, odpowiada składnik

$\prod_{i=1}^k \varphi(p_i^{k'_i})$

Na podstawie podanej poniżej zależności wartości funkcji Eulera od rozkładu na czynniki pierwsze łatwo widać, że składnik powyższy

$\prod_{i=1}^k \varphi(p_i^{k'_i})=\varphi(m)$

Tak więc dla każdego dzielnika m liczby n w sumie odpowiadającej rozpatrywanemu iloczynowi (równemu n) istnieje składnik φ(n). Łatwo widać, że istnieje również zależność odwrotna, tj. każdemu składnikowi sumy odpowiada dokładnie jeden dzielnik m liczby n. Tak więc rozpatrywany iloczyn jest równy n i jednocześnie jest on sumą wartości funkcji Eulera dla wszystkich swoich dzielników.

[edytuj] Zależność od rozkładu na czynniki pierwsze

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

[edytuj] Wartości funkcji φ(n) dla kilku początkowych n

1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
1	1	2	2	4	2	6	4	6	4

[edytuj] Zobacz też

Zobacz w Wikiźródłach tabelę wartości funkcji φ

Kategoria: Teoria liczb

We provide Linux to the World