oblicz
Iza: 221x+754y=NWD(221,754)
jak się za to zabrać?
mógłby ktos napisać algorytm postępowania, jak rozwiązywać takie zadania?
20 kwi 19:03
20 kwi 19:11
20 kwi 19:48
jc:
754 = 3*221+91
221=2*91+39
91=2*39+13
39=3*13+0
13=91−2*39
=91−2*(221−2*91)=5*91−2*221
=5*(754−3*221)−2*221=5*754 − 17*221
x=−17+58k
y=5−17k
20 kwi 19:55
jc: Początek, to zwykły algorytm Euklidesa: a=kb+r.
Potem idziesz od końca do początku.
Rozwiązań jest nieskończenie wiele: do x możesz dodać kA/NWD, a od y odjąć kB/NWD.
A, B to liczby od których zaczynamy.
Algorytm komputerowy piszemy nieco inaczej: każda kolejna reszta
jest postaci xA + yB.
20 kwi 19:59