Funkcja φ

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[1][2][3][a].

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ści[edytuj]

  • Dla :
  • 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]

Przypisy[edytuj]

  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

Uwagi

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

Bibliografia[edytuj]

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