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

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

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

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

Читати повністю

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

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

Серед дільників чисел і  можуть бути однакові, тобто спільні дільники. Очевидно, їх кількість так само є скінченною. Наприклад, числа 30 і 70 мають чотири спільних дільники: 1, 2, 5 і 10. Серед цих дільників є найбільший (в даному випадку 10), його називають найбільшим спільним дільником (НСД) і позначають .

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

Читати повністю