✖

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

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

Для прикладу візьмімо числа 24 і 32. Який їхній найбільший спільний дільник? Передусім шукаємо число, яке ділить обидва числа.

  • Наприклад, число 12 ділить число 24, але не ділить число 32, бо 32 : 12 дорівнює 2,666…, а це не ціле число. Отже, число 12 не може бути найбільшим спільним дільником чисел 24 і 32.
  • А що скажеш про число 4? Воно ділить обидва числа: 24 : 4 дорівнює 6, а 32 : 4 дорівнює 8. Число 4 — наш перший кандидат. Чи немає більшого числа, яке ділило б обидва числа?
  • Число 8 ділить і число 24, і число 32, до того ж воно більше за 4.
  • Жодного іншого числа, більшого за 8, яке ділило б обидва числа, не існує. Отже, число 8 — найбільший спільний дільник чисел 24 і 32.

Алгоритм Евкліда для знаходження найбільшого спільного дільника

Існує досить простий спосіб знайти найбільший спільний дільник двох чисел — алгоритм Евкліда. Нехай на початку маємо два числа x і y, для яких хочемо знайти НСД. Для прикладу спробуймо на числах x = 50 і y = 35. Далі діємо так:

  1. Ділимо x : y і запам'ятовуємо остачу. Позначимо її z. У нашому прикладі маємо 50 : 35, що дає остачу z = 15.
  2. Тепер переставляємо змінні: у змінну x записуємо значення y, а в y записуємо значення z. Початкове значення x відкидаємо. Після цього кроку маємо x = 35 і y = 15.
  3. Тепер дивимося, чи y дорівнює нулю. Якщо так, то НСД — це число x. Оскільки y не дорівнює нулю, продовжуємо й повторюємо весь процес спочатку, з першого пункту.
  4. Знову ділимо x : y, тобто 35 : 15, що дає остачу z = 5.
  5. Переставляємо змінні, тож маємо x = 15 і y = 5. Оскільки y не дорівнює нулю, продовжуємо.
  6. Ділимо x : y, тобто 15 : 5. Остача z = 0.
  7. Переставляємо змінні й отримуємо x = 5 і y = 0.
  8. Тепер y = 0, і наш алгоритм закінчується. Найбільший спільний дільник — число x = 5.

Важливо, що порядок чисел не має значення. Якби ми поміняли числа з прикладу місцями, отримали б пару x = 35 і y = 50. Процес був би таким самим:

  1. Ділимо x : y, тобто 35 : 50, що дає остачу z = 35.
  2. Переставляємо змінні: x = 50 і y = 35.
  3. Бачимо, що після цього кроку ми лише поміняли місцями вміст змінних x і y…