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

Але багато натуральних чисел діляться націло ще й на інші натуральні числа.

Наприклад:

Число 12 ділиться на 1, 2, 3, 4, 6, 12;

Число 36 ділиться на 1, 2, 3, 4, 6, 12, 18, 36.

Числа, на які число ділиться націло (для 12 це 1, 2, 3, 4, 6 та 12) називаються дільниками числа. Дільник натурального числа a- це таке натуральне число, яке ділить це число aбез залишку. Натуральне число, яке має більше двох дільників, називається складовим. Зверніть увагу, що числа 12 та 36 мають спільні дільники. Це числа: 1, 2, 3, 4, 6, 12. Найбільший із дільників цих чисел – 12.

Загальний дільник двох даних чисел aі b- це число, на яке діляться без залишку обидва дані числа aі b. Загальний дільник кількох чисел (НД)- Це число, що служить дільником для кожного з них.

Найкоротший загальний дільник чисел aі bзаписують так:

приклад: НОД (12; 36) = 12.

Дільники чисел у записі рішення позначають великою літерою "Д".

Приклад:

НОД (7; 9) = 1

Числа 7 і 9 мають лише один спільний дільник – число 1. Такі числа називають взаємно простимичи сламі.

Взаємно прості числа- це натуральні числа, які мають лише один спільний дільник – число 1. Їх НОД дорівнює 1.

Найбільший загальний дільник (НДД), властивості.

Основна властивість: найбільший спільний дільник mі nділиться будь-який спільний дільник цих чисел. приклад: для чисел 12 та 18 найбільший загальний дільник дорівнює 6; він ділиться попри всі спільні дільники цих чисел: 1, 2, 3, 6.
Наслідок 1: безліч спільних дільників mі nзбігається з безліччю дільників НОД( m, n).
Наслідок 2: безліч загальних кратних mі nзбігається з безліччю кратних НОК ( m, n).

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

Найбільший спільний дільник чисел mі nможе бути визначений як найменший позитивний елемент множини всіх їх лінійних комбінацій:

і тому представимо у вигляді лінійної комбінації чисел mі n:

Це співвідношення називається співвідношенням Безу, а коефіцієнти uі v — коефіцієнтами Безу. Коефіцієнти Безу ефективно обчислюються розширеним алгоритмом Евкліда. Це твердження узагальнюється на набори натуральних чисел - його сенс у тому, що підгрупа групи, породжена набором, - циклічна і породжується одним елементом: НОД ( a 1 , a 2 , … , a n).

Обчислення найбільшого загального дільника (НДД).

Ефективними способами обчислення НОД двох чисел є алгоритм Евклідаі бінарнийалгоритм. Крім того, значення НОД ( m,n) можна легко обчислити, якщо відомо канонічне розкладання чисел mі nна прості множники:

де — різні прості числа, та й — неотрицательные цілі числа (вони може бути нулями, якщо відповідне просте відсутня розкладанні). Тоді НОД ( m,n) та НОК ( m,n) виражаються формулами:

Якщо чисел більше двох: , НОД перебуває за наступним алгоритмом:

— це і є шуканий НОД.

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

Розберемо покрокове обчислення найбільшого спільного дільника:

1. Розкласти дільники чисел на прості множники:

Обчислення зручно записувати за допомогою вертикальної межі. Зліва від риси спочатку записуємо ділене, праворуч - дільник. Далі у лівому стовпці записуємо значення приватних. Пояснимо одразу на прикладі. Розкладемо на прості множники числа 28 та 64.

2. Підкреслюємо однакові прості множники в обох числах:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Знаходимо добуток однакових простих множників і записуємо відповідь:

НОД (28; 64) = 2 . 2 = 4

Відповідь: НОД (28; 64) = 4

Оформити перебування НОД можна двома способами: у стовпчик (як робили вище) або «в рядок».

Перший спосіб запису НОД:

Знайти НОД 48 та 36.

НОД (48; 36) = 2 . 2 . 3 = 12

Другий спосіб запису НОД:

Тепер запишемо рішення пошуку НОД у рядок. Знайти НОД 10 та 15.

Д (10) = (1, 2, 5, 10)

Д (15) = (1, 3, 5, 15)

Д (10, 15) = (1, 5)

НОД – це найбільший спільний дільник.

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

визначити множники, загальні обох чисел;
знайти добуток загальних множників.

Приклад знаходження НОД:

Знайдемо НОД чисел 315 та 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Випишемо множники, спільні для обох чисел:

3. Знайдемо твір спільних множників:

НОД(315; 245) = 5 * 7 = 35.

Відповідь: НОД(315; 245) = 35.

Знаходження НОК

НОК – це найменше загальне кратне.

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

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

Приклад знаходження НОК:

Знайдемо НОК чисел 236 та 328:

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

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Випишемо множники, що входять до розкладання одного з чисел і допишемо до них множники, що не вистачають з розкладання другого числа:

