Eulerova funkcija je funkcija koja svakom prirodnom broju pridružuje broj relativno prostih brojeva s koji su manji od (ili jednaki kada je ). Označavamo ju s .Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
Primjerice, vrijedi itd.
Uočimo da je gdje je bilo koji prosti broj.
Skup relativno prostih brojeva s u označavat ćemo sa .
Ovu je funkciju 1763. uveo znameniti švicarski matematičar Leonhard Euler.
Osnovna svojstva ▪Eulerova funkcija je multiplikativna, odnosno vrijedi te ,Geometrijski dokaz se može naći na poveznici Eulerova funkcija
▪
▪ Vrijedi
▪ Vrijedi (Gaussova lema o Eulerovoj funkciji).
Struktura skupa
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
Dodatna svojstva djeljivosti elemenata skupa Isto tako, treba uočiti da vrijedi sljedeće.
Ako je paran Ako je dakle , tada je razlika bilo koja dva člana skupa paran broj. Ovo slijedi iz činjenice da je očito svaki element skupa neparan. Primjerice te .
Ako je neparan Ako je pak , primijetimo da razlike elemenata skupa ne moraju nužno sve biti parne, ali s druge strane su članovi skupa (pa je njihova razlika najmanji neparni broj, broj ), tj. mora biti Naime, iz slijedi . No, kako slijedi jer je . (1)
Svojstvo je ekvivalento s pa, zbog (1), ono vrijedi. Primjer ovakvog skupa bio bi te primjerice .
Izvori
Kategorija:Algebra