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 .

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 VE | uredi]

▪Eulerova funkcija je multiplikativna, odnosno vrijedi

▪ Vrijedi

▪ Vrijedi (Gaussova lema o Eulerovoj funkciji).

Struktura skupa [uredi VE | 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