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

Огляд

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

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

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

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

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

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

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

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

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

Тоді НСД

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

,

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

,

Отже, НСД

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

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

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

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

,

отримуємо

НСД .

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

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

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

Джерела