NSD kalkulačka

Kalkulačka vypočíta najväčšieho spoločného deliteľa (NSD) ľubovoľných prirodzených čísel.


Ako používať NSD kalkulačku

Do poľa zadajte ľubovoľný počet prirodzených čísel oddelených medzerou a kliknite na “Vypočítať”. Naša kalkulačka vypočíta najväčší spoločný deliteľ na základe Euklidovho algoritmu.

Čo je najväčší spoločný deliteľ

Pod pojmom deliteľ sa v popisovanej problematike myslí prirodzené číslo, ktoré delí iné prirodzené číslo bez zvyšku.

Ak dve prirodzené čísla majú toho istého deliteľa, je to ich spoločný deliteľ.

Napríklad čísla 18 a 24 majú spoločného deliteľa číslo 6. Čísla 18 a 24 nazývame súdeliteľné čísla.

Každé dve prirodzené čísla majú aspoň jedného spoločného deliteľa, je to číslo 1.

Zo všetkých spoločných deliteľov dvoch prirodzených čísel je vždy jeden najväčší, nazýva sa najväčší spoločný deliteľ.

Ak je najväčší spoločný deliteľ dvoch prirodzených čísel číslo 1, čísla nazývame nesúdeliteľné.

Najpoužívanejšie metódy nájdenia NSD

Porovnávanie deliteľov a výber najväčšieho

Táto metóda zahŕňa vyhľadávanie všetkých deliteľov porovnávaných čísel a identifikáciu najväčšieho spoločného deliteľa.

Rozklad na prvočinitele

Metóda spočíva v rozložení čísel na súčin prvočísel. Následne určíme najväčší spoločný deliteľ, ktorý sa skladá zo všetkých prvočíselných faktorov, ktoré majú obe čísla spoločné, pričom berieme do úvahy najmenší exponent z každého prvočiniteľa.

Euklidov algoritmus

Euklidov algoritmus je najefektívnejší a najčastejšie používaný spôsob na výpočet NSD. Tento algoritmus sa zakladá na tom, že NSD dvoch čísel sa nemení, ak väčšie číslo nahradíme zvyškom po delení väčšieho čísla tým menším.

Najväčší spoločný deliteľ príklady a riešenie

Úloha: Nájdime najväčšieho spoločného deliteľa čísel 36 a 48.

Riešenie metódou porovnania deliteľov a výber najväčšieho

Skúsme úlohu vyriešiť tak, že nájdeme všetky delitele čísel 36 a 48 a potom zo spoločných deliteľov vyberieme najväčšieho.

Delitele čísla 36 sú: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Delitele čísla 48 sú: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.

Spoločné delitele sú 1, 2, 3, 4, 6, 12, najväčší z nich je 12, tzn. je to ich najväčší spoločný deliteľ a zapisujeme ako D(36, 48) = 12.

Výsledok: NSD čísel 36 a 48 je číslo 12.

Riešenie metódou rozkladu na prvočinitele

Úlohu môžeme riešiť aj rozložením čísel 36 a 48 na prvočinitele.

Každé prirodzené číslo väčšie ako 1 sa dá jediným spôsobom, až na poradie činiteľov, vyjadriť ako súčin prvočísel.

Prvočísla v takomto zápise sa nazývajú prvočinitele.

Najväčší spoločný deliteľ bude súčinom prvočiniteľov, ktoré sa nachádzajú v rozkladoch obidvoch čísel:

36 = 2 x 2 x 3 x 3 

48 = 2 x 2 x 2 x 2 x 3

Teda spoločnými číslami sú čísla 2 x 2 x 3 = 12

Výsledok: Najväčší spoločný deliteľ čísel 36 a 48, na základe rozkladu na prvočinitele, je číslo 12.

Riešenie metódou Euklidovho algoritmu

Ako sme už písali, existuje viacero spôsobov k dosiahnutiu výsledku NSD. Naša kalkulačka vypočíta výsledok NSD na základe Euklidového algoritmu.

  • Krok č.1: Určíme väčšie a menšie číslo
    • Väčšie číslo: a = 48
    • Menšie číslo: b = 36 
  • Krok 2: Vypočítame zvyšok “r” pri delení a číslom b
    • 48 mod 36 = 12 (Pri delení 48 číslom 36 je kvocient 1 a zvyšok 12)
  • Krok 3: Nahraďme a hodnotou b a b hodnotou zvyšku “r”
    • Teraz máme a = 36 a b = 12
  • Krok 4: Opakujeme výpočet zvyšku “r”
    • 36 mod 12 = 0 (Pri delení 36 číslom 12 je kvocient 3 a zvyšok 0)
  • Krok 5: Ak je zvyšok “r” = 0, NSD je hodnota b
    • Keďže “r” = 0, algoritmus končí a posledné nenulové b je NSD.

Výsledok: NSD (36,48) = 12. Tento výsledok znamená, že najväčšie číslo, ktoré delí 36 aj 48 bez zvyšku, je 12.

Využitie NSD v praxi

  • NSD používame pre krátenie zlomkov, napr. zlomok 36/48 vieme zjednodušiť vydelením čitateľa aj menovateľa ich NSD (12), čo dáva ¾,
  • v kryptografii, napr. v algoritme RSA, používame výpočet NSD na generovanie a kontrolu kľúčov. V konkrétnom algoritme je nevyhnutné, aby dve čísla boli navzájom nesúdeliteľné (t.j. ich NSD je 1 – nemajú žiadneho spoločného deliteľa, okrem 1 ),
  • pri optimalizácií algoritmov používame NSD v návrhu a optimalizácii, najmä pri návrhu cyklických procesov, kde potrebuje minimalizovať čas alebo počet krokov na základe spoločných deliteľov,
  • v teórii čísel, napr. pre dôkaz správnosti Euklidovho algoritmu,
  • v stavebníctve, napríklad pri návrhu modulárnych jednotiek, kde potrebujeme nájsť najväčší spoločný rozmer pre diely alebo panely.

Zdroje: