Aby wyznaczyc NWD(a,b),mozna posłuzyc sie algorytmem EUKLIDESA.jest on pomocny szczegolnie w przypadku duzych liczb a i b .Niech a=2261 i b=2695
2695=1*2261 + 434
2261=5*434+91
434=4*91+70
91=1*70+21
70=3*21+7
21=3*7+0
NWD(a,b) jest ostatnia róznica od zera,reszta.Zatem NWD(2261,2695)=7.korzystajaca z algorytmu Euklidesa,wyznacz NWD(1920,405).

1

Odpowiedzi

2010-01-29T23:13:33+01:00
NWD(1920,405) = 15

1920 = 4 * 405 + 300
405 = 1 * 300 + 105
300 = 2 * 105 + 90
105 = 1 * 90 + 15
90 = 6 * 15 + 0