Největší společný dělitel (NSD) - jak ho vypočítat, příklady

Největší společný dělitel (zkráceně NSD) dvou nebo více přirozených čísel je největší číslo, kterým jsou všechna beze zbytku dělitelná. Například největší společný dělitel čísel 12 a 18 je 6: šestka dělí obě čísla a žádné větší číslo to nedokáže.

`\text{dělitelé 12:}\quad 1,\ 2,\ 3,\ 4,\ \mathbf{6},\ 12`
`\text{dělitelé 18:}\quad 1,\ 2,\ 3,\ \mathbf{6},\ 9,\ 18`
`D(12,\ 18)=6`

Ve škole se zapisuje D(12, 18) = 6, často také NSD(12, 18) = 6. Spočítat ho jde několika způsoby: vypsáním dělitelů (pro malá čísla), z prvočíselného rozkladu (nejčastější ve škole) a Euklidovým algoritmem (nejrychlejší pro velká čísla). Nejčastěji ho budete potřebovat při krácení zlomků. Pokud chcete jen výsledek s postupem, spočítá ho kalkulačka Největší společný dělitel.

Co je společný dělitel

Dělitel čísla je číslo, kterým ho jde vydělit beze zbytku. Dělitelé dvanáctky jsou 1, 2, 3, 4, 6 a 12. Společný dělitel dvou čísel je číslo, které dělí obě. Čísla 12 a 18 mají společné dělitele 1, 2, 3 a 6 a z nich je největší šestka.

Všimněte si, že ostatní společní dělitelé (1, 2, 3) jsou zároveň děliteli šestky. To platí vždy: každý společný dělitel dělí i NSD. Největší společný dělitel je nejvýš tak velký jako menší z čísel a nejméně 1, protože jednička dělí každé číslo. Dvě čísla tedy NSD mají vždy, i když je to jen jednička.

Občas se hledá „největší společný násobek“. Takový neexistuje: společných násobků je nekonečně mnoho a žádný není největší. Ve škole se počítá největší společný dělitel a nejmenší společný násobek, ten popisuje článek Nejmenší společný násobek.

1. způsob: vypsání dělitelů

Vypište všechny dělitele obou čísel a najděte největšího, který je v obou seznamech. Rychlejší je vypsat jen dělitele menšího čísla, procházet je od největšího a u každého se zeptat, jestli dělí i to větší. První, který vyhoví, je NSD.

Příklad 1

Určete největší společný dělitel čísel 18 a 30.

Dělitelé osmnáctky od největšího: 18, 9, 6, 3, 2, 1. Číslo 30 osmnácti dělitelné není, devíti také ne (30 : 9 je 3, zbytek 3), ale 30 : 6 = 5.

`D(18,\ 30)=6`

Kontrola: 18 : 6 = 3 a 30 : 6 = 5. Podíly 3 a 5 už žádného společného dělitele kromě jedničky nemají, takže větší společný dělitel být nemůže.

U čísel do 50 je vypisování pohodlné. U čísel jako 692 a 734 by se dělitelé hledali dlouho, a tam se vyplatí rozklad nebo Euklidův algoritmus.

2. způsob: prvočíselný rozklad

Každé číslo rozložte na součin prvočísel (postup ukazuje článek Prvočíselný rozklad). NSD je součin jen těch prvočísel, která jsou ve všech rozkladech, a každé z nich vezmete s nejmenším exponentem, s jakým se v rozkladech objevuje.

Příklad 2

Určete D(78, 168).

`78=2\cdot 3\cdot 13`
`168=2^{3}\cdot 3\cdot 7`

V obou rozkladech jsou dvojka a trojka. Třináctka je jen v prvním a sedmička jen ve druhém, ty do NSD nepatří. Dvojka má menší exponent 1 (u 78), trojka je v obou jednou:

`D(78,\ 168)=2\cdot 3=6`

Kontrola: 78 : 6 = 13 a 168 : 6 = 28. Podíly 13 a 28 jsou nesoudělné, takže 6 je opravdu největší.

Proč nejmenší exponent

Je to vidět na obrázku. Prvočinitele obou čísel rozdělíme do dvou kruhů tak, aby ti společní byli v průniku:

