Найбільший спільний дільник

Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних чисел — найбільше натуральне число, на яке ці числа діляться без остачі.

Огляд

Позначення

Найбільший спільний дільник двох чисел a і b позначається як НСД(a, b), деколи (a, b). В англомовній літературі прийнято вживати позначення gcd(a, b).

Приклад

Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:

${\displaystyle 54\times 1=27\times 2=18\times 3=9\times 6.\,}$

Отже дільниками числа 54 є:

${\displaystyle 1,2,3,6,9,18,27,54.\,}$

Аналогічно дільниками числа 24 є:

${\displaystyle 24\times 1=12\times 2=8\times 3=6\times 4.\,}$

${\displaystyle 1,2,3,4,6,8,12,24.\,}$

Числа, які знаходяться в обох цих списках, є спільними дільниками чисел 54 та 24:

${\displaystyle 1,2,3,6.\,}$

Найбільшим серед них є число 6. Воно є найбільшим спільним дільником чисел 54 та 24. Можна записати:

${\displaystyle (54,24)=6.\,}$

Скорочення дробів

Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,

${\displaystyle {42 \over 56}={3\cdot 14 \over 4\cdot 14}={3 \over 4}.}$

Властивості

• НСД є комутативною функцією: НСД(a, b)= НСД(b, a).
• ${\displaystyle 1\leq }$ НСД(a, b) ${\displaystyle \leq \min(|a|,|b|)}$
• НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d))
• НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.

Обчислення НСД методом розкладу на прості множники

Нехай розклад чисел на прості множники має вигляд:

${\displaystyle a=2^{q_{2}}\cdot 3^{q_{3}}\cdot \dots \cdot p_{k}^{q_{p_{k}}}}$

${\displaystyle b=2^{r_{2}}\cdot 3^{r_{3}}\cdot \dots \cdot p_{k}^{r_{p_{k}}}}$

Тоді

НСД${\displaystyle (a,b)=2^{\min(q_{2};r_{2})}\cdot 3^{\min(q_{3};r_{3})}\cdot \dots \cdot p_{k}^{\min(q_{p_{k}};q_{p_{k}})}}$

Приклад

Визначимо НСД${\displaystyle (840,396)}$. Розклад на прості множники:

${\displaystyle 840=2^{3}\cdot 3\cdot 5\cdot 7}$

${\displaystyle 396=2^{2}\cdot 3^{2}\cdot 11}$,

або, подаючи для наочності нульові степені,

${\displaystyle 840=2^{3}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{0}}$

${\displaystyle 396=2^{2}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0}\cdot 11^{1}}$,

Отже,

НСД${\displaystyle (840,396)=2^{2}\cdot 3^{1}\cdot 5^{0}\cdot 7^{0}\cdot 11^{0}=12}$

Ефективним алгоритмом обчислення НСД є алгоритм Евкліда

НСД в кільці многочленів

В кільці многочленів ${\displaystyle K[X]}$ над довільним полем ${\displaystyle K}$ найбільшим спільним дільником многочленів ${\displaystyle f(x)}$ і ${\displaystyle g(x)}$, принаймні один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени ${\displaystyle f(x)}$ і ${\displaystyle g(x)}$ Обчислити НСД можна розкладаючи многочлен на нескоротні множники. Можна застосувати також алгоритм Евкліда.

Приклад

Обчислимо НСД двох многочленів над полем дійсних чисел:

${\displaystyle f(x)=2x^{3}+6x^{2}+14x+10}$

${\displaystyle g(x)=3x^{2}-3x-6}$

Розкладаючи многочлени на нескоротні множники

${\displaystyle f(x)=2(x+1)(x^{2}+2x+5)}$

${\displaystyle g(x)=3(x+1)(x-2)}$,

отримуємо

НСД ${\displaystyle (f(x),g(x))=x+1}$.

Приклади програмної реалізації знаходження НСД

Рекурсивна реалізація:

int gcd(int a, int b)
{
   if (b == 0) return a;
   return gcd(b, a % b);
}

Реалізація без використання рекурсії:

int gcd(int a, int b)
{
    if (a == 0) return b;
    while (b != 0)
    {
        if( a > b ){
            int r = a % b;
        } else {
            int r = b % a;
        }
        a = b;
        b = r;
    }
    return a;
}

Див. також

• Алгоритм Евкліда
• Найменше спільне кратне

Джерела

• Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)