Kalkulačka NSN a NSD

The GCD je největší kladné celé číslo, které dělí všechna zadaná čísla beze zbytku.

Použijte Euklidův algoritmus pro efektivní výpočet: opakovaně dělte a počítejte zbytky, dokud nedojdete k 0.

The LCM je nejmenší kladné celé číslo dělitelné všemi zadanými čísly.

Spočítejte pomocí prvočíselného rozkladu (vezměte nejvyšší mocniny) nebo vzorce: NSN = (a × b) / NSD.

The GCD (největší společný dělitel) je největší celé číslo, které přesně dělí každé zadané číslo, zatímco LCM (nejmenší společný násobek) je nejmenší kladné celé číslo, do kterého každé zadané číslo přesně dělí.

Fungují opačně: NSD se dívá směrem dolů na největší sdílený dělitel, NSN se dívá směrem nahoru na nejmenší sdílený násobek. Pro 12 a 18 je NSD 6 a NSN 36.

Podle Wolfram MathWorld se NSD také píše jako gcd(a, b) nebo (a, b) a termín „největší společný dělitel“ je běžné synonymum pro stejnou hodnotu.

Euklidův algoritmus hledá největší společný dělitel tak, že opakovaně nahrazuje větší číslo zbytkem po jeho vydělení menším číslem, dokud zbytek nedosáhne nuly; poslední nenulový zbytek je NSD.

Pro 48 a 18: 48 = 2×18 + 12, pak 18 = 1×12 + 6, pak 12 = 2×6 + 0, takže gcd(48, 18) = 6.

Encyklopedie Britannica uvádí, že tato metoda pochází z Euklidových Základů (kolem roku 300 př. n. l.), což z ní činí jeden z nejstarších algoritmů stále používaných v každodenní praxi. Díky své efektivitě ji softwarové knihovny využívají namísto rozkladu velkých čísel na součinitel.

Chcete-li najít NSN pomocí prvočíselného rozkladu, rozložte každé číslo na prvočísla a poté vynásobte každé prvočíslo umocněné na jeho nejvyšší mocninu, která se vyskytuje v jakémkoli rozkladu.

Pro 12 = 2²×3 a 18 = 2×3² vezměte 2² a 3², což dává NSN = 4×9 = 36. Pro NSD naopak vezměte každé společné prvočíslo v jeho nejnižší mocnině: 2¹×3¹ = 6.

Khan Academy učí toto srovnání vedle sebe, protože díky němu je kontrast mezi NSN a NSD názorný. Prvočíselný rozklad je intuitivní pro malá čísla, ale pomalejší než Euklidův algoritmus pro velká čísla, protože rozkládání je výpočetně náročné.

Pro libovolná dvě kladná celá čísla a a b platí NSN(a, b) × NSD(a, b) = a × b. Tato identita umožňuje vypočítat jednu veličinu z druhé: NSN(a, b) = (a × b) / NSD(a, b).

Pro 12 a 18 je NSD 6, takže NSN = (12 × 18) / 6 = 216 / 6 = 36 a skutečně 6 × 36 = 216 = 12 × 18.

Wolfram MathWorld dokumentuje tento vztah jako standardní můstek mezi oběma funkcemi. Všimněte si, že vzorec platí pouze pro dvě čísla; pro tři nebo více jej aplikujete po dvojicích, namísto abyste předpokládali, že součin se rovná NSN × NSD.

Pro tři nebo více čísel aplikujte NSD nebo NSN po dvojicích: vypočítejte výsledek prvních dvou, pak jej zkombinujte s dalším číslem a tak dále.

Například gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6 a lcm(4, 6, 8) = lcm(lcm(4, 6), 8) = lcm(12, 8) = 24. Obě operace jsou asociativní, takže pořadí seskupení výsledek nemění.

Tato kalkulačka zpracovává dávky automaticky, avšak zkratka NSN×NSD = součin se na tři nebo více vstupů nevztahuje, což je bod, který Wolfram MathWorld zdůrazňuje.

Dvě čísla jsou nesoudělná, když se jejich NSD rovná 1, což znamená, že nesdílejí žádné společné prvočinitele, i když ani jedno z nich samo o sobě není prvočíslem.

Například gcd(8, 15) = 1: 8 = 2³ a 15 = 3×5 nemají žádné společné prvočíslo, takže jsou nesoudělná. Když jsou čísla nesoudělná, jejich NSN se rovná jejich součinu; lcm(8, 15) = 120 = 8×15.

Wolfram MathWorld poznamenává, že nesoudělnost tvoří základ modulární aritmetiky a šifrování RSA, kde generování klíčů vyžaduje exponent nesoudělný s Eulerovou totientovou funkcí. Nesoudělnost je vlastnost dvojice, nikoli jednotlivých čísel.

NSN a NSD se objevují daleko za hranicemi učebnic.

NSD zjednodušuje zlomky na základní tvar (12/18 se po vydělení 6 zkrátí na 2/3) a nachází největší skupiny stejné velikosti při rozdělování položek – a jakmile jsou tyto skupiny pevně dány, kalkulačka faktoriálu spočítá možnosti uspořádání položek v rámci každé z nich.

NSN zjišťuje, kdy se opakující se události shodují, například dva autobusy odjíždějící každých 12 a 18 minut se znovu setkají po 36 minutách, a vytváří společného jmenovatele pro sčítání zlomků.

Inženýři používají NSD při návrhu převodových poměrů a rozvodových řemenů, zatímco kryptografové spoléhají na kontroly nesoudělnosti (NSD = 1) během nastavování klíče RSA, jak popisuje Encyclopaedia Britannica ve svém přehledu aplikací teoretické aritmetiky.

Bézoutova identita uvádí, že pro celá čísla a a b existují celá čísla x a y taková, že ax + by = gcd(a, b).

Pro 12 a 18 je gcd 6 a jedním řešením je 12×(−1) + 18×(1) = −12 + 18 = 6. Rozšířený Euklidův algoritmus vypočítá tyto koeficienty zároveň s výpočtem NSD, což je přesně způsob, jak se v kryptografii nacházejí modulární inverze.

Wolfram MathWorld a digitální knihovna matematických funkcí NIST považují Bézoutovu identitu za základní kámen elementární teorie čísel, protože zaručuje, že lineární kombinace rovnající se NSD vždy existuje.

Nkolik častých chyb lidi potrápí při počítání NSN a NSD:

• Častou chybou je záměna obou hodnot: NSD není nikdy větší než nejmenší vstup, zatímco NSN není nikdy menší než největší vstup, takže si svůj výsledek zkontrolujte oproti této hranici.

• Další chybou je předpoklad, že NSN × NSD = součin funguje pro tři nebo více čísel, což nefunguje.

• Lidé také zapomínají, že NSD a NSN jsou definovány pro kladná celá čísla, nikoli pro zlomky nebo desetinná čísla, takže vstupy musí být celá čísla.

• A konečně, když jsou čísla nesoudělná, pamatujte, že NSD je 1 (nikoli 0) a NSN se rovná jejich součinu.

Ověření pomocí identity NSN×NSD = a×b odhalí většinu přehmatů u dvou čísel.