Dělitel čísla 78 může obsahovat jen to, co je v levém kruhu, dělitel čísla 168 jen to, co je v pravém. Společný dělitel tedy smí obsahovat jen to, co je v obou, a největší je ten, který vezme celý průnik: 2 · 3 = 6. Dvojka je v průniku jen jednou, protože 78 ji obsahuje jen jednou, a víc dvojek by sedmdesát osm nevydělilo. Proto menší exponent. Součin všeho v obrázku dohromady, 13 · 2 · 3 · 2 · 2 · 7 = 2184, je naopak nejmenší společný násobek.

Příklad 3: tři čísla

U více čísel se postupuje stejně, jen se hledají prvočísla, která jsou ve všech rozkladech. Určete D(84, 112, 168).

`84=2^{2}\cdot 3\cdot 7`
`112=2^{4}\cdot 7`
`168=2^{3}\cdot 3\cdot 7`

Ve všech třech řádcích jsou dvojka a sedmička. Trojka chybí u 112, takže do NSD nepatří. Nejmenší exponent dvojky je 2 (u 84):

`D(84,\ 112,\ 168)=2^{2}\cdot 7=28`

Kontrola: 84 : 28 = 3, 112 : 28 = 4 a 168 : 28 = 6.

3. způsob: Euklidův algoritmus

Euklidův algoritmus nepotřebuje rozklad, jen dělení se zbytkem, a proto je u velkých čísel nejrychlejší. Popsal ho Eukleidés kolem roku 300 před naším letopočtem. Postup:

Větší číslo vydělte menším se zbytkem.
Dělitele a zbytek vezměte jako novou dvojici čísel a znovu dělte.
Opakujte, dokud nevyjde zbytek 0. NSD je poslední nenulový zbytek, tedy dělitel v posledním řádku.

Příklad 4

Určete největší společný dělitel daných čísel 692 a 734.

`\begin{aligned} 734&=1\cdot 692+42\\[4pt] 692&=16\cdot 42+20\\[4pt] 42&=2\cdot 20+2\\[4pt] 20&=10\cdot 2+0 \end{aligned}`

Poslední nenulový zbytek je 2, takže

`D(692,\ 734)=2`

Kontrola rozkladem: 692 = 2² · 173 a 734 = 2 · 367, kde 173 i 367 jsou prvočísla. Společná je jen jedna dvojka. Tady je vidět, proč je Euklidův algoritmus pohodlnější: k rozkladu byste museli zjistit, že 367 je prvočíslo, a to znamená zkoušet dělit všemi prvočísly do 19.

Proč to funguje

Každé číslo, které dělí dvě čísla, dělí i jejich rozdíl. Když dělí 734 a 692, dělí i 734 − 692 = 42, a naopak, co dělí 692 a 42, dělí i jejich součet 734. Dvojice (734, 692) a (692, 42) mají tedy úplně stejné společné dělitele, a tím i stejného největšího. Dělení se zbytkem je jen opakované odčítání najednou. Čísla se tak zmenšují, až jedno z nich dělí druhé beze zbytku, a pak je NSD to menší.

Na obrázku je to vidět jako krájení obdélníku. Z obdélníku 42 × 30 odřízneme co největší čtverce, ze zbytku zase co největší čtverce, a tak dál. Nejmenší čtverec, kterým se zbytek vyplní beze zbytku, má stranu D(42, 30) = 6:

`\begin{aligned} 42&=1\cdot 30+12\\[4pt] 30&=2\cdot 12+6\\[4pt] 12&=2\cdot 6+0 \end{aligned}`

Příklad 5

Určete D(462, 1071).

`\begin{aligned} 1071&=2\cdot 462+147\\[4pt] 462&=3\cdot 147+21\\[4pt] 147&=7\cdot 21+0 \end{aligned}`

Poslední nenulový zbytek je 21, D(462, 1071) = 21. Zkouška: 462 : 21 = 22 a 1071 : 21 = 51.

U tří čísel spočítejte NSD prvních dvou a pak NSD výsledku a třetího čísla. Například D(84, 112) = 28 a D(28, 168) = 28, takže D(84, 112, 168) = 28, stejně jako v příkladu 3.

