Funkcja φ

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Funkcje matematyczne

dziedzina

Funkcje elementarne

Funkcje algebraiczne:

wymierna - niewymierna
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ść

Funkcja φ Eulera (inaczej tocjent) – funkcja określona dla dodatnich liczb całkowitych, której wartością dla danej liczby n jest ilość mniejszych od niej liczb względnie pierwszych z liczbą n, przy czym 1 jest traktowana jako względnie pierwsza z każdą liczbą.

Funkcja φ odgrywa dużą rolę w badaniach nad pierwszością liczb. Ma również istotne zastosowania w kryptografii, szczególnie w dowodach o trudności łamania szyfrów.

Spis treści

1 Definicja formalna
2 Własności
3 Wartości funkcji φ(n) dla kilku początkowych n
4 Zobacz również

[edytuj] Definicja formalna

Dla Liczby całkowitej n funkcja Eulera określona jest następująco:

$\varphi(n)= card \{k \in \mathbb{Z}: 0 < k < n \and \operatorname{NWD}(n, k)=1\}$

gdzie card oznacza moc zbioru, a NWD(n,k) największy wspólny dzielnik liczb n i k.

[edytuj] Własności

[edytuj] Wzór ogólny

Można pokazać, że dla każdej dodatniej liczby całkowitej n zachodzi:

$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$

gdzie p przebiega wszystkie liczby pierwsze dzielące n.

[edytuj] Wartość dla liczb pierwszych

Jeżeli p jest liczbą pierwszą to każda z liczb 1,2,...p-1 należy do zbioru liczb mniejszych od p względnie pierwszych 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

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

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

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

$n=\prod_{i=1}^kp_i$

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

$\varphi(n)=\prod_{i=1}^k(p_i-1)$

[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 powyzszy

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