Hogyan tudjuk kiszámítani 72 és 48 legnagyobb közös osztóját?

Egyik lehetőség: felírod a két szám osztóját, és megnézed, hogy melyik a legnagyobb, ami mindkettőt osztja.

Másik megoldás: a prímtényezős felbontásukból kiolvasod.

egy kis "handholding": a prímtényezős felbontásnál, a legkisebb prímszámtól felfelé haladva kell keresni az osztókat

72 / 2 = 36

36 / 2 = 18

18 / 2 = 9

9 / 3 = 3

3 / 3 = 1

Tehát a 72 prímtényezős felbontása: 2*2*2*3*3

42 / 2 = 21

21 / 3 = 7

7 / 7 = 1

Tehát a 42 prímtényezős felbontása: 2*3*7

A legnagyobb osztó, amit ebből "kirakhatsz" a 2*3 lesz tehát a válasz 6.

2#

Annyival rontottad el, hogy véletlen a 42-őt bontottad fel a 48 helyett.

a 48 prímtényezős felbontása:

48 / 2 = 24

24 / 2 = 12

12 / 2 = 6

6 / 2 = 3

3 / 3 = 1

48 = 2 * 2 * 2 * 2 * 3

Tehát a legnagyobb közös osztó 2 * 2 * 2 * 3 = 24

A prímtényezőre való bontás nem mindíg működik. Ha egy szám nagy prímeket is tartalmaz, akkor azok megtalálása nagyon számolásigényes.

Létezik egy másik módszer is:

- írjuk egymás mellé a két számot.

- a nagyobból vonjuk le a kisebbet. Vagy a többszörösét, ha az még mindig kisebb

- az eredményt írjuk a nagyobb alá.

- folytassuk, amig mindkét oszlopban ugyanaz a szám lesz. Az a legnagyobb közös osztó.

72 48

24 48

24 24

Ennyi.

A módszer azon alapul, hogy ha a>b, akkor a-b és b közös osztója ugyanannyi, mint a és b közös osztója.

A 6-os által vázolt megoldást polgári nevén euklideszi algoritmusnak hívják. Ezt csak azért mondom, hogy ez bizonyítottan működik mindig. Annyit azonban megjegyeznék, hogy a kivonást 0-ig szokták csinálni, vagyis az utolsó lépcsőfok a fenti esetben

24 0, ekkor a megmaradt nemnulla szám lesz az eredeti számok legnagyobb közös osztója, ami a 24. Ez persze csak egy árnyalatnyi különbség, a 24 24 esetén is ugyanez olvasható ki.

Kipróbáltam és úgy tűnik, nem hülyeség ez az euklideszi algoritmus :) köszi a tippet!

1562, 132

110, 132

110, 22

0, 22

1562 = 2*11*71

110 = 2*5*11

Eszedbe jutott már, hogy mi a legnagyobb közös osztója, mondjuk a 55432182-nak és a 321546-nak?:) Look no further:

55432182, 321546

126270, 321546

126270, 69006

57264, 69006

57264, 11742

10296, 11742

10296, 1446

174, 1446

174, 54

12, 54

12, 6

Két ekkora szám és 6 a legnagyobb közös osztójuk. Szépen nézünk ki.