Točno
29. listopada 2013. 16:28 (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.
U zadacima ovog tipa, uvjek je korisno pokusati pronaci
takav da je suma modulo
invarijantna. To se radi na sljedeci nacin:
![x+y \equiv 13x-6y+7y-2x \pmod n](/media/m/7/5/4/754652fd603e17628533697bfa3b629c.png)
![x+y \equiv 11x + y \pmod n](/media/m/b/a/c/bacbbe8a46a97658883f9b1524bfe911.png)
![10x \equiv 0 \pmod n](/media/m/7/a/0/7a03fdd83b81a2a3f1114624263c1087.png)
Kako ovo mora vrjediti za svaki
, znamo da
mora biti djeljitelj od broja
.
![x+y \equiv 3y-6x+2x+3y \pmod n](/media/m/1/3/6/13659efe8f150619fd543f90f65cb6ca.png)
![x+y \equiv 6y-4x \pmod n](/media/m/f/1/2/f12ff2b8b2ce8660fb7002cdd0b41abe.png)
![5x - 5y \equiv 0 \pmod n](/media/m/f/4/2/f42333e794bf33e03eb67be1ac79ee5c.png)
![5(x-y) \equiv 0 \pmod n](/media/m/d/b/0/db0fddcdb65c7afbb4c6b71362f21e87.png)
Kako ovo mora vrjediti za sve
i
, znamo da
mora biti djeljitelj broja
.
Dakle, da bi prva promjena bila invarijantna modulo
,
, da bi druga promjena bila invarijantna modulo
,
. Ocito jedini brojevi koji ovo zadovoljavaju su
i
. Kako je gledati ostatke pri djeljenju s
malo besmisleno, gledamo ostatke pri djleljenju s
.
Znamo da se suma mod
ne mijenja. Na pocetku je suma jednaka
, a na kraju
. Ta dva broja ne daju isti ostatak pri djeljenju s
, pa je nemoguce doci iz uredenog para
u
.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![x+y \equiv 13x-6y+7y-2x \pmod n](/media/m/7/5/4/754652fd603e17628533697bfa3b629c.png)
![x+y \equiv 11x + y \pmod n](/media/m/b/a/c/bacbbe8a46a97658883f9b1524bfe911.png)
![10x \equiv 0 \pmod n](/media/m/7/a/0/7a03fdd83b81a2a3f1114624263c1087.png)
Kako ovo mora vrjediti za svaki
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![10](/media/m/5/b/e/5beb46430dbe2d22c0f8289c36a92c84.png)
![x+y \equiv 3y-6x+2x+3y \pmod n](/media/m/1/3/6/13659efe8f150619fd543f90f65cb6ca.png)
![x+y \equiv 6y-4x \pmod n](/media/m/f/1/2/f12ff2b8b2ce8660fb7002cdd0b41abe.png)
![5x - 5y \equiv 0 \pmod n](/media/m/f/4/2/f42333e794bf33e03eb67be1ac79ee5c.png)
![5(x-y) \equiv 0 \pmod n](/media/m/d/b/0/db0fddcdb65c7afbb4c6b71362f21e87.png)
Kako ovo mora vrjediti za sve
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
![y](/media/m/c/c/0/cc082a07a517ebbe9b72fd580832a939.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
Dakle, da bi prva promjena bila invarijantna modulo
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n|10](/media/m/f/a/2/fa21f16cc00184dcf2b56d249481d80a.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n|5](/media/m/e/8/c/e8c949d4da377e4592481211f29fc77c.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
Znamo da se suma mod
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
![4](/media/m/d/a/6/da6087359ae47e86dcb2e49565050046.png)
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
![(2,3)](/media/m/2/5/9/259123c1b81bc226bb391aa499cff3aa.png)
![(3,1)](/media/m/a/0/a/a0ae37f68f632741b954bb02bb2251a5.png)