Знаходження нод за алгоритмом евкліда та за допомогою розкладання на прості множники. Знаходження нок за допомогою розкладання чисел на прості множники Алгоритм Евкліда для знаходження НОД

Розглянемо два способи знаходження найбільшого загального дільника.

Знаходження шляхом розкладання на множники

Перший спосіб полягає у знаходженні найбільшого загального дільника шляхом розкладання даних чисел на прості множники.

Щоб знайти НОД кількох чисел, достатньо розкласти їх на прості множники і перемножити між собою ті з них, які є спільними для всіх даних чисел.

приклад 1.Знайдемо НОД (84, 90).

Розкладаємо числа 84 та 90 на прості множники:

Отже, ми наголосили на всіх загальних простих множниках, залишилося перемножити їх між собою: 1 · 2 · 3 = 6.

Таким чином, НОД (84, 90) = 6.

приклад 2.Знайдемо НОД (15, 28).

Розкладаємо 15 та 28 на прості множники:

Числа 15 і 28 є взаємно простими, оскільки найбільший спільний дільник - одиниця.

НОД (15, 28) = 1.

Алгоритм Евкліда

Другий спосіб (інакше його називають способом Евкліда) полягає у знаходженні НОД шляхом послідовного поділу.

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

Якщо більше двох даних чисел ділиться на менше, то число, яке менше і буде їх найбільшим спільним дільником.

приклад 1.Візьмемо два числа 27 і 9. Так як 27 ділиться на 9 і 9 ділиться на 9, значить, 9 є спільним дільником чисел 27 і 9. Цей дільник є в той же час найбільшим, тому що 9 не може ділитися на яке число, більше 9. Отже, НОД (27, 9) = 9.

В інших випадках, щоб знайти найбільший спільний дільник двох чисел, використовується наступний порядок дій:

1. З цих двох чисел більше число ділять на менше.
2. Потім, меншу кількість ділять на залишок, що вийшов від розподілу більшого числа на менше.
3. Далі перший залишок ділять на другий залишок, який вийшов від розподілу меншого числа на перший залишок.
4. Другий залишок ділять на третій, який вийшов від розподілу першого залишку на другий і т.д.
5. Таким чином розподіл продовжується доти, поки в залишку не вийде нуль. Останній дільник якраз і буде найбільшим спільним дільником.

приклад 2.Знайдемо найбільший спільний дільник чисел 140 та 96:

1) 140: 96 = 1 (залишок 44)

2) 96: 44 = 2 (залишок 8)

3) 44: 8 = 5 (залишок 4)

Останній дільник дорівнює 4 - це означає, що НОД (140, 96) = 4.

Послідовний поділ також можна записувати стовпчиком:

Щоб знайти найбільший спільний дільник трьох чи більше даних чисел, використовуємо наступний порядок дій:

1. Спершу знаходимо найбільший спільний дільник будь-яких двох чисел із кількох даних.
2. Потім знаходимо НОД знайденого дільника та якогось третього даного числа.
3. Потім знаходимо НОД останнього знайденого дільника та четвертого даного числа і таке інше.

Приклад 3.Знайдемо найбільший загальний дільник чисел 140, 96 та 48. НОД чисел 140 та 96 ми вже знайшли у попередньому прикладі (це число 4). Залишилося знайти найбільший спільний дільник числа 4 і третього цього числа - 48:

48 ділиться на 4 без залишку. Таким чином, НОД (140, 96, 48) = 4.

Подання числа у вигляді добутку простих чисел називається розкладання цього числа на прості множники.

Наприклад, запис 110 = 2 · 5 · 11 говорить про те, що число 110 розкладено на прості множники 2, 5 та 11.

Взагалі розкласти на прості множники можна будь-яке складове число причому при будь-якому способі виходить те саме розкладання, якщо не враховувати порядку множників. Тому уявлення числа 110 як твори 2 · 5 · 11 чи твір 5 · 2 · 11 є, сутнісно, ​​одне й теж розкладання числа 110 на прості множники.

Розкладаючи числа на прості множники, використовуючи ознаки розподілу на 2, 3, 5 та ін. Згадаймо спосіб запису розкладання числа на прості множники. Розкладемо, наприклад, на прості множники число 720. Число 720 ділиться на 2. Отже, 2 є один із простих множників у розкладанні числа 720. Розділимо 720 на 2. Число 2 пишеться праворуч від знака рівності, а приватне 360 – під числом 720. 360 ділимо на 2, отримуємо 180. Ділимо 180 на 2, отримуємо 90, ділимо 90 на 2, отримуємо 45, ділимо 45 на 3, отримуємо 15, ділимо 15 на 3, отримуємо 5. Число 5 просте, при розподілі його на 5 одержуємо 1. Розкладання на множники закінчено.

