Найбільший спільний дільник та найменше спільне кратне

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

Наприклад

НСД

Взаємно прості числа

Означення: Два натуральних числа називаються взаємно простими, якщо їхній НСД дорівнює одиниці.

Знаходження НСД за допомогою розкладання на прості множники

Щоб знайти НСД двох або кількох чисел, необхідно:

  1. Розкласти дані числа на прості множники.
  2. Скласти добуток зі спільних простих множників, взятих із найменшим показником степеня.
  3. Знайти значення добутку.

Алгоритм Евкліда

  1. Поділити на з остачею:
  2. Поділити дільник на :
  3. Поділити дільник на нову остачу :

Остання відмінна від нуля остача і є НСД.

Найменше спільне кратне (НСК)

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

Знаходження НСК двох натуральних чисел

Щоб знайти НСК двох або кількох чисел, необхідно:

HCK

Наприклад

НСК

Звязок між НСД і НСК двох чисел

HCД

Розділ:
Версії іншими мовами: