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

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

позначення: НСД (А; В).

ПРИКЛАД. Знайдемо НОД чисел 4 і 6.

• Число 4 без залишку ділиться на: 1, 2 і 4.
• Число 6 без залишку ділиться на: 1, 2, 3 і 6.
• Найбільшим спільним дільником чисел 4 і 6 буде число 2.
• НСД (4; 6) \u003d 2

Це простий приклад. А як бути з великими числами, для яких треба відшукати НСД?

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

ПРИКЛАД. Знайдемо НОД чисел 81 і 45.

81 = 3 · 3 · 3 · 3 45 \u003d 3 · 3 · 5 НСД (81; 45) \u003d 3 · 3 = 9

У тих випадках, коли у двох чисел немає однакових простих множників, єдиним натуральним числом, на яке без остачі будуть ділитися такі числа буде 1. НОД таких чисел \u003d 1. Наприклад: НСД (7; 15) \u003d 1.

Що таке НОК

Число А називають кратним числу В, якщо А ділиться на В без залишку (остачі). Наприклад, 10 ділиться без остачі на 5, тому, 10 кратно 5; 11 не ділиться без остачі на 5, тому, 11 не кратне 5.

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

позначення: НОК (А; В).

Правило відшукання НОК:

• розкласти обидва числа на прості множники, відзначити однакові прості множники в обох розкладах, якщо такі є;
• твір всіх простих множників одного з чисел (власне, саме число) і всіх не зазначених множників іншого числа складуть НОК.

ПРИКЛАД. Знайдемо НОК чисел 81 і 45.

81 = 3 · 3 · 3 · 3 45 \u003d 3 · 3 · 5 НОК (81; 45) \u003d 81 · 5 \u003d 405

405 є найменшим кратним для чисел 81 і 45: 405/81 \u003d 5; 405/45 \u003d 9.

Якщо у двох чисел немає однакових простих множників, то НОК для таких чисел буде дорівнює добутку цих чисел.

14 \u003d 2 · 7 15 \u003d 3 · 5 НОК (14; 15) \u003d 14 · 15 \u003d 210

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

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

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

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

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

знаходження НОД

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для складання дробів вираз необхідно привести до спільного знаменника, що зводиться до задачі знаходження НОК. Для цього виберіть в калькуляторі 5 чисел і введіть значення знаменників у відповідні комірки. Програма вирахує НОК (8, 9, 12, 15, 18) \u003d 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 \u003d d. Якщо відношення d / НОД (a, b) є ціле число, то рівняння вирішується в цілих числах. Давайте перевіримо пару рівнянь на можливість цілочисельного рішення. Спочатку перевіримо рівняння 150x + 8y \u003d 37. За допомогою калькулятора знаходимо НСД (150,8) \u003d 2. Ділимо 37/2 \u003d 18,5. Число не ціле, отже, рівняння не має цілочисельних коренів.

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

висновок

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

Найбільший спільний дільник

визначення 2

Якщо натуральне число a ділиться на натуральне число $ b $, то $ b $ називають дільником числа $ a $, а число $ a $ називають кратним числа $ b $.

Нехай $ a $ і $ b $ -натуральна числа. Число $ c $ називають загальним дільником і для $ a $ і для $ b $.

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

$ НСД \\ (a; b) \\ або \\ D \\ (a; b) $

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

1. Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде шуканим найбільшим спільним дільником.

приклад 1

Знайти НОД чисел $ 121 $ і $ 132. $

$ 242 \u003d 2 \\ cdot 11 \\ cdot 11 $

$ 132 \u003d 2 \\ cdot 2 \\ cdot 3 \\ cdot 11 $

Вибрати числа, які входять в розкладання цих чисел

$ 242 \u003d 2 \\ cdot 11 \\ cdot 11 $

$ 132 \u003d 2 \\ cdot 2 \\ cdot 3 \\ cdot 11 $

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

$ НОД \u003d 2 \\ cdot 11 \u003d 22 $

приклад 2

Знайти НСД одночленним $ 63 $ і $ 81 $.

Будемо знаходити згідно з поданим алгоритмом. Для цього:

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

$ 63 \u003d 3 \\ cdot 3 \\ cdot 7 $

$ 81 \u003d 3 \\ cdot 3 \\ cdot 3 \\ cdot 3 $

Вибираємо числа, які входять в розкладання цих чисел

$ 63 \u003d 3 \\ cdot 3 \\ cdot 7 $

$ 81 \u003d 3 \\ cdot 3 \\ cdot 3 \\ cdot 3 $

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

$ НОД \u003d 3 \\ cdot 3 \u003d 9 $

Знайти НСД двох чисел можна і по-іншому, використовуючи безліч дільників чисел.

