Rje~savanje kongruencij~a ~ raspisano
> Haj,
Hi,
> Ajd mi pliz pomozi, zapeo sam - treba rijesiti linearnu kongruenciju
> 240x=72(mod 603)... To bi znacilo da 603 dijeli 240x-72, ali sto dalje s
> tim? Nisam uspio naci pretjerano literature koja bi mi pomogla, (cak ni
> Hardy-Wright, Advanced number theory).
>
> Unaprijed hvala ;-))
Bilo bi lijepo da si napisao sto si, no pretpostavljam da si student na
mathu i da se pripremas za kolokvij iz Elementarne...
[ned_ryerson:]Am I right?[/] :-))
Dakle, ovak: pod tom pretpostavkom, logicno bi bilo za ocekivati da si
prosao kroz sve vjezbe, no tada bi i ovo znao trivijalno rijesiti, pa cu
zato pretpostaviti da imas osnovne pojmove, ali ti i dalje neke stvari
nisu jasne.
Ok, prvo teorijski pristup. Da, 603 dijeli 240x-72 ,
odnosno, (240x-72)/603 je cijeli broj. Taj razlomak se moze skratiti
(s 3), pa se dobije da je (80x-24)/201 cijeli broj. Osim toga, u
brojniku se moze izluciti 8 , pa dobivamo da je 8*(10x-3)/201 cijeli
broj, odnosno da kad se izracuna 10x-3 , pa se to pomnozi s 8 , dobije
se nesto djeljivo s 201 . No sad je jasno da to mnozenje s osmicom dodaje
samo dvojke (njih 3, that is) u rastavu na proste faktore, dakle ne
pomaze djeljivosti broja 3x-10 s 201=3*67 . Dakle, 10x-3 se mora
osloniti na svoje snage only, odnosno mora vec sam biti djeljiv s 201 .
Ovo zadnje mogu zapisati i preciznije. 8 je relativno prost s 201 .
Dakle, NZM(8,201)=1 , odnosno postoje cijeli k i l takvi da 8k+201l=1 .
Ako to sad pomnozim s 10x-3 (kojeg cu zbog lijenosti oznaciti s y :),
dobijem 8ky+201ky=y . 8y je djeljivo s 201 (pise gore), pa i 8ky .
201ky e trivijalno djeljivo s 201 , pa dobijemo da i njihova suma (koja
je - vidi cuda - jednaka y ) mora biti djeljiva s 201 .
Super. Dakle, dosli smo do toga da je (10x-3)/201 cijeli broj.
Sto dalje? Pa, oznacimo taj cijeli broj s m . Dakle, 10x-3=201m ,
odnosno 10x-201m=3 . Dakle, 3 je prikazan kao linearna kombinacija od
10 i 201 (s koeficijentima x i -m ). No znamo da su 10 i 201 relativno
prosti, pa se sigurno 1 moze izraziti kao njihova linearna kombinacija.
Naravno, ako se moze 1 , moze i 3 - samo pomnozimo stvar s 3 ,
koeficijenti ce ostati cijeli brojevi. Dakle, treba odrediti
koeficijente. To se moze pomocu Euklidovog algoritma, koji za brojeve
10 i 201 izgleda ovako:
NZM(201,10)=NZM(201mod10,10)=NZM(1,10)=NZM(10,1)=NZM(10mod1,1)=NZM(0,1)=1 .
Dakle, 201=10*20+1 , i iz toga odmah 201*1+10*(-20)=1 (da je bilo vise
dijeljenja s ostacima, unatrag bismo uvrstavali dok ne bismo dobili 1
kao linearnu kombinaciju gornja dva broja). So, koeficijent uz 10 je -20 .
Pomnozivsi s 3 , dobijemo 201*3+10*(-60)=3 , odnosno 10*(-60) je
kongruentno 3 modulo 201 . Dakle, -60 je jedno rjesenje.
Lako se vidi da je to i jedino rjesenje, modulo 201 . Naime,
pretpostavimo 10x==3 & 10x'==3 (mod201) . Dakle, 10x==10x'(mod201) ,
odnosno 10(x-x') je djeljivo s 201 . Opet jednako kao gore s osmicom,
buduci da su 10 i 201 relativno prosti, 10 ne moze pomoci (x-x')u da
bude djeljiv s 201 , pa on mora to uciniti sam. Dakle, x==x'(mod201) ,
odnosno postoji samo jedno rjesenje modulo 201 . To je dakle -60 ,
odnosno (sto je isto modulo 201 ), -60+201=141 . Dakle, u svijetu
mod201 , rjesenje je x==141 .
Naravno, sljedece je pitanje, kako vratiti jednadbu u svijet u kojem je
zadana (remember, to je bio svijet mod603 ). Taj svijet je ocito 3put
veci, odnosno jednom broju u mod201-svijetu odgovaraju 3 u
mod603-svijetu. Samo je pitanje koja to tri broja odgovaraju 141ici ...
Jedan od njih je 141 itself. Naime, ako je broj kongruentan 141 modulo
603 , onda je ocito kongruentan 141 i modulo 201 (tranzitivnost
djeljivosti, 201|603|bla-141 ). Druga dva dobijemo ovako:
Trazimo neki broj u svijetu mod603 . Svi takvi brojevi uvijek se mogu
svesti na brojeve od 0 do 602 (prica o klasama, itd.). Od _tih_ brojeva,
koji su kongruentni 141 modulo 201 ? Ako je z takav, znaci da 201 dijeli
z-141 , odnosno z=141+201r . Iz uvjeta z@[0..602] lako dobijemo
r@{0,1,2} . Dakle, imamo tri rjesenja modulo 603 :
x1==141(mod603)
x2==141+201==342(mod603)
x3==141+201*2==141+402==543(mod603) .
Rjesenja su 141 , 342 i 543 u svijetu mod603 .
Eto. Sad ajmo na "mehanicko" rjesavanje.
Trebamo rijesiti ax==b(mod n) . a=240 , b=72 , n=603 .
Racunamo d=NZM(a,n) , Euklidovim algoritmom.
603:240=2 i ost. 123
240:123=1 i ost. 117
123:117=1 i ost. 6
117: 6=19 i ost. (3) <- d=3 . d|b (3|72 ok), pa kongruencija
------------------ ima d (odnosno 3 ) rjesenja.
6 : 3 =2 i ost. 0
240x==72(mod603) /::3
80x==24(mod201)
Tablica za inverz od 80 modulo 201 :
2 19 1 1 2
0 1 -19 20 -39 (98) <- k
80x==24(mod201) /*98
x==2352==141(mod201) <- x0=141
x1=141 , x2=141+(2-1)*201=342 , x3=141+(3-1)*201=543 . Over.
Etoga. Ako ti ne treba brzo mehanicko rjesavanje, slobodno ga mozes
zanemariti. Iz gornjeg teorijskog razmatranja sve bi trebalo biti jasno.
Ako nije, pitaj.
Bye & da se nisi usudio ne rijesiti 4. zadatak... ;-),
--
*(*-***-*(*-*(*
*(*-**(-**(-(*( Without love, intelligence is dangerous.
(*(-***-*(*-(*( Without intelligence, love is not enough.