Як знайти найбільший спільний дільник (НСД) декількох цілих чисел?


Дільником цілого числа m називається будь-яке ціле число q, на яке m ділиться без залишку.

Спільним дільником декількох чисел називається таке число, яке є дільником кожного з них. Наприклад, числа 36, 60, 42 мають спільні дільники 2, 3 і 6.

Найбільший спільний дільник (НСД) для двох цілих чисел m і n – це найбільше із цілих чисел, на які m і n діляться без залишку. Наприклад: для чисел 70 і 105 найбільший спільний дільник дорівнює 35.

Для найбільшого спільного дільника чисел m і n застосовуються наступні математичні позначення:

  • НСД (m, n)
  • (M, n)
  • gcd (m, n) – від англ. Greatest Common Divisor.

Найбільший спільний дільник існує і однозначно визначений, якщо хоча б одне з чисел m або n відмінно від нуля.

Поняття найбільшого загального дільника природним чином узагальнюється на набори з більш ніж двох цілих чисел.

Щоб знайти найбільший спільний дільник (НСД) кількох чисел треба:

  1. Представити кожне число як добуток його простих множників, наприклад:
    360 = 2 · 2 · 2 · 3 · 3 · 5.
  2. Записати ступеня всіх простих множників:
    360 = 2 · 2 · 2 · 3 · 3 · 5 = 23 · 32 · 51.
  3. Виписати всі загальні дільники (множники) цих чисел.
  4. Вибрати найменшу ступінь кожного з них, що зустрілася у всіх творах.
  5. Перемножити ці ступені.

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

  1. Нехай m> n. Знайдемо залишок r від ділення m на n.
  2. Якщо r = 0 (тобто m ділиться на n), то НСД (m, n) = n.
  3. В іншому випадку замість чисел m і n треба взяти числа n і r і перейти до п. 1.
  4. Алгоритм завершується, коли черговий залишок від ділення виявиться дорівнює нулю.

Джерела:

  • ru.wikipedia.org – Вікіпедія: Найбільший спільний дільник
  • bymath.net – сайт «Вся елементарна математика», розділ «Загальний дільник. Найбільший спільний дільник »
  • ru.wikipedia.org – Вікіпедія: Алгоритм Евкліда

Додатково на Генон:

  • Що таке прості числа?
  • Що таке натуральне число?
  • Який ознака подільності числа на 3 і на 9?


Category: Наука та освіта

Comments (Прокоментуй!)

There are no comments yet. Why not be the first to speak your mind.

Leave a Reply