720 = 2 · 2 · 2 · 2 · 3 · 3 · 5

Добуток однакових множників прийнято замінити ступенем: 720 = · 5. Таке уявлення числа 720 називають канонічним виглядомцього числа.

Розкладання числа на прості множники використовується при знаходженні їхнього найбільшого спільного дільника та найменшого загального кратного.

Знайдемо, наприклад, найбільший спільний дільник та найменше загальне кратне чисел 3600 та 288.

Представимо кожне з цих чисел у канонічному вигляді.

3600 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 5 = · · ; 288 = 2 · 2 · 2 · 2 · 2 · 3 · 3 = ·

У розкладанні на прості множники найбільшого загального дільника чисел 3600 та 288 мають увійти все загальні прості множте,які у розкладах даних чисел, причому кожен із новачків потрібно взяти з найменшим показником,з яким він входить в обидва розкладання. Тому до розкладання найбільшого загального дільника чисел 3600 і 288 увійдуть множники і . Значить, D (3600? 288) = · = 144.

У розкладанні на прості множники найменшого загального кратного чисел 3600 та 288 повинні увійти усі прості множники, що містяться хоча б в одномуз розкладів чисел 3600 і 288 причому кожен із них потрібно взяти з найбільшим показником,що входять в обидва розкладання даних чисел. Тому до розкладання найменшого загального кратного чисел 3600 і 288 увійдуть множники , , 5. Значить,

К (3600, 288) = · · 5 = 7200.

Взагалі, щоб знайти найбільший спільний дільник даних чисел:

2) Утворимо добуток загальних для всіх даних чисел простих множників, причому кожен з них беремо з найменшим показником, з яким він входить у всі розкладання цих чисел;

3) Знаходимо значення цього твору – і буде найбільшим загальним дільником даних чисел.

Щоб знайти найменше загальне кратне даних чисел:

1) Представляємо кожне дане число у канонічному вигляді;

2) Утворимо твір з усіх простих множників, що перебувають у розкладаннях даних чисел, причому кожен беремо з найбільшим показником, з яким він входить у всі розкладання цих чисел;

3) Знаходимо значення цього твору – воно і буде найменшим загальним кратним даними чисел.

Білет № 45. Найменше загальне кратне число. Його властивості та способи знаходження. приклади.

Обчислення найменшого загального кратного (НОК) через НОД(найменший спільний дільник)

Один із способів знаходження найменшого загального кратного заснований на зв'язку між НОК та НОД. Існуючий зв'язок між НОК та НОД дозволяє обчислювати найменше загальне кратне двох цілих позитивних чисел через відомий найбільший спільний дільник. Відповідна формула має вигляд НОК (a, b) = a · b: НОД (a, b) . Розглянемо приклади знаходження НОК за наведеною формулою.

приклад.

Знайдіть найменше загальне кратне двох чисел 126 і 70 .

Рішення.

У цьому прикладі a=126, b=70. Скористаємося зв'язком НОК із НОД, що виражається формулою НОК (a, b) = a · b: НОД (a, b). Тобто, спочатку ми маємо знайти найбільший спільний дільник чисел 70 і 126 після чого ми зможемо обчислити НОК цих чисел за записаною формулою.

Знайдемо НОД(126, 70), використовуючи алгоритм Евкліда: 126 = 70 · 1 +56, 70 = 56 · 1 +14, 56 = 14 · 4, отже, НОД(126, 70) = 14.

Тепер знаходимо необхідне найменше загальне кратне: НОК(126, 70) = 126 · 70: НОД (126, 70) = 126 · 70: 14 = 630.

Відповідь:

НОК(126, 70) = 630.

приклад.

Чому одно НОК(68, 34)?

Рішення.

Так як 68 ділиться націло на 34 , то НОД(68, 34) = 34. Тепер обчислюємо найменше загальне кратне: НОК (68, 34) = 68 · 34: НОД (68, 34) = 68 · 34:34 = 68.

Відповідь:

НОК(68, 34) = 68.

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

Знаходження НОК за допомогою розкладання чисел на прості множники

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

Озвучене правило знаходження НОК випливає з рівності НОК (a, b) = a · b: НОД (a, b). Справді, добуток чисел aі bодно добутку всіх множників, що беруть участь у розкладах чисел aі b. В свою чергу НОД(a, b)дорівнює добутку всіх простих множників, одночасно присутніх у розкладах чисел aі b(Про що написано в розділі знаходження НОД за допомогою розкладання чисел на прості множники).