2; 2; 59; 2; 41.

3. Знайдемо твір множників, що вийшли:

НОК(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Відповідь: НОК(236; 328) = 19352.

Для знаходження НОД (найбільшого спільного дільника) двох чисел необхідно:

2. Знайти (підкреслити) всі загальні прості множники отриманих розкладаннях.

3. Знайти добуток загальних простих множників.

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

1. Розкласти ці числа на прості множники.

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

3. Обчислити добуток отриманих множників.

Ознаки ділимості натуральних чисел.

Числа, що діляться без залишку на 2, називаютьсяпарними .

Числа, які не діляться без залишку на 2, називаютьсянепарними .

Ознака ділимості на 2

Якщо запис натурального числа закінчується парною цифрою, це число ділиться без залишку на 2, і якщо запис числа закінчується непарною цифрою, це число не ділиться без залишку на 2.

Наприклад, числа 60 , 30 8 , 8 4 діляться без залишку на 2, а числа 51 , 8 5 , 16 7 не діляться без залишку на 2.

Ознака ділимості на 3

Якщо сума цифр числа ділиться на 3, то число ділиться на 3; якщо сума цифр числа не ділиться на 3, то число не ділиться на 3.

Наприклад, з'ясуємо, чи ділиться на 3 число 2772825. Для цього підрахуємо суму цифр цього числа: 2+7+7+2+8+2+5 = 33 – ділиться на 3. Отже, число 2772825 ділиться на 3.

Ознака ділимості на 5

Якщо запис натурального числа закінчується цифрою 0 або 5, це число ділиться без залишку на 5. Якщо ж запис числа закінчується іншою цифрою, то число без залишку на 5 не ділиться.

Наприклад, числа 15 , 3 0 , 176 5 , 47530 0 діляться без залишку на 5, а числа 17 , 37 8 , 9 1 не діляться.

Ознака ділимості на 9

Якщо сума цифр числа ділиться на 9, то число ділиться на 9; якщо сума цифр числа не ділиться на 9, то число не ділиться на 9.

Наприклад, з'ясуємо, чи ділиться на 9 число 5402070. Для цього підрахуємо суму цифр цього числа: 5+4+0+2+0+7+0 = 16 – не ділиться на 9. Отже, число 5402070 не ділиться на 9.

Ознака ділимості на 10

Якщо запис натурального числа закінчується цифрою 0, це число ділиться без залишку на 10. Якщо запис натурального числа закінчується іншою цифрою, воно не ділиться без залишку на 10.

Наприклад, числа 40 , 17 0 , 1409 0 діляться без залишку на 10, а числа 17 , 9 3 , 1430 7 - Не діляться.

Правило знаходження найбільшого спільного дільника (НДД).

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

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

3) знайти добуток множників, що залишилися.

приклад. Знайдемо НОД (48; 36). Скористайтеся правилом.

1. Розкладемо числа 48 та 36 на прості множники.

48 = 2 · 2 · 2 · 2 · 3

36 = 2 · 2 · 3 · 3

2. З множників, що входять до розкладання числа 48, викреслимо ті, які не входять до розкладання числа 36.

48 = 2 · 2 · 2 · 2 · 3

Залишаються множники 2, 2 та 3.

3. Перемножимо множники, що залишилися, і отримаємо 12. Це число і є найбільшим загальним дільником чисел 48 і 36.

НОД (48; 36) = 2· 2 · 3 = 12.

Правило знаходження найменшого загального кратного (НОК).

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

1) розкласти їх у прості множники;

2) виписати множники, що входять до розкладання одного з чисел;

3) додати до них множники, що відсутні, з розкладів інших чисел;

4) знайти добуток множників, що вийшли.

приклад.Знайдемо НОК (75; 60). Скористайтеся правилом.

1. Розкладемо числа 75 та 60 на прості множники.

75 = 3 · 5 · 5

60 = 2 · 2 · 3 · 3

2. Випишемо множники, що входять до розкладання числа 75: 3, 5, 5.

НОК (75; 60) = 3 · 5 · 5 · …

3. Додамо до них множники, що відсутні, з розкладання числа 60, тобто. 2, 2.

НОК (75; 60) = 3 · 5 · 5 · 2 · 2

4. Знайдемо твір множників, що вийшли.

НОК (75; 60) = 3 · 5 · 5 · 2 · 2 = 300.

Найбільший спільний дільник та найменше загальне кратне – ключові арифметичні поняття, які дозволяють без зусиль оперувати звичайними дробами. НОК і найчастіше використовують для пошуку спільного знаменника кількох дробів.

Основні поняття

Дільник цілого числа X - це інше ціле число Y, яке X поділяється без залишку. Наприклад, дільник 4 - це 2, а 36 - 4, 6, 9. Кратне цілого X - це число Y, яке ділиться на X без залишку. Наприклад, 3 кратно 15, а 6 - 12.

