Взаємно простими числами називаються числа, найбільший спільний дільник яких дорівнює 1.
Спільним дільником декількох натуральних чисел називається число, яке є дільником кожного з даних чисел. У разі якщо їх декілька, найбільший з них називається найбільшим спільним дільником (НСД).
Для знаходження найбільшого спільного дільника кількох чисел необхідно:
- записати канонічне розкладання даних чисел;
- перелічити всі загальні прості множники, що входять в канонічні розкладання кожного з даних чисел;
- звести кожне з перерахованих простих множників чисел в найменший ступінь, з якою цей простий множник входить в канонічні розкладання даних чисел.
Приклади розв'язання задач
Завдання. Знайти НОД чисел 2520 і 5940
Рішення. 1) Запишемо їх канонічний розклад
2) У цих двох чисел загальними будуть такі прості числа:;
3) Мінімальна ступінь двійки в канонічних розкладах - друга, для 3 теж друга, п'ятірка входить в обидва розкладання в першого ступеня.
Таким чином, НОД дорівнює: НСД (2530; 5940)
Відповідь. НСД (2530; 5940)
Знаходження НОД онлайн Розкладання чисел онлайн
Завдання. Серед перерахованих чисел вказати взаємно прості числа:
11 і 29; 84 і 715; 27 і 111
Рішення. У першій парі 11 і 29 кожне з чисел є простим числом. тому вони будуть взаємно простими. Для другої пари чисел 84 і 715 знайдемо НСД. Їх канонічні розкладання мають вигляд
В їх канонічних розкладах немає загальних множників, тому НСД (84; 715) = 1. і, отже, вони взаємно прості. Знайдемо тепер НСД для останньої пари чисел. Їх канонічні розкладання мають вигляд,, а НОД (27; 111) = 3. Числа 27 і 111 не є взаємно простими.