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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Огляд[ред.ред. код]

Позначення[ред.ред. код]

Найбільший спільний дільник двох чисел 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)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Див. також[ред.ред. код]