Для будь-якої пари чисел ми можемо знайти їхні спільні дільники та кратні. Наприклад, для 6 і 9 загальним кратним є 18, а загальним дільником - 3. Очевидно, що дільників і кратних пар може бути кілька, тому при розрахунках використовується найбільший дільник НОД і найменше кратне НОК.

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

Знаходження НІД

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

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

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

Знаходження НОК

Найменше загальне кратне також визначається послідовним перебором або розкладанням на неподільні множники. Крім того, легко знайти НОК, якщо вже визначено найбільшого дільника. Для чисел X і Y НОК і НОД пов'язані наступним співвідношенням:

НОК (X, Y) = X × Y / НОД (X, Y).

Наприклад, якщо НОД(15,18) = 3, то НОК(15,18) = 15 × 18 / 3 = 90. Найбільш очевидний приклад використання НОК - пошук спільного знаменника, який є найменшим загальним кратним для заданих дробів.

Взаємно прості числа

Якщо в пари чисел немає спільних дільників, то така пара називається взаємно простою. НОД для таких пар завжди дорівнює одиниці, а виходячи із зв'язку дільників та кратних, НОК для взаємно простих дорівнює їхньому твору. Наприклад, числа 25 і 28 взаємно прості, адже вони немає спільних дільників, а НОК(25, 28) = 700, що їх твору. Два будь-які неподільні числа завжди будуть взаємно простими.

Калькулятор загального дільника та кратного

За допомогою нашого калькулятора ви можете визначити НОД і НОК для довільної кількості чисел на вибір. Завдання на обчислення загальних дільників та кратних зустрічаються в арифметиці 5, 6 класу, проте НОД та НОК – ключові поняття математики та використовуються в теорії чисел, планіметрії та комунікативної алгебри.

Приклади із реального життя

Загальний знаменник дробів

Найменше загальне кратне використовується для пошуку спільного знаменника кількох дробів. Нехай в арифметичній задачі потрібно підсумувати 5 дробів:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Для складання дробів вираз необхідно привести до спільного знаменника, що зводиться до завдання знаходження НОК. Для цього виберіть у калькуляторі 5 чисел та введіть значення знаменників у відповідні комірки. Програма обчислить НОК (8, 9, 12, 15, 18) = 360. Тепер необхідно обчислити додаткові множники кожного дробу, які визначаються як співвідношення НОК до знаменника. Таким чином, додаткові множники будуть виглядати як:

360/8 = 45
360/9 = 40
360/12 = 30
360/15 = 24
360/18 = 20.

Після цього множимо всі дроби на відповідний додатковий множник і отримуємо:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Такі дроби ми можемо легко підсумовувати та отримати результат у вигляді 159/360. Скорочуємо дріб на 3 і бачимо остаточну відповідь – 53/120.

Розв'язання лінійних діофантових рівнянь

Лінійні діофантові рівняння – це вирази виду ax + by = d. Якщо відношення d / НОД (a, b) є ціле число, то рівняння можна розв'язати в цілих числах. Давайте перевіримо пару рівнянь на можливість цілого рішення. Спочатку перевіримо рівняння 150x + 8y = 37. За допомогою калькулятора знаходимо НОД (150,8) = 2. Ділимо 37/2 = 18,5. Число не ціле, отже, рівняння не має цілих коренів.

Перевіримо рівняння 1320x + 1760y = 10120. Використовуємо калькулятор для знаходження НОД(1320, 1760) = 440. Розділимо 10120/440 = 23. У результаті отримуємо ціле число, отже, діофантово врівно.

Висновок

НОД і НОК відіграють велику роль у теорії чисел, а самі поняття широко використовуються в різних областях математики. Використовуйте наш калькулятор для розрахунку найбільших дільників та найменших кратних будь-якої кількості чисел.

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

Навігація на сторінці.

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

Зауважимо, що якби ми від початку звернулися до таблиці простих чисел , то з'ясували б, що числа 661 і 113 – прості, звідки можна було б відразу сказати, що й найбільший спільний дільник дорівнює 1 .

Відповідь:

НОД (661, 113) = 1 .

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

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

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

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

Розглянемо приклад знаходження НОД за озвученим правилом.

приклад.

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

Рішення.

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

Тобто, 72 = 2 · 2 · 2 · 3 · 3 і 96 = 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 , …, ak дорівнює числу 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.

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

приклад.

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

Рішення.

У цьому прикладі a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Спочатку за алгоритмом Евкліда визначимо найбільший спільний дільник d 2 перших двох чисел 78 і 294 . При розподілі отримуємо рівності 294 = 78 · 3 +60; 78 = 60 · 1 +18; 60 = 18 · 3 +6 і 18 = 6 · 3 . Таким чином, 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 .

Відповідь:

НОД (78, 294, 570, 36) = 6 .

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

приклад.

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

Рішення.

Розкладемо числа 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.