приклад 3

Знайти НОД чисел $ 48 $ і $ 60 $.

Рішення:

Знайдемо безліч дільників числа $ 48 $: $ \\ left \\ ((\\ rm 1,2,3.4.6,8,12,16,24,48) \\ right \\) $

Тепер знайдемо безліч дільників числа $ 60 $: $ \\ \\ left \\ ((\\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \\ right \\) $

Знайдемо перетин цих множин: $ \\ left \\ ((\\ rm 1,2,3,4,6,12) \\ right \\) $ - це безліч буде визначати безліч спільних дільників чисел $ 48 $ і $ 60 $. Найбільший елемент в даному безлічі буде число $ 12 $. Значить найбільший спільний дільник чисел $ 48 $ і $ 60 $ буде $ 12 $.

визначення НОК

визначення 3

Загальним кратним натуральних чисел $ A $ і $ b $ називається натуральне число, яке кратно і $ a $ і $ b $.

Спільними кратними чисел називаються числа які діляться на вихідні без остатка.Напрімер для чисел $ 25 $ і $ 50 $ загальними кратними будуть числа $ 50,100,150,200 $ і т.д

Найменше з загальних кратних буде називатися найменшим спільним кратним і позначається НОК $ (a; b) $ або K $ (a; b). $

Щоб знайти НСК двох чисел, необхідно:

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

приклад 4

Знайти НОК чисел $ 99 $ і $ 77 $.

Будемо знаходити згідно з поданим алгоритмом. Для цього

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

$ 99 \u003d 3 \\ cdot 3 \\ cdot 11 $

Виписати множники, що входять до складу першого

додати до них множники, які входять до складу другого і не ходять до складу першого

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

$ НОК \u003d 3 \\ cdot 3 \\ cdot 11 \\ cdot 7 \u003d 693 $

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

Твердження, на яких заснований алгоритм Евкліда:

Якщо $ a $ і $ b $ --натуральние числа, причому $ a \\ vdots b $, то $ D (a; b) \u003d b $

Якщо $ a $ і $ b $ --натуральние числа, такі що $ b

Користуючись $ D (a; b) \u003d D (a-b; b) $, можна послідовно зменшувати розглядаються числа до тих пір, поки не дійдемо до такої пари чисел, що одне з них ділиться на інше. Тоді менше з цих чисел і буде шуканим найбільшим спільним дільником для чисел $ a $ і $ b $.

Властивості НОД і НОК

1. Будь-яке спільне кратне чисел $ a $ і $ b $ ділиться на K $ (a; b) $
2. Якщо $ a \\ vdots b $, то До $ (a; b) \u003d a $

Якщо К $ (a; b) \u003d k $ і $ m $ -натуральне число, то До $ (am; bm) \u003d km $

Якщо $ d $ -загальний дільник для $ a $ і $ b $, то К ($ \\ frac (a) (d); \\ frac (b) (d) $) \u003d $ \\ \\ frac (k) (d) $

Якщо $ a \\ vdots c $ і $ b \\ vdots c $, то $ \\ frac (ab) (c) $ - спільне кратне чисел $ a $ і $ b $

Для будь-яких натуральних чисел $ a $ і $ b $ виконується рівність

$ D (a; b) \\ cdot К (a; b) \u003d ab $

Будь загальний дільник чисел $ a $ і $ b $ є дільником числа $ D (a; b) $

Найбільший спільний дільник

визначення 2

Якщо натуральне число a ділиться на натуральне число $ b $, то $ b $ називають дільником числа $ a $, а число $ a $ називають кратним числа $ b $.

Нехай $ a $ і $ b $ -натуральна числа. Число $ c $ називають загальним дільником і для $ a $ і для $ b $.

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

$ НСД \\ (a; b) \\ або \\ D \\ (a; b) $

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

1. Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде шуканим найбільшим спільним дільником.

приклад 1

Знайти НОД чисел $ 121 $ і $ 132. $

$ 242 \u003d 2 \\ cdot 11 \\ cdot 11 $

$ 132 \u003d 2 \\ cdot 2 \\ cdot 3 \\ cdot 11 $

Вибрати числа, які входять в розкладання цих чисел

$ 242 \u003d 2 \\ cdot 11 \\ cdot 11 $

$ 132 \u003d 2 \\ cdot 2 \\ cdot 3 \\ cdot 11 $

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

$ НОД \u003d 2 \\ cdot 11 \u003d 22 $

приклад 2

Знайти НСД одночленним $ 63 $ і $ 81 $.

Будемо знаходити згідно з поданим алгоритмом. Для цього:

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

$ 63 \u003d 3 \\ cdot 3 \\ cdot 7 $

$ 81 \u003d 3 \\ cdot 3 \\ cdot 3 \\ cdot 3 $

Вибираємо числа, які входять в розкладання цих чисел

$ 63 \u003d 3 \\ cdot 3 \\ cdot 7 $

$ 81 \u003d 3 \\ cdot 3 \\ cdot 3 \\ cdot 3 $

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

$ НОД \u003d 3 \\ cdot 3 \u003d 9 $

Знайти НСД двох чисел можна і по-іншому, використовуючи безліч дільників чисел.

приклад 3

Знайти НОД чисел $ 48 $ і $ 60 $.

Рішення:

Знайдемо безліч дільників числа $ 48 $: $ \\ left \\ ((\\ rm 1,2,3.4.6,8,12,16,24,48) \\ right \\) $

Тепер знайдемо безліч дільників числа $ 60 $: $ \\ \\ left \\ ((\\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \\ right \\) $

Знайдемо перетин цих множин: $ \\ left \\ ((\\ rm 1,2,3,4,6,12) \\ right \\) $ - це безліч буде визначати безліч спільних дільників чисел $ 48 $ і $ 60 $. Найбільший елемент в даному безлічі буде число $ 12 $. Значить найбільший спільний дільник чисел $ 48 $ і $ 60 $ буде $ 12 $.

визначення НОК

визначення 3

Загальним кратним натуральних чисел $ A $ і $ b $ називається натуральне число, яке кратно і $ a $ і $ b $.

Спільними кратними чисел називаються числа які діляться на вихідні без остатка.Напрімер для чисел $ 25 $ і $ 50 $ загальними кратними будуть числа $ 50,100,150,200 $ і т.д

Найменше з загальних кратних буде називатися найменшим спільним кратним і позначається НОК $ (a; b) $ або K $ (a; b). $

Щоб знайти НСК двох чисел, необхідно:

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

приклад 4

Знайти НОК чисел $ 99 $ і $ 77 $.

Будемо знаходити згідно з поданим алгоритмом. Для цього

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

$ 99 \u003d 3 \\ cdot 3 \\ cdot 11 $

Виписати множники, що входять до складу першого

додати до них множники, які входять до складу другого і не ходять до складу першого

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

$ НОК \u003d 3 \\ cdot 3 \\ cdot 11 \\ cdot 7 \u003d 693 $

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

Твердження, на яких заснований алгоритм Евкліда:

Якщо $ a $ і $ b $ --натуральние числа, причому $ a \\ vdots b $, то $ D (a; b) \u003d b $

Якщо $ a $ і $ b $ --натуральние числа, такі що $ b

Користуючись $ D (a; b) \u003d D (a-b; b) $, можна послідовно зменшувати розглядаються числа до тих пір, поки не дійдемо до такої пари чисел, що одне з них ділиться на інше. Тоді менше з цих чисел і буде шуканим найбільшим спільним дільником для чисел $ a $ і $ b $.

Властивості НОД і НОК

1. Будь-яке спільне кратне чисел $ a $ і $ b $ ділиться на K $ (a; b) $
2. Якщо $ a \\ vdots b $, то До $ (a; b) \u003d a $

Якщо К $ (a; b) \u003d k $ і $ m $ -натуральне число, то До $ (am; bm) \u003d km $

Якщо $ d $ -загальний дільник для $ a $ і $ b $, то К ($ \\ frac (a) (d); \\ frac (b) (d) $) \u003d $ \\ \\ frac (k) (d) $

Якщо $ a \\ vdots c $ і $ b \\ vdots c $, то $ \\ frac (ab) (c) $ - спільне кратне чисел $ a $ і $ b $

Для будь-яких натуральних чисел $ a $ і $ b $ виконується рівність

$ D (a; b) \\ cdot К (a; b) \u003d ab $

Будь загальний дільник чисел $ a $ і $ b $ є дільником числа $ D (a; b) $

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

Введіть числа: і
НОК:
НСД:

визначити

Просто введіть числа і отримаєте результат.

Як знайти НСК двох чисел

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

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

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

приклад

Для прикладу визначимо НОК чисел 8 і 22 .

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

2) Виділимо всі множники 8-ми, яких немає у 22-х:

8 = 2⋅2 ⋅2

3) Додамо виділені множники 8-ми до множників 22-х:

НОК (8; 22) \u003d 2 · 11 · 2 · 2

4) Обчислюємо НОК:

НОК (8; 22) \u003d 2 · 11 · 2 · 2 \u003d 88

Як знайти НСД двох чисел

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

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

приклад

Для прикладу визначимо НОД чисел 20 і 30 .

20 = 2 ⋅2⋅5

30 = 2 ⋅3⋅5

НСД (20,30) = 2⋅5 = 10