DSC01310 (2)

28/12 =2; reszta=4; 28/11 =2; reszta=6; 28/10 =2; reszta=8 28/9 =3; reszta=1 28/8 =3; reszta=4 28/7 =4; reszta=0 28/6 =4; reszta=4 28/5 =5; reszta=3 28/4 =7; reszta=0

12712 m; reszta=0 szukamy NWD(28;12)=?

12/11 =1; reszta-1

12/10=1; reszta=2

12/9 =1; reszta=3

12/8 =1; reszta=4

12/7 =1; reszta=5

12/6 =2; reszta=0

12/5 =2; reszta=2

12/4 =3; reszta=0 rozw NWD(28;12)=4

1 .b. Algorytm Euklidesa. Polega on na powtarzaniu ciągu operacji;

Podzieleniu; liczby większej przez mniejszą np.:

28/12 =2; reszta=4

A następnie podzieleniu dzielnika przez uzyskaną resztę. Itd..

1214 =3; r^zta=0

Operację dzielenia wykonujemy do uzyskania reszty=0.

Wynik mamy po 2 operacjach dzielenia. Rozw.: NWD(28; 12)=4