Internetowa Encyklopedia „Wiki”

Funkcja Gaussa


Funkcja φ (Eulera) lub tocjent – funkcja przypisująca każdej liczbie naturalnej liczbę (ilość) liczb które są z nią względnie pierwsze i nie większe od niej[1] (liczymy również 1). Nazwa pochodzi od nazwiska Leonharda Eulera[a][2][3][4][5.1]. 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

+ 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[6].

Własności

  • Dla każdej liczby naturalnej
  • Jeżeli jest pierwsza, to każda z liczb jest względnie pierwsza z więc[5.2]
[2].
  • Jeżeli jest liczbą pierwszą, to[5.2]
  • Jeżeli są wszystkimi czynnikami pierwszymi liczby liczonymi bez powtórzeń, to[5.3]
  • Jeżeli nie ma wielokrotnych dzielników pierwszych, tj.[5.3]
gdzie liczby są pierwsze i parami różne to
(sumowanie obejmuje wszystkie dzielniki liczby ).

Zobacz też

Uwagi

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

Przypisy

  1. ↑ Funkcje Eulera, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-21].
  2. ↑ a b Funkcja φ Eulera [online], www.math.edu.pl [dostęp 2017-10-14] [zarchiwizowane z adresu 2014-12-04].
  3. ↑ Twierdzenie Eulera | Informatyka MIMUW [online], 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. ISBN 83-01-12124-6.
    1. ↑ S. 158-171.
    2. ↑ a b S. 159.
    3. ↑ a b S. 160.
    4. ↑ S. 161.
  6. ↑ Adam Neugebauer, Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. I, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 146-147, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-07-07].

Bibliografia