Кратним числа називається таке число, яке саме ділиться на без залишку. Спільне кратне чисел і – це число, що є кратним для кожного з них.
До прикладу, числа 10 і 15 мають спільне кратне 180. Числа 150, 120, 90 – також є спільними кратними цих чисел. Серед всіх спільних кратних завжди є найменше, в даному випадку таким являється число 30. Це число називають найменшим спільним кратним (НОК) і позначають .
Щоб знайти найменше спільне кратне двох чисел, потрібно розкласти їх на прості множники. Після цього, необхідно вибрати всі прості множник що входять в обидві множини та перемножити їх між собою. На наступному кроці, отриманий результат необхідно також помножити на прості множники, числа , які не являються множниками числа та прості множникик числа , що не являються простими множниками числа . До прикладу, для чисел 441 та 350 даний процес виглядатиме наступним чином:
Не важко переконатись, що в якості обчислювальної процедури, даний алгоритм має ті ж недоліки, що і згадуваний в параграфі алгоритм пошуку найбільшого спільного дільника шляхом розкладання чисел на прості множники (міститься за посиланням «алгоритм Евкліда») – являється доволі складним та неефективним для великих чисел.
Другий спосіб знаходження найменшого спільного кратного заснований на зв’язку між НОК і НОД. Зазначимо, що цей зв’язок визначається наступною теоремою: найменше спільне кратне двох додатних цілих чисел і дорівнює добутку , поділеному на найбільший спільний дільник цих чисел:
Тобто задача знаходження НОК в такий спосіб, зводиться до задачі обчислення найбільшого спільного дільника, для рішення якої, як нам відомо, існує дуже ефективний алгоритм Евкліда.
Зауваження: доводити істенність формули (1) не має сенсу. Якщо придивитись на неї, і так стане все зрозуміло: добуток чисел і дорівнює добутку всіх множників, які беруть участь в розкладанні цих двох чисел. При цьому НСД двох чисел дорівнює добутку всіх простих множників, які одночасно присутні в розкладах на множники даних двох чисел.
Найменше спільне кратне двох чисел – приклад знаходження:
Використовуючи формулу (1), знайти найменше спільне кратне двох чисел 1432 і 41.
Виходячи з того, що за умовою, для рішення даної задачі необхідно використовувати формулу, яка пов’язує НОК і НОД, то, для початку, знайдемо найбільший спільний дільник заданих чисел. Отже, скориставшись алгоритмом Евкліда отримаємо:
Останній ненульовий залишок дорівнює 1, тому . Далі, знаходимо найменше спільне кратне: