algorytm koziol: Rozszerzony algorytm euklidesa dla 441x + 168y = NWD(441,168) x y a b q r 1 0 − 441 − 168 0 1 441 168 2 105 1 −2 168 105 1 63 −1 3 105 63 1 42 2 −5 63 42 1 21 −3 8 42 21 2 0 Nie pamiętam jak się wyliczało x i y, czy ktoś wie jak to się wylicza?

Mila: Co chcesz z tym zrobić?

koziol: wyliczyć x i y, x = −3, y =8 tylko nie pamiętam jak te x,y po kolei się wyliczało, które są w tabeli, bo reszte umiem

Mila: 441=2*168+105 168=1*105+63 105=1*63+42 63=1*42+21 42=2*21+0 =========== NWD(441,168)=21 Mamy równanie: 441x + 168y =21 /:21 21x+8y=1 Algorytm 21=2*8+5 8=1*5+3 5=1*3+2 3=1*2+1 2=2*1+0 ============odwracamy obliczenia 1=3−1*2=1*3−1*(5−1*3)=1*3−1*5+1*3= =2*3−1*5=2*(8−1*5)−1*5=2*8−2*5−1*5= =2*8−3*5=2*8−3*(21−2*8)=2*8−3*21+6*8= =−3*21+8*8

koziol: zrobiłaś to chyba zwykłym euklidesem, a w tabeli jest rozszerzony euklides

koziol: i nie pamiętam jak te x,y po kolei w tabeli się wyliczało

koziol: ktoś wie?

Mila: Pod kreską masz R.

koziol: tak, ale ja to rozszerzony algorytmem euklidesa chcę rozwiązać, nie zwykłym.

Mila: https://matematykaszkolna.pl/szukaj/szukaj.py