Kalkulačka GCD a LCM

GCD, nazývaný aj najväčší spoločný deliteľ (GCF), je najväčšie kladné celé číslo, ktoré delí obe čísla bez zvyšku. Napríklad GCD čísel 12 a 18 je 6, pretože 6 je najväčšie číslo, ktoré rovnomerne delí obe čísla.

LCM je najmenšie kladné celé číslo, ktoré je deliteľné oboma číslami. Napríklad LCM 4 a 6 je 12, pretože 12 je najmenšie číslo deliteľné 4 aj 6.

Pre ľubovoľné dve kladné celé čísla a a b platí: GCD(a,b) × LCM(a,b) = a × b. Tento vzťah umožňuje vypočítať LCM, ak poznáte GCD, alebo naopak.

GCD je nevyhnutný na zjednodušovanie zlomkov (delenie čitateľa a menovateľa ich GCD), riešenie diofantických rovníc a rôzne aplikácie v kryptografii a informatike.

Ak chcete zlomok zjednodušiť, vydeľte čitateľa aj menovateľa ich GCD. Napríklad na zjednodušenie 24/36: nájdite GCD(24,36) = 12, potom vydeľte obidva zlomky 12 a dostanete 2/3. Takto získate zlomok v jeho najnižšom členení.

LCM sa používa pri synchronizácii opakujúcich sa udalostí. Príkladom je zistenie, kedy dva autobusy prídu v rovnakom čase, určenie spoločných menovateľov pre sčítanie zlomkov, plánovanie opakujúcich sa úloh alebo plánovanie, kedy sa ozubené kolesá s rôznym počtom zubov zoradia.

Rozdeľte každé číslo na prvočinitele a potom vynásobte spoločné prvočinitele najnižšími mocninami. Napríklad 48 = 2^4 × 3 a 18 = 2 × 3^2. Spoločné činitele sú 2^1 a 3^1, takže GCD = 2 × 3 = 6.

Každé číslo rozdeľte na prvočinitele a potom všetky prvočinitele vynásobte pomocou najvyšších mocnín. V prípade 12 = 2^2 × 3 a 18 = 2 × 3^2 zoberte 2^2 a 3^2, takže LCM = 4 × 9 = 36.

Euklidovský algoritmus efektívne nájde GCD opakovaným delením a vyberaním zvyškov. Pre GCD(48,18): Keď je zvyšok 0, posledný deliteľ (6) je GCD.