Mielőtt a legnagyobb közös osztó (GCD) fogalmának meghatározásához kezdenénk, meg kell értenünk, mi a közös osztó általában.
Ismert, hogy egy egész számnak több osztója is lehet. Arra vagyunk kíváncsiak, hogy egyidejűleg több egész számmal hozzájuk férhessenek. Több egész szám közös osztójának azt a számot tekintjük, amely a megadott sorozat minden egyes számának osztójaként működhet.
Például a 8-as és 12-es számoknak a következő közös osztói vannak: 1 és 4. Ez könnyen ellenőrizhető matematikai kifejezések felírásával: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
Meg kell jegyezni, hogy kezdetben minden számnak legalább két közös osztója van: bármely szám osztható önmagával maradék nélkül, és osztható 1-gyel is.
A legnagyobb közös osztó meghatározása
Két természetes szám legnagyobb közös osztója (GCD) a legnagyobb a természetes számok közül, amellyel két számunkat oszthatjuk. Ha két természetes szám legnagyobb közös osztójának értéke 1, akkor ezeket a számokat koprímnek nevezzük.
Két a és b szám esetén a legnagyobb közös osztó az a szám, amellyel a és b maradék nélkül osztható. Ez a kifejezés a következőképpen írható: gcd (a, b) = c.
A GCD írásának másik módja: (a, b) = c. A legtöbb esetben azonban az első opciót használjuk.
Így például a 4-es és 16-os szám legnagyobb közös osztója 4. Írjuk fel: gcd (4, 16) = 4.
Írjuk le, hogyan jutottunk ehhez az eredményhez:
- Kiírtuk a 4-es szám összes osztóját. A következőt kaptuk: 4, 2, 1.
- Ezután megfestettük a 16 összes osztóját. A következőt kaptuk: 16, 8, 4, 2, 1.
- Olyan osztókat választottunk, amelyek a 4-re és a 16-ra is közösek. A következőt kaptuk: 4, 2, 1.
- A kapott közös osztók közül a legnagyobbat választottuk ki. Ez a 4.
- Megkapjuk a választ: 4-es és 16-os szám esetén a GCD 4.
Hasonlóan megtalálhatja a GCD-t három vagy több egész számra. Ebben az esetben ez lesz a legnagyobb egész szám, amellyel eloszthatja a javasolt sorozat összes számát.
Így például a 6, 12, 18, 42 egész számok legnagyobb osztója a 6 lesz, azaz gcd (6, 12, 18, 42) = 6. A választ egy algoritmus segítségével kaptuk meg. a fent leírtakhoz hasonlóan - egy sorozatból származó számok esetén az összes osztót egymás után kiírták, majd a legnagyobbat választották ki közülük.
GCD tulajdonságai
A legnagyobb közös osztónak számos olyan tulajdonsága van, amelyek a nullánál nagyobb osztókkal rendelkező pozitív egészek GCD-jére vonatkoznak.
1. tulajdonság
A számok helyének megváltoztatása miatt a GCD végső értéke nem változik. Ezt az állítást így írhatod:
- gcd(a, b) = gcd(b, a).
2. tulajdonság
Ha a osztható b-vel, akkor a és b közös osztóinak halmaza megegyezik b osztóinak halmazával. Így írva:
- gcd(a, b) = b.
A bizonyított legnagyobb osztó tulajdonság felhasználható két olyan szám gcd-jének meghatározására, amikor az egyik osztható a másikkal. Ebben az esetben a GCD egyenlő ezen számok egyikével, amellyel egy másik szám osztható.
Például:
- gcd(12, 4) = 4.
Hasonló:
- gcd(10, 1) = 1.
3. tulajdonság
Ha a = bq + c, ahol a, b, c és q egész számok, akkor a és b közös osztóinak halmaza megegyezik b és c közös osztóival.
Érvényessé válik a gcd (a, b) = gcd (b, c) egyenlőség.
4. tulajdonság
A gcd(ma, mb) = m ⋅ gcd(a, b) kifejezés igaz, feltéve, hogy m bármely természetes szám.
5. tulajdonság
Tegyük fel, hogy p az a és b bármely közös osztója.
Ezután:
- gcd(a / p, b / p) = gcd(a, b) / p.
Ha p = gcd(a, b), akkor a következőt kapjuk:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
Így az a / gcd (a, b) és b / gcd (a, b) számok másodlagos számok.
6. tulajdonság
Bármely két számnak van legalább egy közös osztója – ez az 1.
A GCD koncepció elméleti alapjainak ismerete, valamint definíciójának gyakorlati ismerete szükséges a közönséges törtekkel való munkavégzéshez. Ezenkívül a GCD szorosan kapcsolódik egy másik matematikai egységhez - a legkevésbé közös osztóhoz. Mindkét definíciót általában egy szabványos iskolai tanterv részeként tanulmányozzák.
