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

  • Jeżeli jest pierwsza, to każda z liczb jest względnie pierwsza z , więc:
  • Jeżeli liczby całkowite względnie pierwsze, to
  • 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
  • Dla dowolnej liczby całkowitej zachodzi:
(sumowanie przebiega wszystkie dzielniki liczby ).
  • Jeżeli

jest rozkładem liczby na czynniki pierwsze, to

Zobacz też[edytuj]

Uwagi

  1. W Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę 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.