Наведемо приклад. Нехай ми знаємо, що 75 = 3 · 5 · 5і 210 = 2 · 3 · 5 · 7. Складемо твір із усіх множників даних розкладів: 2·3·3·5·5·5·7. Тепер із цього твору виключимо всі множники, присутні й у розкладанні числа 75 і в розкладанні числа 210 (такими множниками є 3 і 5 ), тоді твір набуде 2·3·5·5·7. Значення цього твору дорівнює найменшому загальному кратному чисел 75 і 210 , тобто, НОК (75, 210) = 2 · 3 · 5 · 5 · 7 = 1050.

приклад.

Розклавши числа 441 і 700 на прості множники, знайдіть найменше загальне кратне цих чисел.

Рішення.

Розкладемо числа 441 і 700 на прості множники:

Отримуємо 441 = 3 · 3 · 7 · 7і 700 = 2 · 2 · 5 · 5 · 7.

Тепер складемо твір із усіх множників, що беруть участь у розкладаннях даних чисел: 2·2·3·3·5·5·7·7·7. Виключимо з цього твору всі множники, що одночасно присутні в обох розкладаннях (такий множник тільки один – це число 7 ): 2·2·3·3·5·5·7·7. Таким чином, НОК (441, 700) = 2 · 2 · 3 · 3 · 5 · 5 · 7 · 7 = 44 100.

Відповідь:

НОК(441, 700) = 44100.

Правило знаходження НОК з використанням розкладання чисел на прості множники можна сформулювати трохи інакше. Якщо до множників з розкладання числа aдодати відсутні множники з розкладання числа b, то значення отриманого твору дорівнюватиме найменшому загальному кратному чисел aі b .

Наприклад візьмемо ті самі числа 75 і 210 , їх розкладання на прості множники такі: 75 = 3 · 5 · 5і 210 = 2 · 3 · 5 · 7. До множників 3 , 5 і 5 з розкладання числа 75 2 і 7 з розкладання числа 210 , отримуємо твір 2·3·5·5·7значення якого дорівнює НОК(75, 210).

приклад.

Знайдіть найменше загальне кратне чисел 84 і 648 .

Рішення.

Отримуємо спочатку розкладання чисел 84 і 648 на прості множники. Вони мають вигляд 84 = 2 · 2 · 3 · 7і 648 = 2 · 2 · 2 · 3 · 3 · 3 · 3. До множників 2 , 2 , 3 і 7 з розкладання числа 84 додаємо відсутні множники 2 , 3 , 3 і 3 з розкладання числа 648 , отримуємо твір 2·2·2·3·3·3·3·7, яке дорівнює 4 536 . Таким чином, шукане найменше загальне кратне чисел 84 і 648 одно 4 536 .

Відповідь:

НОК(84, 648) = 4536.

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

Yandex.RTB R-A-339285-1

Алгоритм Евкліда для знаходження НОД

Алгоритм Евкліда дозволяє легко вирахувати найбільший спільний дільник для двох позитивних чисел. Формулювання та доказ алгоритму Евкліда ми навели у розділі «Найбільший спільний дільник: визначник, приклади».

Суть алгоритму у тому, щоб послідовно проводити розподіл із залишком, під час якого виходить ряд рівностей виду:

a = b · q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Ми можемо закінчити поділ тоді, коли r k + 1 = 0, при цьому r k = НОД (a, b).

Приклад 1

64 і 48 .

Рішення

Введемо позначення: a = 64 b = 48 .

На основі алгоритму Евкліда проведемо поділ 64 на 48 .

Отримаємо 1 і залишок 16 . Виходить, що q 1 = 1 r 1 = 16 .

Другим кроком розділимо 48 на 16 , отримаємо 3 . Тобто q 2 = 3, а r 2 = 0.Таким чином, число 16 – це найбільший спільний дільник для чисел з умови.

Відповідь:НОД (64, 48) = 16 .

Приклад 2

Чому дорівнює НОД чисел 111 і 432 ?

Рішення

Ділимо 432 на 111 . Відповідно до алгоритму Евкліда отримуємо ланцюжок рівностей 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Таким чином, найбільший спільний дільник чисел 111 і 432 - Це 3 .

Відповідь:НОД (111, 432) = 3 .

Приклад 3

Знайдіть найбільший спільний дільник чисел 661 та 113 .

Рішення

Проведемо послідовно розподіл чисел і отримаємо НОД (661 , 113) = 1 . Це означає, що 661 та 113 – це взаємно прості числа. Ми могли б з'ясувати це до початку обчислень, якби звернулися до таблиці простих чисел.

Відповідь:НОД (661, 113) = 1 .

Знаходження НОД за допомогою розкладання чисел на прості множники

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

Приклад 4

Якщо ми розкладемо числа 220 та 600 на прості множники, то отримаємо два твори: 220 = 2 · 2 · 5 · 11і 600 = 2 · 2 · 2 · 3 · 5 · 5. Спільними у цих двох творах будуть множники 2, 2 та 5. Це означає, що НОД (220, 600) = 2 · 2 · 5 = 20.

