Funkcja φ
Przejdź do nawigacji
Przejdź do wyszukiwania
|
Funkcja φ (Eulera) lub tocjent – funkcja 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ś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 liczby całkowite są 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 | edytuj kod]
- chińskie twierdzenie o resztach
- funkcja Carmichaela
- funkcja π
- małe twierdzenie Fermata
- RSA
- twierdzenie Eulera
Uwagi[edytuj | edytuj kod]
- ↑ W Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę funkcja Gaussa.
Przypisy[edytuj | edytuj kod]
- ↑ a b Funkcja φ Eulera, www.math.edu.pl [dostęp 2017-10-14] .
- ↑ Twierdzenie Eulera | Informatyka MIMUW, smurf.mimuw.edu.pl [dostęp 2017-10-14] (pol.).
- ↑ 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.
Linki zewnętrzne[edytuj | edytuj kod]
- Witold Bednarek: Funkcja Eulera (pol.). „Delta”, październik 2019. [dostęp 2019-10-02].