Kalkulačka NSD – Největší společný dělitel

Co je největší společný faktor (GCF)?

Největší společný faktor (GCF) — také známý jako největší společný dělitel (GCD) nebo nejvyšší společný faktor (HCF) — je největší kladný celočíselný počet, který dělí dva nebo více čísel bez zbytečného zbytku. Je to základní koncept v teorii čísel a má praktické aplikace v zjednodušení frakcí, řešení složitých úloh a rozdělení věcí do stejného počtu skupin.

Pro příklad jsou faktory 24: 1, 2, 3, 4, 6, 8, 12, 24. Faktory 36 jsou: 1, 2, 3, 4, 6, 9, 12, 18, 36. Společné faktory jsou: 1, 2, 3, 4, 6, 12. Největší z nich je 12, takže GCF(24, 36) = 12.

GCF je spojen s nejmenším společným násobkem (LCM) prostřednictvím fundamentální identity: GCF(a, b) × LCM(a, b) = a × b. To znamená, že pokud znáte GCF, můžete snadno vypočítat LCM a naopak. Pro 24 a 36: GCF = 12, LCM = 24 × 36/12 = 72.

Metody pro nalezení GCF

Existují tři hlavní metody pro nalezení GCF. Každá má své výhody v závislosti na velikosti čísel.

Metoda 1: Seznamování faktorů

Seznamte si všechny faktory každého čísla a identifikujte největší společný. Toto funguje dobře pro malé čísla, ale stává se obtížným pro velké čísla.

Příklad: GCF(18, 24). Faktory 18: 1, 2, 3, 6, 9, 18. Faktory 24: 1, 2, 3, 4, 6, 8, 12, 24. Společné: 1, 2, 3, 6. GCF = 6.

Metoda 2: Primární faktorizace

Vyjmenujte každé číslo jako produkt prvočíselných faktorů a poté násobte společné prvočíselné faktory (použijte nejnižší exponent pro každé).

Příklad: GCF(120, 180). 120 = 2³ × 3 × 5. 180 = 2² × 3² × 5. Společné prvočíselné faktory: 2² × 3 × 5 = 4 × 3 × 5 = 60. GCF(120, 180) = 60.

Metoda 3: Euklidův algoritmus

Euklidův algoritmus je nejefektivnější metoda, zejména pro velké čísla. Je založen na vlastnosti, že GCF(a, b) = GCF(b, a mod b). Opakujte, dokud nebude zbytek 0; poslední nenulový zbytek je GCF.

Příklad: GCF(252, 105). Krok 1: 252 = 2 × 105 + 42. Krok 2: 105 = 2 × 42 + 21. Krok 3: 42 = 2 × 21 + 0. GCF = 21.

Tabulka GCF: Obvyklé dvojice čísel

Je zde uvedeno několik hodnot GCF pro často používané dvojice čísel v matematických úlohách a zjednodušování frakcí:

Poznámka: Když GCF(a, b) = b, b dělí a přesně. Když GCF(a, b) = 1, čísla jsou korektní — sdílejí žádné společné faktory kromě 1. Korektní čísla jsou důležité v kryptografii, zejména v RSA šifrování, kde je výběr korektních čísel pro generování klíčů klíčový.

Sjednocení lomených čísel pomocí GCF

Nejčastěji se GCF používá k zjednodušení lomených čísel na nejnižší podobu. K zjednodušení lomeného čísla a/b rozdělte obě čísla v lomeném číslu dělitelným číslem GCF(a, b).

Příklady:

• 48/60: GCF(48, 60) = 12. → 48÷12 / 60÷12 = 4/5 ✓
• 56/84: GCF(56, 84) = 28. → 56÷28 / 84÷28 = 2/3 ✓
• 75/100: GCF(75, 100) = 25. → 75÷25 / 100÷25 = 3/4 ✓
• 144/360: GCF(144, 360) = 72. → 144÷72 / 360÷72 = 2/5 ✓

Lomené číslo je v nejnižší podobě (nejjednodušší podobě), pokud GCF(numerator, denominator) = 1. Například 3/5 je již v nejnižší podobě, protože GCF(3, 5) = 1. Lomené číslo 6/10 není v nejnižší podobě, protože GCF(6, 10) = 2 → 3/5.

V kuchyni pomáhá GCF při měření receptů. Pokud recept je určen pro 24 osob, ale chcete podávat 18, potřebujete 18/24 = 3/4 každého ingredience. GCF(18, 24) = 6, takže 18/24 → 3/4. Vynásobte všechny množství 3/4.

GCF v reálných aplikacích

Přibližně kromě zjednodušování lomených čísel řeší GCF několik typů praktických problémů:

Rovnoměrné rozdělení: Máte 36 jablíček a 48 pomerančů, které chcete balit do košíků, přičemž každý košík obsahuje stejný počet každé ovoce a žádné ovoce nezbývá. Maximální počet košíků je GCF(36, 48) = 12. Každý košík dostane 3 jablíčka a 4 pomeranče.

Tvarové problémy: Chcete pokrýt 120cm × 180cm podlahu čtverečkovými dlaždicemi, minimalizujte odpady. Největší čtverečková dlaždice, která funguje dokonale, má stranu GCF(120, 180) = 60 cm. Potřebujete (120/60) × (180/60) = 2 × 3 = 6 dlaždic.

