Funkcja φ

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Funkcja φ (Eulera) lub tocjentfunkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych mniejszych 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 wzorem

gdzie są wszystkimi czynnikami pierwszymi liczby liczonymi bez powtórzeń.

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 , 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

Przykład[edytuj]

1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 2 4 2 6 4 6 4 10 4

Zobacz też[edytuj]