Eulerova funkcija

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

Eulerova funkcija je funkcija koja svakom prirodnom broju pridružuje broj relativno prostih s koji su manji od (ili jednaki kada je ). Označavamo ju s .[1]

Primjerice, itd.

Uočimo da je gdje je bilo koji prosti broj.

Skup relativno prostih brojeva s u označavat ćemo sa .

Osnovna svojstva[uredi | uredi kôd]

▪Eulerova funkcija je multiplikativna, odnosno vrijedi [2],

▪ Vrijedi

▪ Vrijedi (Gaussova lema o Eulerovoj funkciji).

Struktura skupa [uredi | uredi kôd]

Uzmimo Navodimo skup relativno prostih brojeva s 20 manjih od 20:

Uočimo da je

Pretpostavljamo da struktura skupa ima sljedeću invarijantu:


Sada ćemo tvrdnju ovog naslućivanja i dokazati. Neka je takav da Želimo pokazati da je tada nužno Pretpostavimo da je To bi značilo da Da bi izraz bio djeljiv s mora biti To povlači što je i trebalo dokazati.


Zato je za kardinalnost skupova paran broj, a znamo da je

Izvori[uredi | uredi kôd]

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. Geometrijski dokaz se može naći na poveznici http://e.math.hr/Vol31/Bokun