4. způsob: přes nejmenší společný násobek

Pro dvě čísla platí, že součin NSD a NSN se rovná součinu obou čísel:

`D(a,\ b)\cdot n(a,\ b)=a\cdot b`
`D(a,\ b)=\dfrac{a\cdot b}{n(a,\ b)}`

U čísel 32 a 54 je n(32, 54) = 864, takže D(32, 54) = 32 · 54 : 864 = 1728 : 864 = 2. Tenhle způsob se hodí, když už NSN znáte, například z předchozí úlohy. Platí ale jen pro dvě čísla. U tří čísel postupujte po dvojicích.

Kdy NSD vidíte hned

Jedno číslo dělí druhé. Pak je NSD to menší: D(15, 45) = 15, D(7, 91) = 7.
Dvě různá prvočísla mají NSD 1: D(13, 29) = 1.
Dvě po sobě jdoucí čísla mají NSD vždy 1, protože jejich rozdíl je 1: D(44, 45) = 1.
Obě čísla jsou sudá: NSD je aspoň 2. Obě končí nulou: NSD je aspoň 10, D(40, 70) = 10.

Soudělná a nesoudělná čísla

Čísla, jejichž největší společný dělitel je 1, se nazývají nesoudělná. Čísla s NSD větším než 1 jsou soudělná. Čísla 35 a 64 jsou nesoudělná, D(35, 64) = 1, přestože ani jedno z nich není prvočíslo: 35 = 5 · 7 a 64 = 2⁶ nemají žádné společné prvočíslo. Čísla 158, 131 a 257 jsou také nesoudělná (158 = 2 · 79, 131 a 257 jsou prvočísla). Jestli jsou dvě čísla nesoudělná, ověří kalkulačka Nesoudělná čísla.

Když jsou rozklady bez společného prvočísla, NSD není „žádný“ ani 0. Je to vždy 1.

NSD a krácení zlomků

Zlomek je v základním tvaru, když jsou čitatel a jmenovatel nesoudělné. Když je vydělíte jejich největším společným dělitelem, dostanete základní tvar na jeden krok:

`\dfrac{84}{126}=\dfrac{84:42}{126:42}=\dfrac{2}{3}`

Tady D(84, 126) = 42. Krátit jde i postupně (dvěma, pak třemi, pak sedmi) a výsledek je stejný, jen to trvá déle a snadno se zapomene na poslední krok. Když po krácení čitatel a jmenovatel ještě mají společného dělitele, nekrátili jste největším. Krácení s postupem ukazuje kalkulačka Krácení zlomků, procvičit si ho můžete v procvičování krácení zlomků a další počítání se zlomky najdete v článku Zlomky - sčítání, odčítání, násobení a dělení.

NSD a NSN: jaký je rozdíl

NSD je největší dělitel, takže je nejvýš tak velký jako menší z čísel. NSN je nejmenší násobek, takže je aspoň tak velký jako větší z čísel. U 12 a 18 je D = 6 a n = 36. V rozkladu se pro NSD berou jen společná prvočísla s menším exponentem, pro NSN všechna s větším. Podrobné srovnání s tabulkou je v článku Nejmenší společný násobek.

Ve slovní úloze poznáte NSD podle toho, že se něco dělí na co největší stejné části, skupiny nebo kusy beze zbytku. Když se naopak něco opakuje a ptáte se, kdy se to znovu sejde, jde o NSN.

Slovní úlohy na největší společný dělitel

Příklad 6: kytice

Květinářka má 90 tulipánů a 126 narcisů. Chce z nich uvázat co nejvíce stejných kytic a použít všechny květiny. Kolik kytic uváže a co bude v každé?

Počet kytic musí dělit 90 i 126, a má být co největší, takže hledáme D(90, 126). Rozklady 90 = 2 · 3² · 5 a 126 = 2 · 3² · 7 dávají D = 2 · 3² = 18. Uváže 18 kytic, v každé 90 : 18 = 5 tulipánů a 126 : 18 = 7 narcisů.

Příklad 7: dlažba

