1 - Sustavi Ostataka
Kvaliteta:
Avg: 5,0Težina:
Avg: 0,0 U ovom poglavlju očekuje se znanje predavanja kongruencije.
Skup
ćemo nazivati potpuni sustav ostataka modulo n ako elementi
svi daju različite ostatke pri dijeljenju s
, i svi ostatci će pojavljuju.
Za razmisliti: koliko elemenata ima svaki potpuni sustav ostataka modulo
, za neki fiksni
?
Skup
ćemo nazivati reducirani sustav ostataka modulo n ako svi elementi
daju različite ostatke pri dijeljenju s
i pojavljuju se svi ostaci koji su relativno prosti s
.
Primjer:
Potpuni sustav ostataka modulo
je ![\{0,1,2,3,4,5,6,7,8,9,10,11\}](/media/m/1/1/3/11362bd983ff4b5056e729b53a92ac46.png)
Reducirani sustav ostataka modulo
je ![\{1,5,7,11\}](/media/m/4/2/d/42d4fb25d6a91cec2832c7fe95548ea9.png)
Primjetimo da je za prost broj
potpuni sustav ostataka
, a reducirani sustav ostataka
. Ovo vrijedi jer je
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
nije ništa drugo nego množenje s
, to jest ako želimo podijeliti neki broj s
, zapravo ga želimo pomnožiti s nekim
takvim da
.
Ovako odabrani
zovemo inverz broja
(primijetimo i da je
inverz od
).
Sada se postavlja prirodno pitanje, ako promatramo neki fiksni modul
, ima li svaki broj
svoj inverz modulo
?
Tu odmah vidimo da je odgovor ne, jer primjerice
očito nema inverz.
No može se pokazati da ako vrijedi
da
ima jedinstveni inverz modulo
. To će biti direktna posljedica zadatka
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
relativno prost s
, tada možemo čitavu jednadžbu podijeliti s
.
Skup
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Za razmisliti: koliko elemenata ima svaki potpuni sustav ostataka modulo
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Skup
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Primjer:
Potpuni sustav ostataka modulo
![12](/media/m/e/f/6/ef6c8e9eecc5ee3d49031ee4f0e20f98.png)
![\{0,1,2,3,4,5,6,7,8,9,10,11\}](/media/m/1/1/3/11362bd983ff4b5056e729b53a92ac46.png)
Reducirani sustav ostataka modulo
![12](/media/m/e/f/6/ef6c8e9eecc5ee3d49031ee4f0e20f98.png)
![\{1,5,7,11\}](/media/m/4/2/d/42d4fb25d6a91cec2832c7fe95548ea9.png)
Primjetimo da je za prost broj
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![\{0,1,2,...,p-1\}](/media/m/5/1/e/51e09eb42b0084d1ee9dcd575c1be1cd.png)
![\{1,2,3,..,p-1\}](/media/m/6/a/f/6afa52db324928e43313d0f20a28c4c4.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
Inverz
Sada se vratimo na pitanje koje smo ostavili otvoreno u poglavlju kongruencije. Pitanje dijeljenja.
Zapazimo da dijeljenje s
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
![\frac{1}{3}](/media/m/a/3/d/a3d9243f208d314445ef031b3af0766b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![nm=1](/media/m/0/1/8/0187cd181a8c3addf428e607684dd448.png)
Ovako odabrani
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
Sada se postavlja prirodno pitanje, ako promatramo neki fiksni modul
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
Tu odmah vidimo da je odgovor ne, jer primjerice
![a=0](/media/m/1/6/f/16ff59abcd4e49b52a5c57287e4536ee.png)
No može se pokazati da ako vrijedi
![\operatorname{gcd}(a,m)=1](/media/m/4/0/a/40a11cb573db0c1f388864c5166b9d30.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
Š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](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)