Найбільший спільний дільник (НСД)

1.

Найбільший
спільний
дільник (НСД)

2.

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

3.

Алгоритм знаходження НСД.
1. Розкласти кожне с даних чисел на
прості множники.
2. Позначити у розкладаннях однакові
множники.
3. Знайти добуток
позначених множників
(беручи їх тільки з одного
розкладання).

4.

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

5.

Знайти НСД (72, 108) .
72
36
18
9
3
1
2
2
2
3
3
108
54
27
9
3
1
2
2
3
3
3
НСД (72, 108) =
2 · 2 · 3 · 3 = 36

6.

Знайти НСД (15, 22)
15 3
5 5
1
22 2
11 11
1
НСД (15, 22) = 1
Натуральні числа,
найбільший спільний дільник
яких дорівнює 1, називають
взаємно простими.

7.

До готелю завезли 84 ліжка та 56 шаф,
які порівну розподілили по кімнатам.
Скільки кімнат у готелі, якщо відомо, що
їх більше ніж 25?
Кількість кімнат = НСД (84, 56)
84 2
42 2
21 3
7 7
1
56 2
28 2
14 2
7 7
1
НСД (84, 56) = 2 · 2 · 7
= 28
Відповідь: у готелі 28 кімнат.

8.

Дякую за увагу !