Найменше спільне кратне двох натуральних чисел

Кратним числа називається таке число, яке саме ділиться на  без залишку. Спільне кратне чисел і – це число, що є кратним для кожного з них.

До прикладу, числа 10 і 15 мають спільне кратне 180. Числа 150, 120, 90 – також є спільними кратними цих чисел. Серед всіх спільних кратних завжди є найменше, в даному випадку таким являється число 30. Це число називають найменшим спільним кратним (НОК) і позначають .

Щоб знайти найменше спільне кратне двох чисел, потрібно розкласти їх на прості множники. Після цього, необхідно вибрати всі прості множник що входять в обидві множини та перемножити їх між собою. На наступному кроці, отриманий результат необхідно також помножити на прості множники, числа , які не являються множниками числа  та прості множникик числа , що не являються простими множниками числа . До прикладу, для чисел 441 та 350 даний процес виглядатиме наступним чином:

Не важко переконатись, що в якості обчислювальної процедури, даний алгоритм має ті ж недоліки, що і згадуваний в параграфі алгоритм пошуку найбільшого спільного дільника шляхом розкладання чисел на прості множники (міститься за посиланням «алгоритм Евкліда») – являється доволі складним та неефективним для великих чисел.

Другий спосіб знаходження найменшого спільного кратного заснований на зв’язку між НОК і НОД. Зазначимо, що цей зв’язок визначається наступною теоремою: найменше спільне кратне двох додатних цілих чисел  і  дорівнює добутку , поділеному на найбільший спільний дільник цих чисел:

Тобто задача знаходження НОК в такий спосіб, зводиться до задачі обчислення найбільшого спільного дільника, для рішення якої, як нам відомо, існує дуже ефективний алгоритм Евкліда.

Зауваження: доводити істенність формули (1) не має сенсу. Якщо придивитись на неї, і так стане все зрозуміло: добуток чисел  і  дорівнює добутку всіх множників, які беруть участь в розкладанні цих двох чисел. При цьому НСД двох чисел дорівнює добутку всіх простих множників, які одночасно присутні в розкладах на множники даних двох чисел.

Найменше спільне кратне двох чисел – приклад знаходження:

Використовуючи формулу (1), знайти найменше спільне кратне двох чисел 1432 і 41.

Виходячи з того, що за умовою, для рішення даної задачі необхідно використовувати формулу, яка пов’язує НОК і НОД, то, для початку, знайдемо найбільший спільний дільник заданих чисел. Отже, скориставшись алгоритмом Евкліда отримаємо:

Останній ненульовий залишок дорівнює 1, тому . Далі, знаходимо найменше спільне кратне:

Блок-схема алгоритму знаходження найменшого спільного кратного двох натуральних чисел:

Найменше спільне кратне блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*