Legnagyobb közös osztó

A természetes számokat, az osztóik száma alapján, három halmazba sorolhatjuk:
A = {0; 1}
B = {2; 3; 5; 7; 11; 13; 17; 19; 23; 29; ...}
C = {4; 6; 8; 9; 10; 12; 14; 15; 16; 18; 20; ...}

B halmazba azok a természetes számok tartoznak, amelyeknek pontosan 2 osztójuk van, 1 és önmaguk. Ezeket a számokat prímszámoknak nevezzük.

C halmazba azok a természetes számok tartoznak, melyeknek legalább 3 osztójuk van. Ezeket a számokat összetett számoknak nevezzük.

A nullának végtelen sok osztója van, önmagán kívül minden más természetes számmal osztható. Az 1-nek pedig egy darab osztója van, önmaga. Így ők ketten nem tartoznak sem a prímszámok, sem az összetett számok közé.

Az összetett számok felbonthatók prímszámok szorzatára. Például:
12 = 2*2*3
54 = 2*3*3*3
Ezt a szorzat alakot nevezzük prímtényezős szorzat alaknak - a szorzás minden tényezője prímszám.

Segítségével könnyen előállíthatjuk a szám összes osztóját:
12 osztói: 1; 2; 3; 2*2; 2*3; 2*2*3
54 osztói: 1, 2; 3; 2*3; 3*3; 2*3*3; 3*3*3, 2*3*3*3

A két számnak vannak közös osztóik: 1, 2, 3; 6. Kérdés: hogyan lehet a legnagyobb közös osztót leolvasni a számok prímtényezős szorzat alakjáról?

A legnagyobb közös osztó prímtényezős szorzat alakját tudjuk leolvasni a két szám szorzat alakjáról: a 12 is és az 54 is egy darab 2-es  és egy darab 3-as közös prímtényezővel rendelkezik. Így az ő legnagyobb közös osztójuk a 2*3.

Más példa:
288 = 2⁵*3²
3024 = 2⁴*3³*7
Közös prímtényezők: négy darab 2-es tényező és kettő darab 3-as tényező. Így legnagyobb közös osztójuk:
2⁴*3² = 144.

A legnagyobb közös osztó jelölése a gömbölyű zárójel:
(12; 54) = 6
(288; 3024) = 144

Összefoglalva: két (vagy több) szám legnagyobb közös osztójának prímtényezős szorzat alakját úgy olvassuk le, hogy
1.) a számokat prímszámok szorzatára bontjuk, majd
2.) a számok közös prímtényezőit, az előforduló kisebbik hatványon összeszorozzuk.

Ha a számok legnagyobb közös osztója 1, akkor relatív prímeknek nevezzük őket. Például a 14 és a 15 összetett számok, ám nincs közös prímtényezőjük:
14 = 2*7
15 = 3*5.
Így legnagyobb közös osztójuk az 1.
(14; 15) = 1.

A legnagyobb közös osztó meghatározásának a törtek egyszerűsítésénél van szerepe. Ha meghatározzuk a számláló és a nevező legnagyobb közös osztóját, akkor egy lépésben tudjuk egyszerűsíteni a törtet. Például:
Egyszerűsítsük az 5100/6120 törtet!

1.) Prímszámok szorzatára bontjuk a számlálót és a nevezőt:
5100 = 2²*3*5²*17
6120 = 2³*3²*5*17

2.) Leolvassuk a legnagyobb közös osztót:
(5100; 6120) = 2²*3*5*17 = 1020

3.) 1020-szal egyszerűsítjük a törtet:
5100/6120 = 5/6.