Розглянемо спочатку спосіб, заснований на розкладанні даних чисел на прості множники.
Нехай дано два числа 3600 і 288. Уявімо їх у канонічному вигляді 3600 = 2 4 × 3 2 × 5 2, 288 = 2 5 × 3 2. Знайдемо найбільший спільний дільник даних чисел. У його розкладання повинні увійти всі загальні прості множники, які містяться в розкладах чисел 3600 і 288, причому кожен з них потрібно взяти з найменшим показником. з яким він входить в обидва розкладання. Отже, D (3600 288) = 2 4 × 3 2 = 144.
Взагалі, щоб знайти найбільший спільний дільник даних чисел:
1) представляють кожне дане число в канонічному вигляді;
2) утворюють твір загальних для всіх даних чисел простих множників, кожний з найменшим показником, яким він входить в усі розкладання даних чисел;
3) знаходять значення цього твору - воно і буде найбільшим загальним дільником даних чисел.
Знайдемо найменше спільне кратне чисел 3600 і 288. В його розкладання повинні увійти всі прості множники, які містяться хоча б в одному з розкладів чисел 3600 і 288, причому кожен з них потрібно взяти з найбільшим показником, з яким він входить в обидва розкладання. отже,
K (3600 288) = 2 5 × 3 2 × 5 = 7200.
Взагалі, щоб знайти найменше спільне кратне даних чисел:
1) представляють кожне дане число в канонічному вигляді;
2) утворюють твір всіх простих множників, що знаходяться в розкладах даних чисел, кожен з найбільшим показником, з яким він входить в усі розкладання даних чисел;
3) знаходять значення цього твору, воно і буде найменшим спільним кратним даних чисел.
Завдання 1. Знайти найбільший спільний дільник і найменше про-ний кратне чисел 60, 252 і 264.
Рішення. Уявімо кожне число в канонічному вигляді: 60 = 2 + 2 × 3 × 5, 252 = 2 + 2 × 3 2 × 7, 264 = 2 3 × 3 × 11.
Щоб знайти найбільший спільний дільник даних чисел, утворюємо твір загальних для всіх даних розкладів простих множників, кожний з найменшим показником, з яким він входить в усі рішення даних чисел: D (60,252,264) = 2 2 × 3 = 12.
Найменше спільне кратне чисел можна знайти, утворивши произве-дення всіх простих множників, що знаходяться в даних розкладах, кожен з найбільшим показником, з яким він входить в усі розклали-ня даних чисел, тобто K (60, 252, 264) = 2 3 × 3 2 × 5 × 7 × 11 = 27720.
Завдання 2. Знайти найбільший спільний дільник і найменше спільне кратне чисел 48 і 245.
Рішення. Уявімо кожне число в канонічному вигляді: 48 = 2 4 × 3, 245 = 5 × 7 2.
Так як розкладання даних чисел не містять загальних простих множників, то D (48, 245) = 1, а K (48, 245) = 48 × 245 = 10760.
Відшукання найбільшого загального дільника двох натуральних чисел по їх канонічного вигляду вимагає попереднього розкладання чисел на прості множники. Це нескладно зробити, якщо числа не великі, але для багатозначних чисел знайти їх канонічний розклад бував-ет важко. Існує спосіб відшукання найбільшого загального дільника, що вимагає лише ділення із залишком. Цей спосіб був запропонований Евклідом, і його називають алгоритмом Евкліда. Він заснований на наступних трьох твердженнях, доказ яких ми опускаємо:
1. Якщо а ділиться на b, то D (а, b) = b.
2. Якщо а = bq + r і r 3. Якщо а = bq + r і r Сформулюємо тепер алгоритм Евкліда для знаходження наиболь-шего загального дільника натуральних чисел а і b. Якщо а ділиться на b, то D (а, b) = b. Якщо при діленні а на b, виходить залишок r, то a = bq + r і D (а, b) = D (b, r) і завдання звелася до відшукання найбільшого загального дільника чисел b і r. Якщо b ділиться на r, то D (b, r) = r і тоді D (а, b) = r. Якщо при розподілі b на r виходить залишок r. то b = rq1 + r1 і тому D (r, r1) = D (b, r) = D (а, b). Продовжуючи описаний процес, одержуємо все менші і менші залишки. Зрештою отримаємо залишок, на який буде ділитися попередній залишок. Цей найменший, відмінний від нуля, залишок і буде найбільшим загальним дільником чисел а і А. Знайдемо за допомогою алгоритму Евкліда найбільший спільний поділи-тель чисел 2585 і 7975. Процес послідовного розподілу будемо записувати так: 7755 3 975 = 2585 3 + 220. 220 11 2585 = 220 × 11 + 165 165 1 220 = 165 × 1 + 55