kongruencije

[Blondie]

nisu mi baš sjele kongruencije pa ako ima dobrovoljca da mi objasni

zad glasi: riješi kongruenciju 1215x==560(mod 2755)

a prof je to ovako raspisao:
2755 1215 325 240 85 70 15 10 5 0
- 2 3 1 2 1 4 1 2
-195 86 -23 17 -6 5 -1 1 0

d=5

1215x==560(mod 2755)/*5
243x==112(mod 541)/*(-195)
x==112*(-195)=-21840==200(mod 551)
=>x=200+551k
0<=k<5

po kojem principu je on raspisao ovu gore 'tablicu'

svaki broj je lijepo potpisan ispod u tablici

_________________
Dijeliti restoran ili lokal na pušačku i nepušačku sekciju je kao da podijelite bazen na dvije polovice
- u jednoj smijes pišati, u drugoj ne.

[BeeBee]

Kod takvih zadataka najvažnije je provjeriti da li je NZM = 1 . U ovom slučaju vidimo da 1215, 560, 2755 imaju zajednički barem jedan faktor a to je 5. Kad podijelimo cijelu jednadžbu da 5 dobijemo jednadžbu oblika 243x==112(mod 551) . Sada provjeravamo da li je NZM (243, 551)=1 Prvo dijelimo 551:243= 2 i ost. 65, zatim dijelimo 243:65=3 i ost. 48, dalje 65:48=1 i ost 17, 48:17=2 i ost 14, 17:14=1 i ost 3, 14:3= 4 i ost 2, 3:2=1 i ost 1 Dakle NZM ( 243,551)=1 sad možemo to raspisati u tablicu
U prvi red tablice stavljamo brojeve koje smo dobili dijeljenjem krenuvši od zadnjeg reda:
1 4 1 2 1 3 2
U 2. red uvijek upisujemo 0 i 1) 0 1 -1 5 -6 17 -23 86 -195
Brojevi u 2. redu su se dobili na sljedeći način: 0-(1*1)=-1
1-(-1*4)=5
-1-(5*1)=-6
5-(-6*2)=17
-6-(17*1)=-23
17-(-23*3)=86
-23-(86*2)=-195
Sada tražimo nekakav x iz tablice koji bi nam zadovoljio jednadžbu oblika 243x==1(mod551) Lako provjerimo da je to upravo ovaj zadnji broj u tablici, tj -195. Znači, sada onu početnu jednadžbu oblika 243x==112(mod551) množimo sa -195 i dobijemo (-195)243x==112*(-195)(mod551)
Od ranije znamo da (-195)243 možemo zapisati kao 1 pa dobivamo x== -21840(mod 551) Sada samo gledamo ostatak pri dijeljenju -21840 sa 551.
Obično se radi sa pozitivnim brojevima pa bi se ovaj -21840 trebao zapisati kao 33260 što se dobije na sljedeći način: 55100
-21840
-----------
33260
Znači, na broj 551 smo dodali nula koliko nam je potrebno.
I sad dijelimo 33260 sa 551 i gledamo ostatak koji po definiciji ne smije biti veći od 551 pa dobijemo x==200(mod551)
Međutim, zadatak nije gotov jer smo na početku cijelu jedndadžbu podijelili sa 5 pa to sada trebamo uzeti u obzir jer u svijetu 2755 ima 5 rješenja a mi smo dobili samo jedno.
x1==200(mod 2755)
x2==200+551==751(mod2755)
x3==200+551*2==1302(mod 2755)
x4==200+551*3==1853(mod 2755)
x5=200+551*4==2404(mod2755)
'x6'==2995==200(mod 2755)=x1

Added after 22 minutes:

Tablica bi trebala biti ovako ispisana:
....... 1 4 1 2 1 3 2
0 1 -1 5 -6 17 -23 86 -195

[Blondie]

[BeeBee]

NZM(a,b)= k*a+ l*b za neke k,l €Z
k*a+l*b=1 --> NZM(a,b)=1 /relativno prosti)
Znači,morali smo naći broj koji će sa 243 dati ostatak 1 po mod 551 a to je upravo br -195
Za a uzmimo 243 a za b 551, tj a=243, b=551. Po definiciji trebamo imati k*243+ l*b=1 Znači, trebamo naći s kojim brojem ćemo pomnožiti 243 a s kojim 551 da nam u zbroju daje 1. Gledamo uvijek zadnja 2 broja u tablici i njih kombiniramo s a i b. za k uzmimo -195 a za l uzmimo 86 i vidjet ćemo da je upravo rezultat 1 što povlači da je (-195)243==1(mod 551)

Euklidov algoritam se koristi kod određivanja NZM
33260/551=60 i ostatak 200 , dalje se ništa ne dijeli, tj ne radi se dalje po Euklidovom jer nas ne zanima NZM nego samo ostatak pri dijeljenju 33260 sa 551 i taj broj i napišemo

Ne znam odakle asistentu oni brojevi u tablici, trebala bih to proučiti malo ali ne vidim razlog jer je ova 'moja' tablica točna i prilično jednostavna

[Blondie]

Kužim

_________________
Dijeliti restoran ili lokal na pušačku i nepušačku sekciju je kao da podijelite bazen na dvije polovice
- u jednoj smijes pišati, u drugoj ne.

[BeeBee]

[zvonči]

Za dva skupa A i B iz P definiramo ARB akko (A\B)U(B\A)=AUB, treba ispitati svojstva relacije

[black]

hmm....mislim da ne vrijedi jednakost medu tim skupovima...
A\B ----> svi iz A koji nisu u B
B\A ----> svi iz B koji nisu u A , a jos unija medu njima

(A\B) U (B\A) = A ,,trokutic" B - simetrična razlika skupova...i to ti nije jednako A U B , vec citav skup A i B bez njihovog presjeka. [/table][/code]

_________________
zivjele P][_,avushe!

[kkarlo]