Točno
20. listopada 2013. 19:37 (10 godine, 9 mjeseci)
Sakrij rješenje
Sakrij rješenje
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
Pretpostavimo da neka dva kvadrata daju isti ostatak modulo
.
![x^2 \equiv y^2 \pmod p](/media/m/a/3/6/a36bb51bb6aa39dba620b8b3d018cd57.png)
![(x-y)(x+y)\equiv 0 \pmod p](/media/m/3/8/b/38b6cb6215ce94fbac9e4b42bd2793c2.png)
Da bi umozak dva broja bio djeljiv s prostim brojem
, barem jedan od njih mora biti djeljiv s
.
Dakle ili vrijedi
![x-y \equiv 0 \pmod p](/media/m/8/1/d/81d2320b5eefd38bfed5e7e066c4930f.png)
ili vrijedi
![x+y \equiv 0 \pmod p](/media/m/6/2/e/62e8937b1c0cccd7b7c9168405174357.png)
Dakle za svaki
postoji tocno jedan broj
koji daje razlicit ostatak pri djeljenju s
, ali ciji kvadrat daje isti ostatak. Naravno, moramo pipaziti na jednu iznimku, broj koji je djeljiv s
ima svojstvo da je
(to jest
). Dakle, brojevi djeljivi s
nam daju jedan ostatak (
), a ostalih ima ukupno
, i svaki ima svog para s kojim daje isti ostatak. Dakle ukupno imamo
mogucih kvadratnih ostataka.
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![x^2 \equiv y^2 \pmod p](/media/m/a/3/6/a36bb51bb6aa39dba620b8b3d018cd57.png)
![(x-y)(x+y)\equiv 0 \pmod p](/media/m/3/8/b/38b6cb6215ce94fbac9e4b42bd2793c2.png)
Da bi umozak dva broja bio djeljiv s prostim brojem
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
Dakle ili vrijedi
![x-y \equiv 0 \pmod p](/media/m/8/1/d/81d2320b5eefd38bfed5e7e066c4930f.png)
![x \equiv y \pmod p](/media/m/7/f/1/7f1d82f9b9f780a5491899012bd6f2d7.png)
ili vrijedi
![x+y \equiv 0 \pmod p](/media/m/6/2/e/62e8937b1c0cccd7b7c9168405174357.png)
![x \equiv -y \pmod p](/media/m/1/6/f/16f5d1ce24b33c550a93a3dc522cc789.png)
Dakle za svaki
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
![y](/media/m/c/c/0/cc082a07a517ebbe9b72fd580832a939.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![x \equiv -x \pmod p](/media/m/5/c/a/5cab1206d58f0ccf518734241275fa13.png)
![0 \equiv 0 \pmod p](/media/m/4/b/a/4ba947a110bc283fb243607216f406ce.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
![p-1](/media/m/3/8/9/389a51fc4e0296668e79f23ead7e404f.png)
![1+\frac {p-1}{2}=\frac{p+1}{2}](/media/m/e/d/7/ed7e765b478bee9500cab5cbd828e1b9.png)