Točno
29. listopada 2013. 16:29 (10 godine, 8 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.
Pokusajmo ponovo pronaci
takav da je suma modulo
invarijantna.
![x+y \equiv 2x+3y+y-x \pmod n](/media/m/0/6/6/0662ad7e4babc9a48764b29c35d3de2e.png)
![x+y \equiv x+4y \pmod n](/media/m/2/8/d/28d6fb61628bc077d7d905d09475a370.png)
![3y \equiv 0 \pmod n](/media/m/0/f/e/0fea0fb1e6676345129b94d14df5520c.png)
Kako ovo mora vrjediti za sve
, znamo da
. Pa promotrimo dali je i druga promjena invarijantna modulo
.
![x+y \equiv x-5y+6y-9x \pmod 3](/media/m/4/f/7/4f7fcf0f8f3991d86c91759f694f04c7.png)
![x+y \equiv x - 2y \pmod 3](/media/m/f/a/6/fa6d3b5fc83fdf493598231db40e9730.png)
![x+y \equiv x+y \pmod 3](/media/m/e/0/f/e0fe7eb1083f3165d9a0bd4be6429b57.png)
Kako svi moguci koraci ostavljaju sumu invarijantnu mod
, potrebno je jos samo provjeriti pocetni i zavrsni par koji smo dobili. Na pocetku je suma djeljiva s
, a na kraju daje ostatak
pri djeljenju s
. Dakle, nemoguce je.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![x+y \equiv 2x+3y+y-x \pmod n](/media/m/0/6/6/0662ad7e4babc9a48764b29c35d3de2e.png)
![x+y \equiv x+4y \pmod n](/media/m/2/8/d/28d6fb61628bc077d7d905d09475a370.png)
![3y \equiv 0 \pmod n](/media/m/0/f/e/0fea0fb1e6676345129b94d14df5520c.png)
Kako ovo mora vrjediti za sve
![y](/media/m/c/c/0/cc082a07a517ebbe9b72fd580832a939.png)
![n|3](/media/m/7/9/6/796efcee23dba529d1feabea9275d299.png)
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
![x+y \equiv x-5y+6y-9x \pmod 3](/media/m/4/f/7/4f7fcf0f8f3991d86c91759f694f04c7.png)
![x+y \equiv x - 2y \pmod 3](/media/m/f/a/6/fa6d3b5fc83fdf493598231db40e9730.png)
![x+y \equiv x+y \pmod 3](/media/m/e/0/f/e0fe7eb1083f3165d9a0bd4be6429b57.png)
Kako svi moguci koraci ostavljaju sumu invarijantnu mod
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)