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 EuleraW Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę funkcja Gaussa.https://web.archive.org/web/20171014183751/https://cs.pwr.edu.pl/ralowski/dydaktyka/algebra_abstrakcyjna/pomoce/euler.pdf. Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.
Pierwsze 100 wartości funkcji {| class="wikitable" style="text-align: right" |+ ! + ! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 |- ! 0 | 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 |- ! 10 | 10 || 4 || 12|| 6 || 8 || 8 || 16 || 6 || 18 || 8 |- ! 20 | 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 |- ! 30 | 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 |- ! 40 | 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20 |- ! 50 | 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 |- ! 60 | 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 |- ! 70 | 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32 |- ! 80 | 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24 |- ! 90 | 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40
Obliczanie Jeśli jest rozkładem liczby na czynniki pierwsze o nietrywialnych wykładnikach, , to , co wynika z wymienionych niżej własności tej funkcji.
Własności Dla każdej liczby naturalnej
Jeżeli jest pierwsza, to każda z liczb jest względnie pierwsza z więc . 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 obejmuje wszystkie dzielniki liczby ).
Zobacz też
chińskie twierdzenie o resztach funkcja Carmichaela funkcja π małe twierdzenie Fermata RSA twierdzenie Eulera
Uwagi
Przypisy
Bibliografia
Linki zewnętrzne
Kategoria:Funkcje arytmetyczne Kategoria:Kryptologia Kategoria:Leonhard Euler Kategoria:Teoria podzielności