Перейти до вмісту

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Огляд

[ред. | ред. код]

Позначення

[ред. | ред. код]

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

Приклад

[ред. | ред. код]

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

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

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

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

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

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

[ред. | ред. код]

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

Властивості

[ред. | ред. код]
  • НСД є комутативною функцією: НСД(ab)= НСД(ba).
  • НСД(ab)
  • НСД(abcd) = НСД(НСД(ab), НСД(cd))
  • НСД(ab) =|ab|/НСК(ab), де НСК(ab) найменше спільне кратне чисел ab.

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

[ред. | ред. код]

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

Тоді

НСД

Приклад

[ред. | ред. код]

Визначимо НСД. Розклад на прості множники:

,

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

,

Отже,

НСД

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

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

[ред. | ред. код]

В кільці многочленів над довільним полем найбільшим спільним дільником многочленів і , принаймні один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени і Обчислити НСД можна розкладаючи многочлен на нескоротні множники. Можна застосувати також алгоритм Евкліда.

Приклад

[ред. | ред. код]

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

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

,

отримуємо

НСД .

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

[ред. | ред. код]

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

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]