Отримання знань

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

 

 

Число 28 має такі дільники: 1, 2, 4, 7, 14, 28.  Дільниками числа 42 є числа 1, 2, 3, 6, 7, 14, 21, 42.  Черво­ним кольором виділено числа  1,  2, 7, 14, які є спільними дільниками чисел 28 і 42. Серед спільних дільників число 14 є найбільшим.

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

 

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

 

 Найбільший спільний дільник чисел а і b позначають так: НСД (а; b). Отже, НСД(28; 42) = 14.

 Неважко встановити, наприклад, що 

 НСД (10; 25) = 5,

 НСД (18; 24) = 6, 

 НСД (7; 12) = 1.

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

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

210 = 2 · 3 · 5 · 7;    294 = 2 · 3 · 7 · 7. Підкреслимо всі спільні прості множники в розкладах даних чисел: 2, 3, 7. Числа 210 і 294 діляться на кожне із чисел 2, 3, 7 і на їх добуток:  2 · 3 · 7 = 42. Число 42 є найбільшим спільним дільником чисел 210 і 294: НСД(210; 294) = 42.

 

Приклад 1

 Знайти НСД (180; 840).

Розв’язання

 Скористав­шись схемою розкладання числа на прості множники, отримаємо:

180 =  2 · 2 · 3 · 3 · 5;

 840 =  2 · 2 · 2 · 3 · 5 · 7.

Як бачимо, у розкладі даних чисел деякі прості множни­ки повторюються. Наприклад, число 2 у першому розкладі зустрічається двічі, а в другому — тричі. Проте зрозуміло, що спільним дільником даних чисел буде число 2 · 2, а не число 2 · 2 · 2. Аналогічні міркування стосуються і множ­ника 3.

Отже, числа 180 і 840 діляться націло на кожне з чисел 2 · 2, 3, 5. Вони також діляться націло й на їх добуток 2 · 2 · 3 · 5. Таким чином,

НСД (180; 840) = 2 · 2 · 3 · 5 = 60.

Відповідь. НСД (180; 840) = 60.

 

Якщо розклад чисел 180 і 840 на прості множники записати у вигляді добутку степенів:

    180 = 2² · 3² · 5¹;

     840 = 2³ · 3¹ · 5¹ · 7¹  

 то НСД зручно знайти за таким правилом.

1)      Визначити степені, основи яких є спільними прости­ми дільниками даних чисел (у розглядуваному прикладі це основи 2, 3, 5).

2)   З кожної пари степенів з однаковими основами вибра­ти степінь з меншим показником (у розглядуваному при­кладі це 2², 3¹, 5¹).

3)   Перемножити вибрані степені.

Отриманий добуток є шуканим найбільшим спільним дільником (у наведеному прикладі НСД (180; 840) = 2² · 3¹ · 5¹).

  Розглянемо ще один приклад. 

  Приклад 2 

  Знайти НСД (585; 616).

  Розв’язання

  Маємо: 

             585 = 3² · 5 · 13;

             616 = 2³ · 7 · 11.

Бачимо, що числа 585 і 616 не мають спільних простих дільників. їх найбільший спільний дільник дорівнює 1, тоб­то НСД (585; 616) = 1.

Відповідь. НСД (585; 616)= 1.

 

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

Числа 585 і 616 взаємно прості.

Зазначимо, що будь-які два простих числа є взаємно простими. 

Наприклад, НСД (17; 43) = 1, НСД (101; 919) = 1.

  Приклад 3.

  Знайдіть НСД (250; 3000).

  Розв’язання

У цьому випадку немає потреби розкладати числа на прості множники. Число 250 — дільник числа 3000. Тому НСД (250; 3000) = 250.

Відповідь. НСД (250; 3000) = 250.

Взагалі, якщо число а — дільник числа b, то НСД (а; b) = а.

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

  Приклад 4

  Знайдіть НСД (132; 180; 144).

 Розв’язання

    Маємо: 

132 2 66 2 33 3 11 11 1

1800 2 90 2 45 3 15 3 5 5 1

144 2  72 2  36 2  18 2    9 3    3 3    1

 

 

132 = 2² · 3 ·11;        180 = 2² · 3² · 5;                 144 = 2⁴ · 3²

 Отже, НСД (132; 180; 144) = 2² · 3 = 12.

Відповідь. НСД (132; 180; 144) = 12.

Задача Яку найбільшу кількість однакових букетів можна скласти із 24 волошок і 32 ромашок, використавши всі квіти?

Розв’язання

З даних квітів можна, наприклад, скласти 2 букети, у кожному з яких буде 12 волошок і 16 ромашок.

Не можна скласти три букети, бо 32 ромашки не можна розділити на 3 однакові частини.

Можна скласти чотири однакові букети, бо і 24 волошки, і 32 ромашки можна розділити на 4 однакові частини.

Очевидно, що для розв’язання задачі потрібно знайти найбільше число, на яке можна розділити 24 волошки і 32 ромашки, тобто знайти найбільший      спільний дільник чисел 24 і 32. 

Оскільки НСД(24; 32) = 8, то найбільше можна скласти 8 однакових букетів. Кожний такий букет складатиметься із 24 : 8 = 3 волошок і 32 : 8 = 4    ромашок. 

Відповідь. 8 букетів

А тепер перевір свої знання. Виконай завдання: