[ pasvord @ 15.08.2009. 17:46 ] @
pozdrav,
muci me zadatak iz kongruencija koji bi trebao da se uradi kineskom metodom.. zadatak glasi :

x = 1 (mod 5);
x = 2 (mod 6)
x = 3 (mod 7)

*= (kongruentno)

dobio sam M koji iznosi 210, zatim M1=42, M2=35 i M3 = 30.. ovo i nije neka pamet
zatim sam krenuo da rijesavam jednacine :) (valjda se tako zovu)

Mi * yi = 1 (mod mi);
---
42 * y1 = 1 (mod 5);
2 * y1 = 1(mod 5)

eh sada, da li se ovdje ovako tacno radi : 2 mnozim sa nekim brojem u opsegu od 0 do 4 (zbog 5) i rezultat treba da bude za 1 veci od 5 ? ako je tako, rijesenje y1 bi bilo:

y1 = 3 (mod 5);

jer je 2 * 3 = 6, 6-5 = 1, sto zadovoljava 2*y1 = 1(mod5)
---
eh, idemo dalje

35 * y2 = 1 (mod 6)
5 * y2 = 1 (mod 6)
eh, ovdje dolazi taj problem (naravno ako je iznad sve tacno)
produkt brojeva 5 i broja u opsegu od 0 do 5 nikada nije veci od broja 6 za 1 :S
tu sam stao i dalje ne ide :(
---
i trecu sam cini mi se dobro uradio
30 * y3 = 1 (mod 7);
2 * y3 = 1 (mod 7);
y3 = 4 (mod 7) (zasto cetiri ? zato sto je 2 * 4 = 8, sto je za 1 vece od modula 7)

inace zadatak je lagan (sto se opcenito kongruencija tice, odoka su lagane), ali nemam puno literature iz koje bih mogao shvatiti...

[Ovu poruku je menjao pasvord dana 15.08.2009. u 22:22 GMT+1]
[ zzzz @ 15.08.2009. 22:44 ] @
x = 1 (mod 5);
x = 2 (mod 6)
x = 3 (mod 7)
ili valjda ovako:ostatak pri djeljenju x sa 5 je 1 (xMod5=1)
----------------------
Napravi od ovog jednu jednačinu sa dvije cjelobrojne nepoznanice.
x=5a+1
x=6b+2
x=7c+3
---------------------
Množimo tako da nam uz a,b i c bude isti faktor
42x=210a+42
35x=210b+70
30x=210c+90
---------------------
Saberemo ove tri gornje jednačine.

107x=210(a+b+c)+202;
Neka je (a+b+c)=y pa imamo takvu jednačinu

107x-210y=202

koju lako rješavamo poznatom redukcijom (Euklid).


[Ovu poruku je menjao zzzz dana 16.08.2009. u 11:24 GMT+1]
[ zzzz @ 15.08.2009. 23:15 ] @
Code:
----------------------------------------
     107x(1)-210x(2)=202
----------------------------------------
     
  i        a(i)             I(i)        x(i)
- - - - - - - - - - - - - - - - - - - - - - - - - -
  1       -210              -1          53 *202
  2        107              -1          27 *202
  3       -103             -25          26 *202
  4          4              -1           1 *202        
  5         -3                           1 *202
  6          1                           0  
- -  - - - - - - - - - - - - - - - - - - - - - - - - -
x(1)=53*202=10706, a najmanji prirodan broj koji zadovoljava uslove zadatka je

x=x(1)Mod 210 =206






206=5*41+1
206=6*34+2
206=7*29+3

[Ovu poruku je menjao zzzz dana 16.08.2009. u 11:31 GMT+1]
[ zzzz @ 16.08.2009. 11:11 ] @
Citat:
pasvord: pozdrav,
muci me zadatak iz kongruencija koji bi trebao da se uradi kineskom metodom.. zadatak glasi :


---
eh, idemo dalje

35 * y2 = 1 (mod 6)
5 * y2 = 1 (mod 6)
eh, ovdje dolazi taj problem (naravno ako je iznad sve tacno)
produkt brojeva 5 i broja u opsegu od 0 do 5 nikada nije veci od broja 6 za 1 :S
tu sam stao i dalje ne ide :(
---

(Previdjeh da mora ići po kineski)
Pa ovdje je greška, jer je za y2=5 imaš 25=1(mod 6)

i onda imaš brojeve 42*3 , 35*5 i 30*4 koji samo sa jednim od
djelioca imaju ostatak 1.Množimo ih sa danim ostacima pa je
x=126*1+175*2+120*3=836.A najmanji prirodan broj se dobije
ako od 836 oduzmemo tri puta po 210, a to je 206.