Hog kell megnézni két szám legnagyobb közös osztóját?

Meg kell találni, meghatározni a két szám prímtényezőit, azaz fel kell bontani őket prímszámok szorzataként (pl. 6= 3x2).

Ennél egy sokkal hatásosabb módszer, az euklideszi algoritmus, ami a hétköznapi maradékos osztás algoritmusát használja fel, azzal a megfigyeléssel kombinálva, hogy ha elosztjuk a-t b-vel, majd az osztási maradékkal b-t, és így tovább, akkor az utolsó nem nulla maradék maga az lnko lesz.

Példa:

lnko(84, 18) = ?

* Ekkor elosztjuk 84-et 18-cal

o a hányados 4, a maradék 12

* elosztjuk 18-at 12-vel

o a hányados 1, a maradék 6

* elosztjuk 12-t 6-tal

o a hányados 2, a maradék 0,

azaz itt megállt az algoritmus, nincs következő lépés, mivel 0-val nem lehet osztani. Tehát az utolsó nem nulla maradék a 6,

azaz lnko(84, 18) = 6.

Ha a és b közül egyik se nulla, akkor felhasználva a legkisebb közös többszörösüket, ami jelölésben az lkkt(a, b):

írd fel őket prímtényezős felbontásban

90|2

45|5

9|3

3|3

1

Ugyanígy felírod a másik számot is és amelyik szám mindkét felbontás jobb oldalán közös, azt bekarikázgatod...

420|2

210|2

105|5

21|7

3|3

1

az iskolai változat, hogy felírod mindkettő prímfelbontását, és minden prímtényezőt akkora kitevővel veszel, mint a kisebbik, amekkorával a két felbontásban szerepel.

Példa: 12 = 2^2 × 3 és 90 = 2 × 3^2 × 5 legnagyobb közös osztójában:

- a 2 első hatványon lesz, mert a 12 felbontásában 2. hatványon van, a 90ében 1.-n, ebből az 1 a kisebb

- a 3 első hatványon lesz, mert 12 felbontásában 1. hatványon van, a 90ében 2.on, ebből az 1 a kisebb.

- az 5 vagy nagyobb prímek nem szerepelnek benne, mert a 12 felbontásában nem szerepelnek.

Tehát az LNKO=2×3=6.

Nagyobb számoknál viszont macera a prímfelbontást megcsinálni, ezért ott alkalmasabb az euklideszi algoritmus [link]

Ez már nem gimis anyag.