Funkcja φ

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

Funkcja φ (Eulera) lub tocjent – Nazwa pochodzi od nazwiska Leonharda Eulera. Funkcja mierzy "rozbijalność" liczb pierwszych. Określa ile jest liczb całkowitych dla każdej liczby naturalnej (n), które są od niej mniejsze lub równe i nie mają z nią wspólnych dzielników. Takie liczby nazywany liczbami względnie pierwszymi. [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ści[edytuj | edytuj kod]

  • 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 | edytuj kod]

Uwagi[edytuj | edytuj kod]

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

Przypisy[edytuj | 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 | 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.