Funkcja φ


Funkcja φ w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Funkcja φ (Eulera) lub tocjentfunkcja 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[a][1][2][3].

Kilka początkowych wartości funkcji φ ( n ) : {\displaystyle \varphi (n){:}}

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

Własności | edytuj kod

  • Dla każdej liczby naturalnej n > 1 : {\displaystyle n>1{:}}
φ ( n ) n 1. {\displaystyle \varphi (n)\leqslant n-1.}
  • Jeżeli p {\displaystyle p} jest pierwsza, to każda z liczb 1 , 2 , , p 1 {\displaystyle 1,2,\dots ,p-1} jest względnie pierwsza z p , {\displaystyle p,} więc
φ ( p ) = p 1 {\displaystyle \varphi (p)=p-1} [1]. φ ( m n ) = φ ( m ) φ ( n ) . {\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}
  • Jeżeli p {\displaystyle p} jest liczbą pierwszą, to
φ ( p k ) = p k 1 ( p 1 ) . {\displaystyle \varphi (p^{k})=p^{k-1}\cdot (p-1).}
  • Jeżeli p 1 , p 2 , , p k {\displaystyle p_{1},p_{2},\dots ,p_{k}} są wszystkimi czynnikami pierwszymi liczby n {\displaystyle n} liczonymi bez powtórzeń, to
φ ( n ) = n ( 1 1 p 1 ) ( 1 1 p 2 ) ( 1 1 p k ) . {\displaystyle \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 {\displaystyle n} nie ma wielokrotnych dzielników pierwszych, tj.
n = p 1 p 2 p k , {\displaystyle n=p_{1}p_{2}\dots p_{k},} gdzie liczby p i {\displaystyle p_{i}} są pierwsze i parami różne ( i = 1 , , k ) , {\displaystyle (i=1,\dots ,k),} to φ ( n ) = ( p 1 1 ) ( p 2 1 ) ( p k 1 ) . {\displaystyle \varphi (n)=(p_{1}-1)(p_{2}-1)\dots (p_{k}-1).} m | n φ ( m ) = n {\displaystyle \sum _{m|n}\varphi (m)=n} (sumowanie przebiega wszystkie dzielniki liczby n {\displaystyle n} ).
  • Jeżeli
n = i = 1 k p i k i {\displaystyle n=\prod _{i=1}^{k}p_{i}^{k_{i}}} jest rozkładem liczby n {\displaystyle n} na czynniki pierwsze, to φ ( n ) = i = 1 k φ ( p i k i ) . {\displaystyle \varphi (n)=\prod _{i=1}^{k}\varphi \left(p_{i}^{k_{i}}\right).}

Zobacz też | edytuj kod

Uwagi | edytuj kod

  1. W Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę funkcja Gaussa.

Przypisy | edytuj kod

  1. a b Funkcja φ Eulera, www.math.edu.pl [dostęp 2017-10-14] .
  2. Twierdzenie Eulera | Informatyka MIMUW, smurf.mimuw.edu.pl [dostęp 2017-10-14]  (pol.).
  3. https://cs.pwr.edu.pl/ralowski/dydaktyka/algebra_abstrakcyjna/pomoce/euler.pdf.

Bibliografia | edytuj kod

  • 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.

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "Funkcja φ" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy