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

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

Огляд

Позначення

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

Приклад

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

$54\times 1=27\times 2=18\times 3=9\times 6.$

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

$1,2,3,6,9,18,27,54.$

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

$24\times 1=12\times 2=8\times 3=6\times 4.$

$1,2,3,4,6,8,12,24.$

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

$1,2,3,6.$

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

$(54,24)=6.$

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

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

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

Властивості

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

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

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

$a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}}$

$b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}$

Тоді

НСД$(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})}$

Приклад

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

$840=2^3\cdot 3\cdot 5\cdot 7$

$396=2^2\cdot 3^2\cdot 11$,

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

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

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

Отже,

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

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

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

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

Приклад

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

$f(x)=2x^3+6x^2+14x+10$

$g(x)=3x^2-3x-6$

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

$f(x)=2(x+1)(x^2+2x+5)$

$g(x)=3(x+1)(x-2)$,

отримуємо

НСД $(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;
}

Див. також

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

Джерела

• Шаблон:TAOCP.v2