„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
Új oldal, tartalma: „A matematika területén a legnagyobb közös osztó ('''en: greatest common divisor - gcd''') gyakran és sokat használt algebrai...”
 
Nincs szerkesztési összefoglaló
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&nbsp;=&nbsp;5·3·2<sup>3</sup> és 560&nbsp;=&nbsp;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>&nbsp;=&nbsp;40, így lnko(120, 560)&nbsp;=&nbsp;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 uotlsó nem nulla maradék maga az lnko lesz.
 
Példa: <br> lnko(84, 18)&nbsp;=&nbsp;?
*Ekkor elosztjuk 84-et 18-cal
**a hányados 4, a maradék 12
*elosztjuk 18-at 12-vel
**a hányados 1, a maradék 6
*elosztjuk 12-t 6-tal
**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)&nbsp;=&nbsp;6.