Podlaha má rozměry 4,20 m × 3,60 m. Chceme ji vydláždit co největšími čtvercovými dlaždicemi tak, aby se žádná nemusela řezat. Jak velké dlaždice potřebujeme a kolik jich bude?

Převedeme na centimetry, 420 cm a 360 cm. Strana dlaždice musí dělit obě délky a má být co největší: D(420, 360) = 60. Euklidovým algoritmem 420 = 1 · 360 + 60 a 360 = 6 · 60 + 0. Dlaždice 60 cm × 60 cm, do délky se jich vejde 420 : 60 = 7, do šířky 360 : 60 = 6, celkem 42 dlaždic. Kontrola plochou: 420 · 360 = 151 200 cm² a 42 · 60 · 60 = 151 200 cm².

Časté chyby

Záměna NSD a NSN. NSD nesmí být větší než menší z čísel. Když vám D(12, 18) vyjde 36, spočítali jste násobek.
Větší exponent místo menšího. U 78 = 2 · 3 · 13 a 168 = 2³ · 3 · 7 dá větší exponent dvojky 2³ · 3 = 24, a to sedmdesát osm nevydělí. Správně je D(78, 168) = 6.
Prvočíslo, které není ve všech rozkladech. Do NSD patří jen společná prvočísla. Kdo u 78 a 168 přidá sedmičku, dostane 42, a 78 : 42 nevychází.
Špatné číslo z Euklidova algoritmu. Výsledek je poslední nenulový zbytek, ne poslední podíl a ne nula. U 692 a 734 je to 2, i když poslední podíl je 10.
„NSD neexistuje.“ Nesoudělná čísla mají NSD 1, ne 0 a ne „žádný“.
Vzorec se součinem pro tři čísla. U 4, 6 a 10 je součin 240 a n(4, 6, 10) = 60, ale 240 : 60 = 4 není NSD. Šestka ani desítka čtyřmi dělitelná není, správně je D(4, 6, 10) = 2.

Zkouška je u NSD snadná: vydělte jím každé ze zadaných čísel. Všechna dělení musí vyjít beze zbytku a podíly musí být nesoudělné. Kdyby měly společného dělitele, dalo by se jím NSD ještě zvětšit.

Příklady k procvičení

1. Vypsáním dělitelů určete D(16, 40).

2. Pomocí prvočíselného rozkladu určete D(90, 150).

3. Euklidovým algoritmem určete D(221, 391).

D(221, 391) = 17.

`\begin{aligned} 391&=1\cdot 221+170\\[4pt] 221&=1\cdot 170+51\\[4pt] 170&=3\cdot 51+17\\[4pt] 51&=3\cdot 17+0 \end{aligned}`

Poslední nenulový zbytek je 17. Zkouška: 221 = 13 · 17 a 391 = 23 · 17.

4. Určete největší společný dělitel čísel 48, 80 a 112.

5. Zkraťte zlomek 168/252 na základní tvar jedním krokem.

2/3.

Rozklady jsou 168 = 2³ · 3 · 7 a 252 = 2² · 3² · 7, takže D(168, 252) = 2² · 3 · 7 = 84.

`\dfrac{168}{252}=\dfrac{168:84}{252:84}=\dfrac{2}{3}`

6. Tři stuhy jsou dlouhé 84 cm, 126 cm a 210 cm. Chceme je rozstříhat na stejně dlouhé kusy, co nejdelší, a nesmí nic zbýt. Jak dlouhý bude každý kus a kolik kusů bude celkem?

Kam dál

NSD a NSN dohromady si procvičte v procvičování NSD a NSN, rozklad čísel v procvičování Dělitelé a prvočinitelé a krácení v procvičování krácení zlomků.

Největšího společného dělitele dvou nebo tří čísel i s Euklidovým algoritmem a rozklady spočítá kalkulačka Největší společný dělitel, všechny dělitele čísla vypíše kalkulačka Dělitelé čísla a rozklad udělá kalkulačka Rozklad na prvočinitele.

Související články: Nejmenší společný násobek, Prvočíselný rozklad, Prvočíslo a Zlomky - sčítání, odčítání, násobení a dělení.