Největší společný dělitel (GCF) je největší číslo, kterým lze rozdělit dvě nebo více čísel. To bez zanechání zbytků.
To znamená, že největší společný dělitel nebo GCF je nejvyšší hodnota, kterou lze rozdělit sadu čísel, což vede k celému číslu.
Dělitel lze formálně definovat jako číslo, které je obsaženo v jiném přesně n-krát.
Je třeba poznamenat, že čísla, na nichž se vypočítává GCF, musí být nenulová.
Abychom to lépe vysvětlili, podívejme se na příklad. Předpokládejme, že máme 35 a 15. Sledujeme tedy, jaké jsou dělitele každého z nich:
- Dělitelé 35 → 35,7,5,1
- Dělitelé 15 → 15,5,3,1
Největší společný faktor 35 a 15 je tedy 5.
Za zmínku stojí, že pokud jsou společné dělitele dvou čísel pouze 1 a -1, říká se jim „vzájemně se připravit“.
Metody výpočtu největšího společného dělitele
Můžeme rozlišit následující tři metody pro výpočet největšího společného dělitele:
- Prime factor rozklad: Čísla se rozkládají na prvočísla. Potom pro výpočet GCF vezmeme běžná čísla zvednutá na nejnižší výkon. Předpokládejme například, že máme 216 a 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Největší společný dělitel mezi oběma čísly by tedy byl: (2 2) * 3 = 12
Nyní předpokládejme, že máme tři prvky: 315, 441 a 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Poté, co je rozdělíte a vezmete každého dělitele s nejnižší silou, bude výsledek:
GCF = (3 2) * 7 = 63
- Euklidův algoritmus: Při dělení na Pojď dovnitř b, získá se kvocient C a r. Největší společný dělitel na Y b je stejné jako b Y r. To vzhledem k následujícímu: a = bc + r. Abychom to lépe pochopili, použijeme tuto metodu na příklad zobrazený dříve s 216 a 156.
216/156 = 1 se zbytkem 60
nyní rozdělíme 156/60 = 2 na zbytek 36
Znovu rozdělíme 60/36 = 1 se zbytkem 24
Ještě jednou rozdělíme 36/24 = 1 na zbytek 12
A nakonec rozdělíme 24/12 = 2 na zbytek 0
Proto je největším společným dělitelem 12. Jak vidíme, musíme dělit, dokud zbytek nebude 0 a posledním dělitelem bude GCF.
- Na základě nejméně společného násobku: Čísla se vynásobí a výsledek se vydělí jejich nejméně běžným násobkem (LCM).
Musíme si pamatovat, že nejméně běžný násobek (LCM) je nejmenší číslo, které splňuje podmínku, že je násobkem všech prvků množiny čísel.
To znamená, že se vracíme ke stejnému příkladu, můžeme se rozložit následovně:
216 = (3 3) * (2 3) a 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Nejméně běžný násobek by byl: (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Takže: GCD = 216 * 156 / 2,808 = 12
Stojí za zmínku, že tato metoda funguje pouze pro dvě čísla.