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

Dodatna svojstva djeljivosti elemenata skupa [uredi | uredi kôd]

Isto tako, treba uočiti da vrijedi sljedeće.

Ako je paran[uredi | uredi kôd]

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[uredi | uredi kôd]

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