Točno
26. srpnja 2014. 01:08 (9 godine, 11 mjeseci)
Sakrij rješenje
Dokaži ili opovrgni tvrdnju. Za prost broj
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
i
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
relativno prost s
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
vrijedi da je skup
![\{a,2a,3a,...,(p-1)a\}](/media/m/4/7/2/4728433beadc49221a514c676eaff170.png)
reducirani sustav ostataka modulo
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
.
%V0
Dokaži ili opovrgni tvrdnju. Za prost broj $p$ i $a$ relativno prost s $p$ vrijedi da je skup $\{a,2a,3a,...,(p-1)a\}$ reducirani sustav ostataka modulo $p$.
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Ponovno je dovoljno pokazati da svaka dva elementa daju razlicit ostatak modulo
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
.
Pretpostavimo da je
![ka \equiv la \pmod p](/media/m/9/d/4/9d4e014184190142b1516f150fc9532a.png)
Kako su
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
i
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
relativno prosti, mozemo cijelu jednadzbu pomnoziti s inverzom od
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
.
Tada dobivamo
![k \equiv l \pmod p](/media/m/f/4/b/f4bd86f2bc358de56ab8987ba43d7bd1.png)
.
Kako su i
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
i
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
nuzno manji od
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
, vrijedi
![k=l](/media/m/3/1/5/3150ba9cc8b9dccb7899e5dc3e6726f5.png)
.
Dakle, svi elementi daju razlicite ostatke modulo
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
.
%V0
Ponovno je dovoljno pokazati da svaka dva elementa daju razlicit ostatak modulo $p$.
Pretpostavimo da je $ka \equiv la \pmod p$
Kako su $a$ i $p$ relativno prosti, mozemo cijelu jednadzbu pomnoziti s inverzom od $a$.
Tada dobivamo $k \equiv l \pmod p$.
Kako su i $k$ i $l$ nuzno manji od $p$, vrijedi $k=l$.
Dakle, svi elementi daju razlicite ostatke modulo $p$.
28. srpnja 2014. 18:59 | ikicic | Točno |