Funkcja φ
Z Wikipedii, wolnej encyklopedii
Funkcja φ (Eulera) lub tocjent – funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych nie większych od niej samej.
Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.
Funkcja φ Eulera dana jest dla każdej liczby naturalnej n wzorem
gdzie
są wszystkimi czynnikami pierwszymi liczby n liczonymi bez powtórzeń.
[edytuj] Własności
- Jeżeli p jest pierwsza, to każda z liczb
jest względnie pierwsza z p, więc:
- φ(p) = p − 1
- Jeżeli liczby całkowite m,n są względnie pierwsze, to
- φ(mn) = φ(m)φ(n)
- Jeżeli n = pk, to
- φ(n) = pk − pk − 1
- Jeżeli n nie ma wielokrotnych dzielników pierwszych, tj.
- gdzie liczby pi są pierwsze i parami różne (
), to
- Dla dowolnej liczby całkowitej n zachodzi:
| ∑ | φ(m) = n, |
| m | n |
- (sumowanie przebiega wszystkie dzielniki liczby n).
- Jeżeli
jest rozkładem liczby n na czynniki pierwsze to
[edytuj] Przykład
-
n 1 2 3 4 5 6 7 8 9 10 11 12 φ(n) 1 1 2 2 4 2 6 4 6 4 10 4

jest względnie pierwsza z 
), to


