Největší společný dělitel

Největším společným dělitelem (nsd, greatest common divisor (zkratka: gcd)) přirozených čísel $n_{1},\\; n_{2}, \\cdots,\\; n_{x}$ je číslo, které dělí každé z těchto čísel, a je maximální.

Výpočet

Rozklad na prvočísla

Nejjednodušším způsobem výpočtu největšího společného dělitele je rozložit jednotlivá zkoumaná čísla $n_{1},\\; n_{2}, \\cdots,\\; n_{x}$ na prvočísla a z nich vybrat prvočinitele v nejmenší společné mocnině (nejmenším z exponentů). Vynásobením prvočinitelů v příslušných mocninách získáme největšího společného dělitele daných čísel.

Příklad

Jaký je nejvyšší společný dělitel čísel 72, 48 a 54?

$72 = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3 = 2^{3} \\cdot 3^{2}$
$48 = 2\\cdot 2\\cdot 2\\cdot 2\\cdot 3 = 2^{4} \\cdot 3^{1}$
$54 = 2\\cdot 3\\cdot 3\\cdot 3 = 2^{1} \\cdot 3^{3}$
$gcd(72,\\; 48,\\; 54) = 2^{1}\\cdot 3^{1} = 2\\cdot 3 = 6$

Příklad

Jaký je nejvyšší společný dělitel čí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}$
$gcd(288,\\; 420) = 2^{2}\\cdot 3^{1} = 2 \\cdot 2 \\cdot 3 = 12$

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ů. V průniku těchto množin nalezneme největšího společného dělitele zmíněných čísel.

Největší společný dělitel pomocí Vennova diagramu

Euklidův algoritmus

Rozklad na prvočísla (faktorizace) je z výpočetního hlediska velmi náročný problém. Proto pro efektivní výpočet největšího společného dělitele velkých čísel používáme Euklidův algoritmus.

Princip

Vstupem algoritmu jsou dvě přirozená čísla a . Algoritmus v každém svém kroku vydělí se zbytkem číslo číslem . Pokud zbytek není nulový, tak do přiřadí číslo a zbytek po dělení přiřadí do uvolněné proměnné a celý postup opakuje.

V okamžiku, kdy je zbytek po dělení nulový, je v proměnné uložen největší společný dělitel čísel a .

Pro podrobnější výklad si můžete přečíst tento článek.

Příklad

Jaký je největší společný dělitel čísel 133 a 15?

$A = x \\cdot B + zbytek$
$133 = 8 \\cdot 15 + 13$
$15 = 1 \\cdot 13 + 2$
$13 = 6 \\cdot 2 + 1$
$2 = 2 \\cdot 1 + 0$
$gcd(133, \\; 15) = 1$

Příklad

Jaký je největší společný dělitel čísel 140 a 15?

$A = x \\cdot B + zbytek$
$140 = 9 \\cdot 15 + 5$
$15 = 3 \\cdot 5 + 0$
$gcd(140, \\; 15) = 5$

Nejmenší společný násobek

Pro získání nejmenšího společného násobku dvou čísel můžeme využít následující přepočet:

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

Příklad

Jaký je nejmenší společný násobek čísel 140 a 15?

$gcd(140,\\; 15) = 5$
$lcm(140,\\; 15) = {{140 \\cdot 15} \\over {gcd(140,\\; 15)}} = {{2100} \\over {5}} = 420$

Kód

/**
 * Vstup: Čísla a > 0, b > 0
 * Výstup: gcd(a, b)
 */
function gcd(a, b)
    if a >= b then
        m = a
        n = b
    else
        m = b
        n = a
 
    while n != 0 do
        m = p*n + z
        m = n
        n = z
 
    return m

/**
 * 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");
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

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

/**
 * 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;
}

/**
 * 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;
}

mgcd(X, X, X).
mgcd(X, Y, X) :- Y == 0.
mgcd(X, Y, R) :- Y > X, mgcd(Y, X, R).
mgcd(X, Y, R) :- X > Y, R1 is X mod Y, mgcd(Y,R1,R).

Výpočet

Rozklad na prvočísla

Příklad

Příklad

Euklidův algoritmus

Princip

Příklad

Příklad

Nejmenší společný násobek

Příklad

Kód

Doporučujeme