Nejmenší společný násobek

Nejmenším společným násobkem (nsn, least common multiple - zkratka: lcm) přirozených čísel $n_{1}, n_{2}, \\cdots, n_{x}$ je číslo, které je násobkem každého z čísel $n_{1},\\; n_{2}, \\cdots,\\; n_{x}$ a je minimální.

Nejmenší společný násobek čísel $n_{1},\\; n_{2}, \\cdots,\\; n_{x}$ značíme jako:

$lcm(n_{1},\\; n_{2}, \\cdots,\\; n_{x})$

Výpočet

Rozklad na prvočísla

Nejjednodušším způsobem výpočtu nejmenšího společného násobku čísel $n_{1},\\; n_{2}, \\cdots,\\; n_{x}$ je tato čísla rozložit na prvočísla a z rozkladů vybrat prvočinitele v nejvyšších mocninách. Jejich následným vynásobením získáme $lcm(n_{1},\\; n_{2}, \\cdots,\\; n_{x})$ .

Příklad

Jaký je nejmenší společný násobek čísel 6, 8 a 15?

$6 = 2 \\cdot 3 = 2^1 \\cdot 3^{1}$
$8 = 2\\cdot 2 \\cdot 2 = 2^{3}$
$15 = 5 \\cdot 3 = 5^{1} \\cdot 3^{1}$
$lcm(6,\\; 8,\\; 15) = 2^{3} \\cdot 3^{1} \\cdot 5 = 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 5 = 120$

Příklad

Jaký je nejmenší společný násobek čísel 140 a 72.

$140 = 2\\cdot 2\\cdot 7\\cdot 5 = 2^{2}\\cdot 5^{1}\\cdot 7^{1}$
$72 = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3 = 2^{3}\\cdot 3^{2}$
$lcm(140,\\; 72) = 2^{3} \\cdot 3^{2} \\cdot 5^{1} \\cdot 7^{1} = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3\\cdot 5\\cdot 7 = 2520$

Příklad

Jaký je nejmenší společný násobek čísel 288 a 420?

$288 = 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 3 = 2^{5} \\cdot 3^{2}$
$420 = 2 \\cdot 2 \\cdot 3 \\cdot 5 \\cdot 7 = 2^{2} \\cdot 3^{1} \\cdot 5^{1} \\cdot 7^{1}$
$lcm(288,\\; 420) = 2^{5} \\cdot 3^{2} \\cdot 5^{1} \\cdot 7^{1} = 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 3 \\cdot 5 \\cdot 7 = 10080$

Výše zmíněný postup si můžeme ilustrovat také pomocí Vennova diagramu, v němž budou čísla 288 a 420 reprezentována množinami svých prvočíselných dělitelů. Jelikož tyto množiny mají společné dělitele (průnik množin) uvedeny právě jednou, tak na diagramu najdeme všechny prvočinitele v jejich nejvyšších mocninách. Vynásobením všech čísel z diagramu tedy získáme nejmenší společný násobek čísel 288 a 420 (tj. 10080).

Nejmenší společný násobek pomocí Vennova diagramu

Euklidův algoritmus

Pro výpočet nejmenšího společného násobku dvou čísel lze také využít přepočtu z největšího společného dělitele. Tato metoda je zejména u velkých čísel výrazně výpočetně jednodušší než rozklad na prvočísla.

$lcm(n_{1},\\; n_{2}) = {{n_{1} \\cdot n_{2} } \\over {gcd(n_{1},\\; n_{2})} }$

Pro efektivní výpočet nejvyššího společného dělitele můžeme použít Euklidův algoritmus.

Příklad

$gcd(140,\\; 72) = 4$
$lcm(140,\\; 72) = {{140 \\cdot 72} \\over {gcd(140,\\; 72)}} = {{10080} \\over {4}} = 2520$

Kód

/**
 * Returns least common multiple of two numbers
 * @param a number 1
 * @param b number 2
 * @return lcm(a, b)
 */
public static int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return (a * b) / gcd(a, b);
}
 
/**
 * Returns greatest common divisor of the given numbers
 * @param a number 1
 * @param b number 2
 * @return gcd(a, b)
 */
public static int gcd(int a, int b) {
    if (a < 1 || b < 1) {
        throw new IllegalArgumentException("a or b is less than 1");
    }
    int remainder = 0;
    do {
        remainder = a % b;
        a = b; 
        b = remainder;
    } while (b != 0);
    return a;
}

/**
 * Nejmensi spolecny nasobek cisel "a" a "b"
 * @param a cislo "a"
 * @param b cislo "b"
 * @return lcm(a, b)
 * @autor Thomas (www.adamjak.net)
 */
public static int lcm(int a, int b)
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    return (a * b) / gcd(a, b);
}
 
/**
 * Nejvetsi spolecny delitel cisel "a" a "b"
 * @param a cislo "a"
 * @param b cislo "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
public static int gcd(int a, int b)
{
    if (a < 1 || b < 1)
    {
        throw new ArgumentException("a or b is less than 1");
    }
    int r = 0;
    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (b != 0);
    return a;
}

/**
 * Nejmensi spolecny nasobek cisel "a" a "b"
 * @param $a cislo "a"
 * @param $b cislo "b"
 * @return lcm(a, b)
 * @autor Thomas (www.adamjak.net)
 */
function lcm($a, $b) {
    if ($a == 0 || $b == 0) {
        return 0;
    }
    return ($a * $b) / gcd($a, $b);
}
 
/**
 * Nejvetsi spolecny delitel cisel "a" a "b"
 * @param $a cislo "a"
 * @param $b cislo "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
function gcd($a, $b) {
    if ($a < 1 || $b < 1) {
        die("a or b is less than 1");
    }
    $r = 0;
    do {
        $r = $a % $b;
        $a = $b;
        $b = $r;
    } while ($b != 0);
    return $a;
}

Literatura

POLÁK, Josef. Přehled středoškolské matematiky. 8. vydání. Praha 4 : Prometheus, 2005. 608 s.

Výpočet

Rozklad na prvočísla

Příklad

Příklad

Příklad

Euklidův algoritmus

Příklad

Kód

Literatura

Doporučujeme