Question

Dla podanych liczb oblicz: (32,72), (33,72), (125,15)
1 sposobem z odejmowaniem (nwd)
2. sposobem z reszta z dzielenia (nwd)

Answer 1

Sposób z odejmowaniem (algorytm Euklidesa):
NWD(32,72) = NWD(32, 72-32) = NWD(32,40)=NWD(32, 40-32) =
=NWD(32,8)=NWD(24,8)=NWD(16,8)=NWD(8,8) = 8

NWD(33,72)=NWD(33,39)=NWD(33,6)=NWD(27,6)=...=NWD(9,6)=NWD(6,3)= =NWD(3,3) = 3

NWD(125,15)=NWD(110,15)=NWD(95,15)=NWD(80,15)=...=NWD(20,15)= 
=NWD(5,15)=NWD(5,10)=NWD(5,5)=5

Sposób z resztą z dzielenia:
mamy:
72 : 32 = 2 reszty 8
32 : 8 = 4 reszty 0
Zatem NWD(72,32) =8

72 : 33 = 2 reszty 6
33 : 6 =5 reszty 3
6 : 3 = 2 reszty 0
Zatem NWD(72,33) = 3

125 : 15= 8 reszty 5
15 : 5 = 3 reszty 0
Zatem NWD(125,15)=5

jest to rozszerzony algorytm Euklidesa