Funkcja φ

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

1 2 3 4 5 6 7 8 9 10 11 12
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ściEdytuj

  • Dla każdej liczby naturalnej  
 
  • Jeżeli   jest pierwsza, to każda z liczb   jest względnie pierwsza z   więc
 [1].
 
  • Jeżeli   jest liczbą pierwszą, to
 
  • Jeżeli   są wszystkimi czynnikami pierwszymi liczby   liczonymi bez powtórzeń, to
 
  • Jeżeli   nie ma wielokrotnych dzielników pierwszych, tj.
 
gdzie liczby   są pierwsze i parami różne   to
 
 
(sumowanie przebiega wszystkie dzielniki liczby  ).
  • Jeżeli
 
jest rozkładem liczby   na czynniki pierwsze, to
 

Zobacz teżEdytuj

UwagiEdytuj

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

PrzypisyEdytuj

  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.

BibliografiaEdytuj

  • 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ętrzneEdytuj