Funkcja φ

Funkcja φ (Eulera) lub tocjentfunkcja przypisująca każdej liczbie naturalnej liczbę liczb względnie pierwszych z nią i nie większych od niej[1]. Nazwa pochodzi od nazwiska Leonharda Eulera[a][2][3][4][5] .

Kilka początkowych wartości funkcji

+ 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


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ściEdytuj

  • Dla każdej liczby naturalnej  
 
  • Jeżeli   jest pierwsza, to każda z liczb   jest względnie pierwsza z   więc [6]
 [2].
 
  • Jeżeli   jest liczbą pierwszą, to [6]
 
  • Jeżeli   są wszystkimi czynnikami pierwszymi liczby   liczonymi bez powtórzeń, to [7]
 
  • Jeżeli   nie ma wielokrotnych dzielników pierwszych, tj [7].
 
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

UwagiEdytuj

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

PrzypisyEdytuj

  1. Funkcje Eulera, [w:] Encyklopedia PWN [online] [dostęp 2021-07-21].
  2. a b Funkcja φ Eulera, www.math.edu.pl [dostęp 2017-10-14].
  3. Twierdzenie Eulera | Informatyka MIMUW, smurf.mimuw.edu.pl [dostęp 2017-10-14] (pol.).
  4. https://web.archive.org/web/20171014183751/https://cs.pwr.edu.pl/ralowski/dydaktyka/algebra_abstrakcyjna/pomoce/euler.pdf.
  5. Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 158-171. ISBN 83-01-12124-6.
  6. a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 159. ISBN 83-01-12124-6.
  7. a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 160. ISBN 83-01-12124-6.
  8. Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 161. ISBN 83-01-12124-6.

BibliografiaEdytuj

Linki zewnętrzneEdytuj