Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних чисел — найбільше натуральне число, на яке ці числа діляться без остачі.
Огляд Редагувати
Позначення Редагувати
Найбільший спільний дільник двох чисел 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; }