Školjka

%V0 U ovom poglavlju očekuje se znanje predavanja kongruencije. Skup $S$ ćemo nazivati [b]potpuni sustav ostataka modulo n[/b] ako elementi $S$ svi daju različite ostatke pri dijeljenju s $n$, i svi ostatci će pojavljuju. [b]Za razmisliti:[/b] koliko elemenata ima svaki potpuni sustav ostataka modulo $n$, za neki fiksni $n$? Skup $S$ ćemo nazivati [b]reducirani sustav ostataka modulo n[/b] ako svi elementi $S$ daju različite ostatke pri dijeljenju s $n$ i pojavljuju se svi ostaci koji su relativno prosti s $n$. [b]Primjer:[/b] 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. [b]Inverz[/b] 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 [b]inverz[/b] 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. [b]Što to zapravo znači?[/b] 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$.