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
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 a B. Algoritmus v každém svém kroku vydělí se zbytkem číslo A číslem B. Pokud zbytek není nulový, tak do A přiřadí číslo B a zbytek po dělení přiřadí do uvolněné proměnné B a celý postup opakuje.

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

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







Doporučujeme