„Legnagyobb közös osztó” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Syp (vitalap | szerkesztései) iw |
|||
15. sor:
A legnagyobb közös osztó megkereséséhez meg kell határozni az adott két szám [[prím]]tényezőit, azaz a számokat fel kell bontani prímszámok szorzatára. Egy másik példa alapján az lnko(120, 560) kiszámolásánál felírandó, hogy 120 = 5·3·2<sup>3</sup> és 560 = 7·5·2<sup>4</sup>. Ekkor venni kell a közös prímtényezőket, (mint ahogy a nevében is van), méghozzá az összeset. Itt most 5·2<sup>3</sup> = 40, így lnko(120, 560) = 40. Ez a számolási módszer csak a relatíve kis egészeknél működik, általánosságban a legnagyobb közös osztó megkeresése nagy számoknál ilyen módszerrel sok időt vesz igénybe.
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
Példa: <br> lnko(84, 18) = ?
28. sor:
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):
:<math>\operatorname{lnko}(a,b)=\frac{a\cdot b}{\operatorname{lkkt}(a,b)}.</math>
==Tulajdonságai==
| |||