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

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

Огляд

Позначення

Найбільший спільний дільник двох чисел 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, тому,

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

Властивості

НСД є комутативною функцією: НСД(a, b)= НСД(b, a).
$1\leq$ НСД(a, b) $\leq \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;
}

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.