Ответы
Відповідь:
Покрокове пояснення:
Означення 1.Найбільшим спільним дільником (далі НСД) двох цілих чисел a та b, які одночасно не дорівнюють нулю, називається таке найбільше ціле число d, на яке a та b діляться без остачі. Цей факт позначається так: d = НСД(a, b). Якщо обидва числа дорівнюють нулю, то покладемо НСД(0, 0) = 0.
Виходячи з означення, мають місце наступні співвідношення:
НОД(a, b) = НОД(b, a),
НОД(a, b) = НОД(-a, b)
НОД(a, 0) = |a|
Чому, наприклад, НСД(-12, 18) дорівнює 6, а не -6? Адже ж числа -12 та 18 діляться націло на 6 та на -6. Відповідь є простою: НСД – це найбільший спільний дільник, а число 6 більше за -6.
З поняттям найбільшого спільного дільника тісно пов’язане поняття найменшого спільного кратного.
Означення 2.Найменшим спільним кратним (далі НСК) двох цілих чисел a та b називається найменше додатне ціле число, кратне як a, так і b.
Основна теорема арифметики стверджує, що довільне натуральне число n можна подати у вигляді добутку простих чисел:
medv_gcd_02
Такий розклад натурального числа називається канонічним. З нього випливає, що якщо
medv_gcd_03
то
medv_gcd_04
Приклад 1. Розглянемо числа a = 24 та b = 18. Розкладемо їх на прості множники: 24 = 23·3, 18 = 2·32. Отже
НОД(24, 18) = 2min(3,1) · 3min(1,2) = 21 · 31 = 6,
НОК(24, 18) = 2max(3,1) · 3max(1,2) = 23 · 32 = 8 · 9 = 72
Як раз такий метод, базований на використанні канонічного розкладу чисел, ми вивчаємо у школі для знаходження НСД та НСК. Але цей метод не є ефективним для реалізації алгоритмів їх обчислення.
Розглянемо наступний очевидний факт. Якщо НСД(a, b) = d, то a та b діляться на d. Отже їх різниця a – b також ділиться на d. Має місце наступне рекурентне співвідношення для обчислення НСД:
medv_gcd_05
Приклад 2. Нехай a = 32, b = 12. Тоді
НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =
= НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4
Наведений метод обчислення також не є оптимальним. Наприклад, для знаходження НСД(1000000, 2) слід виконати 500000 операцій віднімання. Для прискорення обчислення НСД операцію віднімання замінимо операцією