Největší společný dělitel a nejmenší společný násobek

Největší společný dělitel (NSD)

• Největší číslo, které dělí čísla $a$ i $b$
• Efektivní metodou pro nalezené je Eukleidův algoritmus
• Pokud je $NSD=1$, pak jsou čísla nesoudělná

Nejmenší společný násobek (NSN)

• Nejmenší číslo, které je spolčeným násobkem obou čísel
• Společný násobek je číslo, pro které platí: $x,y,n\in \mathbb{N}$ a $x\mid n$ i $y\mid n$
  • Z této množiny čísel vybereme největší a to je NSN

Věta - souvislost NSD a NSN

Nechť $x,y\in \mathbb{N}$ pak platí $NSD(x,y)\cdot NSN(x,y)=x\cdot y$.