Prije samog dokaza iskazat ćemo i dokazati sljedeću lemu.
Lema.
Neka je skup svih relativno prostih brojeva s u intervalu Možemo pisati
Za skup kažemo da je reducirani sustav ostataka modulo n.
Svi elementi skupa
za su 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.[2]
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.
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 igdje jeskup svih relativno prostih brojeva su)
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
Brojevi su relativno prosti za svaki prosti broj . Naime, pretpostavimo da . No, tada , kontradikcija. (Ovo vrijedi za bilo koja dva uzastopna prirodna broja.)
↑Andrej Dujella. 2008. Uvod u teoriju brojeva(PDF). Prirodoslovno-matematički fakultet. Zagreb. Inačica izvorne stranice arhivirana 7. travnja 2021. Pristupljeno 8. travnja 2021.CS1 održavanje: bot: nepoznat status originalnog URL-a (link)
↑Posjetiti stranicu mathlesstraveled.com na ovu temu