Приклад 5

Знайдіть найбільший спільний дільник чисел 72 і 96 .

Рішення

Знайдемо всі прості множники чисел 72 і 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Спільними для двох чисел прості множники: 2, 2, 2 та 3. Це означає, що НОД (72, 96) = 2 · 2 · 2 · 3 = 24.

Відповідь:НОД (72, 96) = 24 .

Правило знаходження найбільшого загального дільника двох чисел ґрунтується на властивостях найбільшого загального дільника, згідно з яким НОД (m · a 1 , m · b 1) = m · НОД (a 1 , b 1) , де m – будь-яке ціле позитивне число.

Знаходження НОД трьох та більшої кількості чисел

Незалежно від кількості чисел, для яких нам потрібно знайти НОД, ми будемо діяти по тому самому алгоритму, який полягає в послідовному знаходженні НОД двох чисел. Заснований цей алгоритм на застосуванні наступної теореми: НОД кількох чисел a 1 , a 2 , … , a kдорівнює числу d k, яке знаходиться при послідовному обчисленні НОД (a 1 , a 2) = d 2, НОД (d 2 , a 3) = d 3 , НОД (d 3 , a 4) = d 4 , … , НОД (d k - 1 , a k) = d k .

Приклад 6

Знайдіть найбільший спільний дільник чотирьох чисел 78, 294, 570 і 36 .

Рішення

Введемо позначення: a 1 = 78 , a 2 = 294 , a 3 = 570 , a 4 = 36 .

Почнемо з того, що знайдемо НОД чисел 78 та 294: d 2 =НІД (78 , 294) = 6 .

Тепер приступимо до знаходження d 3 = НОД (d 2, a 3) = НОД (6, 570). Відповідно до алгоритму Евкліда 570 = 6 · 95 .Це означає що d 3 =НІД (6 , 570) = 6 .

Знайдемо d 4 = НОД (d 3 , a 4) = НОД (6 , 36). 36 ділиться на 6 без залишку. Це дозволяє нам отримати d 4 =НІД (6 , 36) = 6 .

d 4 = 6тобто НОД (78 , 294 , 570 , 36) = 6 .

Відповідь:

А тепер давайте розглянемо ще один спосіб обчислення НОД для тих та більшої кількості чисел. Ми можемо знайти НОД, перемноживши всі загальні прості множники чисел.

Приклад 7

Обчисліть НОД чисел 78, 294, 570 та 36 .

Рішення

Зробимо розкладання даних чисел на прості множники: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3 .

Для всіх чотирьох чисел загальними простими множниками будуть числа 2 та 3.

Виходить, що НОД (78, 294, 570, 36) = 2 · 3 = 6.

Відповідь:НОД (78, 294, 570, 36) = 6 .

Знаходження НОД негативних чисел

Якщо нам доводиться мати справу з негативними числами, то знаходження найбільшого загального дільника ми можемо скористатися модулями цих чисел. Ми можемо так вчинити, знаючи властивість чисел із протилежними знаками: числа nі - nмають однакові дільники.

Приклад 8

Знайдіть НОД негативних цілих чисел − 231 і − 140 .

Рішення

На виконання обчислень візьмемо модулі чисел, даних за умови. Це будуть числа 231 та 140 . Запишемо це коротко: НОД (− 231 , − 140) = НОД (231, 140). Тепер застосуємо алгоритм Евкліда для знаходження простих множників двох чисел: 231 = 140 · 1 + 91; 140 = 91 · 1 + 49; 91 = 49 · 1 + 42; 49 = 42 · 1 + 7 та 42 = 7 · 6. Отримуємо, що НОД (231, 140) = 7 .

А тому що НОД (− 231 , − 140) = НІД (231 , 140) , то НОД чисел − 231 і − 140 дорівнює 7 .

Відповідь:НОД (− 231 , − 140) = 7 .

Приклад 9

Визначте НОД трьох чисел − 585 , 81 та − 189 .

Рішення

Замінимо негативні числа у наведеному переліку на їх абсолютні величини, отримаємо НОД (− 585 , 81 , − 189) = НІД (585 , 81 , 189) . Потім розкладемо всі дані числа на прості множники: 585 = 3 · 3 · 5 · 13, 81 = 3 · 3 · 3 · 3 і 189 = 3 · 3 · 3 · 7. Спільними для трьох чисел є прості множники 3 та 3 . Виходить, що НОД (585 , 81 , 189) = НОД (− 585 , 81 , − 189) = 9 .

Відповідь:НОД (− 585 , 81 , − 189) = 9 .

Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter