Question

Aby wyznaczyć najwiekszy wspólny dzielnik liczb 1224 i 216 możemy posłużyć się algorytmem Eoklidesa w następujacy sposób
1224 = 5 x 216 + 144
216 = 1 x144 + 72
144=2x72 +0
NWD(1224,216)=72
Postępując podobnie wyznacz:
a) NWD(1408,3200)
b) NWD(7371,1365)
c) NWD(1615,2618)
d) NWD(22991,19667)

Answer 1

A) NWD(1408,3200) = 128
3200=2 * 1408 + 384
1408= 3* 384 + 256
384=1* 256 + 128
256= 2 * 128 + 0

b) NWD(7371,1365)= 273
7371 = 5 * 1365 + 546
1365= 2 * 546 + 273
546 = 2*273 + 0

c) NWD(1615,2618) = 17
2618= 1* 1615 + 1003
1615= 1* 1003 + 612
1003 =1* 612 +391
612= 1* 391 + 221
391= 1*221+ 170
221= 1*170 +51
180=3*51 + 17
51= 3*17+0

d) NWD(22991,19667) =277
22991=1*19667+3324
19667=5*3324+3047
3324=1*3047+277
3047=11*277 +0

Answer 2

A) NWD(1408,3200)
3200=2×1408+384
1408=3×384+256
384=1×256+128
256=2×128+0
NWD(1408,3200)=128

b) NWD(7371,1365)
7371=5×1365+546
1365=2×546+273
546=2×273+0
NWD(7371,1365)=273

c) NWD(1615,2618)
2618=1×1615+1003
1615=1×1003+612
1003=1×612+391
612=1×391+221
391=1×221+170
221=1×170+51
170=3×51+17
51=3×17+0
NWD(1615,2618)=17

d) NWD(22991,19667)
22991=1×19667+3324
19667=5×3324+3047
3324=1×3047+277
3047=11×277+0
NWD(22991,19667)=277

Answer 3

A) NWD(1408,3200)
3200 = 2 * 1408 + 384
1408 = 3 * 384 + 256
384 = 1 * 256 + 128
256 = 2 * 128 + 0
NWD(1408,3200) = 128

b) NWD(7371,1365)
7371 = 5 * 1365 + 546
1365 = 2 * 546 + 273
546 = 2 * 273 + 0
NWD(7371,1365) = 273

c) NWD(1615,2618)
2618 = 1 * 1615 + 1003
1615 = 1 * 1003 + 612
1003 = 1 * 612 + 391
612 = 1 * 391 + 221
391 = 1 * 221 + 170
221 = 1 * 170 + 51
170 = 3 * 51 + 17
51 = 3 * 17 + 0
NWD(1615, 2618) = 17

d) NWD(22991,19667)
22991 = 1 * 19667 + 3324
19667 = 5 * 3324 + 3047
3324 = 1 * 3047 + 277
3047 = 11 * 277 + 0
NWD(22991,19667) = 277