« Vrati se
U ovom poglavlju očekuje se znanje predavanja kongruencije.

Skup S ćemo nazivati potpuni sustav ostataka modulo n ako elementi S svi daju različite ostatke pri dijeljenju s n, i svi ostatci će pojavljuju.
Za razmisliti: koliko elemenata ima svaki potpuni sustav ostataka modulo n, za neki fiksni n?


Skup S ćemo nazivati reducirani sustav ostataka modulo n ako svi elementi S daju različite ostatke pri dijeljenju s n i pojavljuju se svi ostaci koji su relativno prosti s n.


Primjer:
Potpuni sustav ostataka modulo 12 je \{0,1,2,3,4,5,6,7,8,9,10,11\}
Reducirani sustav ostataka modulo 12 je \{1,5,7,11\}

Primjetimo da je za prost broj p potpuni sustav ostataka \{0,1,2,...,p-1\}, a reducirani sustav ostataka \{1,2,3,..,p-1\}. Ovo vrijedi jer je p relativno prost sa svim brojevima manjima od sebe.


Inverz
Sada se vratimo na pitanje koje smo ostavili otvoreno u poglavlju kongruencije. Pitanje dijeljenja.
Zapazimo da dijeljenje s 3 nije ništa drugo nego množenje s \frac{1}{3}, to jest ako želimo podijeliti neki broj s n, zapravo ga želimo pomnožiti s nekim m takvim da nm=1.
Ovako odabrani m zovemo inverz broja n (primijetimo i da je n inverz od m).
Sada se postavlja prirodno pitanje, ako promatramo neki fiksni modul m, ima li svaki broj a svoj inverz modulo m?
Tu odmah vidimo da je odgovor ne, jer primjerice a=0 očito nema inverz.
No može se pokazati da ako vrijedi \operatorname{gcd}(a,m)=1 da a ima jedinstveni inverz modulo m. To će biti direktna posljedica zadatka 2 iz ovog područja.

Što to zapravo znači?
Ono što to za nas znači u praktičnom smislu je da, ako imamo kongruencijsku jednadžbu, i neki a relativno prost s m, tada možemo čitavu jednadžbu podijeliti s a.

Slični zadaci