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
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.







Místo pro váš banner

Zde je vyhrazené místo pro bannery našich partnerů a zákazníků.