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

математична функція

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

Огляд ред.

Позначення ред.

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

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