Számok legnagyobb közös osztójának meghatározása az euklideszi algoritmus segítségével.
Számok legnagyobb közös osztójának alábbi algoritmusát Eukleidész határozta meg.
Ez az algoritmus az alábbi oszthatósággal kapcsolatos észrevételen alapszik: Ha a=b⋅q+r, akkor (a,b)=(b,r), ahol a, b, q, r egész számok. Mivel a maradékos osztás maradéka mindig kisebb az osztónál, ezért két szám legnagyobb közös osztójának meghatározása mindig visszavezethető két kisebb szám legnagyobb közös osztójának megkeresésére.
Például: Határozzuk meg 252 és 2205 legnagyobb közös osztóját.
2205=252⋅8+189, és (2205,252)=(252,189)
252=189⋅1+63, és (252,189)=(189,63)
189=63⋅3+0, és (189,63)=63
Vagyis (252,2205)=63.
Comments are closed, but trackbacks and pingbacks are open.