28
28
Kategória: |
Definíció
- Bizonyítás
|
Évfolyam: |
9. |
Kulcsszó: |
Euklideszi algoritmus |
Lektorálás: |
Nem lektorált |
Az euklideszi algoritmus
Definíció
Olyan véges sokszor elvégzett maradékos osztás, amely megadja két természetes szám legnagyobb közös osztóját.
Az eljárás folyamán az egyik számot elosztjuk maradékosan a másik számmal, majd a másodikat a maradékkal, az első maradékot az második maradékkal, és így tovább. Az utolsó nem nulla maradék a legnagyobb közös osztó.