Legnagyobb közös osztó

Definíció:

Két vagy több egész szám legnagyobb közös osztója az a pozitív egész szám, amely az adott számok mindegyikének osztója, és az adott számok minden közös osztójának többszöröse.

Mivel oszthatóság szempontjából minden szám és ellentettje is ugyanúgy viselkedik, ezért az egyértelműség végett kikötjük, hogy a legnagyobb közös osztó mindig pozitív.

Jelöléssel: (a,b,c)=d, ha d a legnagyobb olyan egész, hogy a=d⋅m, b=d⋅l, és c=d⋅k, ahol a, b, c, d, l, m, k egész számok. 

Például: (630, 252, 2205)=63. mert 630=6310, 252=63⋅4, 2205=63⋅35.

Ha két vagy több számnak nincs közös prímtényezője, azaz a legnagyobb közös osztójuk az 1, akkor az ilyen számokat egymáshoz képest relatív prímeknek mondjuk. Például (16,25)=1.

A legnagyobb közös osztó előállítása:

Az adott számok közös osztói csak olyan prímtényezőket tartalmaznak, amelyek mindegyik szám prímtényezős felbontásában szerepel. Ebből következik, hogy a közös osztók keresését a számok prímtényezős felbontása alapján keressük: a=630=2⋅3⋅3⋅5⋅7=2⋅32⋅5⋅7, b=252=2⋅2⋅3⋅3⋅7=2232⋅7, c=2205=3⋅3⋅5⋅7⋅7=2*32*5*72. Közös prímtényezők: a 3 (mindegyik számban kétszer), és a 7.

Így a legnagyobb közös osztó: (a;b;c)=(630;252;2205)=d=3⋅3⋅7=32⋅7=63.

Röviden: keressük meg a közös prímszámok mindegyikénél a legkisebb kitevőjűt, és e legkisebb kitevőjű prímszámhatványokat szorozzuk össze.

Alkalmazása:

Például törtek egyszerűsítésénél.
Egyszerűsítsük az alábbi törtet:  ​\( \frac{252}{2205} \)​ !
Mivel a példában szereplő számok legnagyobb közös osztója a 63, ezért: ​\( \frac{252}{2205} \)​=\( \frac{63⋅4}{63⋅35} \)​=  ​\( \frac{4}{35} \)​.

1. Ha két szám legnagyobb közös osztóját akarjuk meghatározni, és az egyik tényező tartalmaz olyan tényezőt, amelyik a másik számhoz relatív prím, akkor ez a tényező elhagyható.
Például: (630, 2205)=(2*315,2205)=(315,2205)=315.

2. Két szám legnagyobb közös osztójának és legkisebb közös többszörösének szorzata megegyezik a két szám szorzatával. Azaz (a,b)⋅[a,b]=a⋅b. Például: (252,630)=126, [252,630]=1260, és 126⋅1260=158760=252630.

Ha érdekel a számok legnagyobb közös osztójának meghatározásra szolgáló, Eukleidész által megfogalmazott algoritmus, akkor katt ide.

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.