Plánování: Akce A se opakuje každé 12 dní, Akce B každé 18 dní. Následují se společně po LCM(12, 18) = 36 dnech. GCF(12, 18) = 6 vám říká jednotkový cyklus; LCM = 12×18/6 = 36.

Kryptografie: Algoritmus RSA vyžaduje výběr dvou velkých prvočísel p a q. Veřejný klíč n = p×q a Eulerova totient φ(n) = (p-1)(q-1). Pro bezpečné fungování algoritmu musí být šifrovací exponent e korektní k φ(n) – tj. GCF(e, φ(n)) = 1. Korektnost ověřuje pomocí euklidovského algoritmu.

Evklidův algoritmus: Historie a důkaz

Evklidův algoritmus, popsaný v Evklidových Elementech (Kniha VII, Proposition 2, přibližně 300 př. n. l.), je jedním z nejstarších algoritmů v matematice – předchází většině moderní matematice o více než dva tisíce let. Zůstává v široké komerční používání dodnes, jako důkaz jeho elegance a efektivnosti.

Algoritmus: Najít GCF(a, b) kde a > b: rozdělit a na b, získat zlomky q a r. Potom GCF(a, b) = GCF(b, r). Opakovat, dokud r = 0; poslední nenulový zbytek je GCF.

Proč funguje: Pokud d dělí a a b, pak d dělí a - q×b = r. Naopak, pokud d dělí b a r, pak d dělí b×q + r = a. Takže soubor společných dělitelů (a, b) rovná se souboru společných dělitelů (b, r). Jejich GCFs musí být stejné.

Efficiency: V nejhorším případě (po sobě jdoucí Fibonacciho čísla), algoritmus vyžaduje O(log(min(a,b))) kroků. GCF(F(n+1), F(n)) vyžaduje přesně n kroků – proto jsou po sobě jdoucí Fibonacciho čísla nazývána "nejhorším případem" pro Evklidův algoritmus. Pro GCF(144, 89): 144 = 1×89 + 55; 89 = 1×55 + 34; 55 = 1×34 + 21; 34 = 1×21 + 13; 21 = 1×13 + 8; 13 = 1×8 + 5; 8 = 1×5 + 3; 5 = 1×3 + 2; 3 = 1×2 + 1; 2 = 2×1 + 0. GCF = 1. (10 kroků, jak je očekáváno pro F(12)/F(11).)

GCF vs LCM: Klíčové rozdíly a spojení

GCF (Největší společný faktor) a LCM (Nejmenší společný násobek) jsou komplementární operace. Porozumění, kdy použít každý, je zásadní pro aritmetiku s frakcemi.

Abyste přidali frakce 1/12 + 1/18: najděte LCM(12, 18) = 36. Převést: 3/36 + 2/36 = 5/36. Abyste zjednodušili 12/18: najděte GCF(12, 18) = 6. Rozdělit: 2/3.

Rozšířený euklidovský algoritmus a Bézoutova identita

Rozšířený euklidovský algoritmus nejenom vypočítá NWW (největší společný dělitel) (a, b), ale také najde celočíselné x a y takové, že ax + by = NWW(a, b). Toto je Bézoutova identita, a celočíselné x a y se nazývají Bézoutovy koeficienty. To má zásadní aplikace v aritmetice modulů a kryptografii.

První příklad: Najděte x a y takové, že 24x + 36y = NWW(24, 36) = 12. Pracujeme zpět skrze kroky euklidovského algoritmu: 12 = 24 - 1 × 12 = 24 - 1 × (36 - 1 × 24) = 2 × 24 - 1 × 36. Takže x = 2, y = -1. Ověřte: 24 × 2 + 36 × (-1) = 48 - 36 = 12 ✓.

Modulární inverzní číslo a modulo m existuje pouze tehdy, pokud NWW(a, m) = 1. Pokud existuje, lze jej najít pomocí rozšířeného euklidovského algoritmu. Například inverzní číslo 7 mod 11: NWW(7, 11) = 1 (kolineární), takže inverzní číslo existuje. 7 × 8 = 56 = 5 × 11 + 1 ≡ 1 (mod 11), takže 7⁻¹ ≡ 8 (mod 11). To je základem pro dešifrování RSA a mnoho dalších kryptografických operací.

NWW pro frakce, poměry a proporce

NWW je nepostradatelný při práci s poměry a proporcemi v každodenních situacích. Poměr 48:64 lze zjednodušit dělením obou členů NWW(48, 64) = 16, což dává ekvivalentní poměr 3:4. Toto zjednodušení usnadňuje srovnávání a odhaluje podkladový vztah.

Při pečení a vaření často potřebují recepty být měněny. Pokud recept vyžaduje 450g mouky a 300g cukru, poměr je 450:300. NWW(450, 300) = 150. Zjednodušený poměr: 3:2. Pro jakoukoli velikost dávky použijte mouku a cukr v poměru 3:2.

Mapové měřítko používá poměry. Měřítko 1:50 000 znamená 1 mapový jednotku = 50 000 skutečných jednotek. Pokud chcete vyjádřit měření 150 cm na mapě jako skutečnou vzdálenost 75 000 cm, zjednodušte poměr 150:75 000. NWW(150, 75000) = 150. Zjednodušený poměr: 1:500. Takže měřítko mapy je 1:500 pro toto měření.