Eulerov teorem

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

Eulerov teorem je jedan od najvažnijih teorema u elementarnoj teoriji brojeva, a tvrdi da je gdje je Eulerova funkcija, tj. funkcija koja svakom prirodnom broju pridružuje broj prirodnih brojeva koji su manji ili jednaki s i relativno prosti s

Isto tako, teorem je blisko povezan s tzv. Malim Fermatovim teoremom, stavljajući za neki prosti broj

Dokaz[uredi | uredi kôd]

Prije samog dokaza iskazat ćemo i dokazati sljedeću lemu.

Lema. Neka je skup svih relativno prostih brojeva s u intervalu Možemo pisati Tada su svi elementi skupa za međusobno nekongruentni modulo i daju ostatke kao elementi skupa pri dijeljenju s ali ne nužno u tom poretku.

Pretpostavimo da su neka dva elementa skupa kongruenta modulo odnosno za Tada očito no što je kontradikcija. Sada ćemo dokazati drugi dio leme. Očito su svi elementi skupa relativno prosti s Prema teoremu o dijeljenju s ostatkom možemo pisati (*). Dokazujemo da mora vrijediti čime je tvrdnja zapravo dokazana. Pretpostavimo suprotno, Tada iz (*) slijedi Onda očito a vrijedi Dakle, čime je lema dokazana.

Uočimo da ako prirodan broj daje neki od ostataka iz skupa relativno prostih brojeva s u intervalu on nužno mora biti relativno prost s Naime, pomnožimo li bilo koji broj s za koji je njegov će ostatak biti djeljiv s modulo

Koristeći ovu lemu nije teško dokazati Eulerov teorem. Označimo s Prema lemi, vrijedi bijekcija Množeći svih kongruencija dobivamo Budući da je i slijedi što je i trebalo dokazati.

Kongruentnost relativno prostih brojeva[uredi | uredi kôd]

Iskazat ćemo i dokazati jedno jednostavno, ali važno svojstvo relativno prostih brojeva.

Neka je skup svih relativno prostih brojeva s brojem u intervalu Ako je tada je gdje je

(Uočimo da tada očigledno vrijedi i gdje je skup svih relativno prostih brojeva s u )

Dokaz. Pretpostavimo suprotno, tj. da je uz No, onda očito (prema Teoremu o dijeljenju s ostatkom) postoji takav da je Kako iz posljednje jednadžbe slijedi što povlači Uočimo da su onda i brojevi svi redom relativno prosti s

Drugim riječima, broj relativno prost s daje ostatak, pri dijeljenju s koji je jedan od relativno prostih brojeva s u