xxx dyskretna: Witam, mam pytanie dotyczące algorytmu Euklidesa i NWD.. mianowicie mam przedstawić NWD jako kombinację liniową liczb a,b na wiki mam taki przykład: NWD 174,18 = 6 174 / 18 = 9 r 12; 18 / 12 = 1 r 6; 12 / 6 = 2 r 0; 6= 18−12=1*18−(1*174+(−9)*18)= −1*174+10*18... <−−skąd wzięły się te wszystkie liczby? może podam taki przykład NWD 43,12 ... z obliczeń wychodzi, że NWD to 1, jednak nie potrafię tego rozpisać jak w przykładzie powyżej pomoże ktoś?

dyskretna: .

ICSP: 43 = 12 * 3 +7 12 = 7 * 1 + 5 7 = 5 *1 + 2 5 = 2 * 2 + 1 1 = 5 − 2*2 = 5 − 2 * (7 −5) = −2*7 + 3 * 5 = −2 * 7 + 3 * (12 − 7) = = −5 * 7 + 3 * 12 = −5 * (43 − 12 * 3) + 3 * 12 = = −5 * 43 + 15 * 12 + 3 * 12 = − 5 * 43 + 12 * 12 = 18*12 − 5*43

dyskretna: do trzeciego znaku = rozumiem, ale skąd nagle: −2*7 + 3 * 5

ICSP: zwyczajne wymnożenie : 5 − 2(7 − 5) = 5 − 2*7 + 2 *5 = 3 *5 − 2 *7

dyskretna: czyli mówiąc ogólnie, każdą resztę musimy rozłożyć według schematu D = A − B * C aż dojdziemy do początku, w tym wypadku 43?

ICSP: