Eulerova funkcija

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 svojstvaUredi

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

 

▪ Vrijedi  

▪ Vrijedi   (Gaussova lema o Eulerovoj funkciji).

Struktura skupa Uredi

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

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

Ako je   paranUredi

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   neparanUredi

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  .

IzvoriUredi

  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