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

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

Правило: Щоб знайти найбільший спільний дільник декількох натуральних чисел, потрібно:
1) розкласти дані числа на прості множники;
2) виписати ті спільні множники, які є в розкладі кожного із чисел,
3) знайти добуток цих множників.

Приклади:

а) Знайти НСД (6600; 6300):
6600 = 2 · 2 · 2 · 3 · 5 · 5 · 11,
6300 = 2 · 2 · 3 · 3 · 5 · 5 · 7,
НСД (6600; 6300) = 2 · 2 · 3 · 5 · 5 = 300;

б) Знайти НСД (34 398; 1260; 6552):
34 398 = 2 · 3 · 3 · 3 · 7 · 7 · 13,
1260 = 2 · 2 · 3 · 3 · 5 · 7,
6552 = 2 · 2 · 2 · 3 · 3 · 7 · 13,
НСД (34 398; 1260; 6552) = 2 · 3 · 3 · 7 = 126.

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

Приклад: Знайти НСД (270; 186). Поділимо 270 на 186 з остачею:

270 : 186 = 1 (ост. 84).

Потім поділимо дільник на остачу і т.д.:

186 : 84 = 2 (ост. 18),
84 : 18 = 4 (ост. 12),
18 : 12 = 1 (ост. 6),
12 : 6 = 2 (ост. 0).

Найбільшим спільним дільником чисел 270 і 186 є остання, відмінна від нуля остача, тобто число 6.

Приклад: Знайти НСД (234; 180).
1) 234 : 180 = 1 (ост. 54),
2) 180 : 54 = 3 (ост. 18),
3) 54 : 18 = 3 (ост. 0).
Значить, НСД (234; 180) = 18.

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

Приклади:

а) 75 і 14 - взаємно прості числа, оскільки НСД (75; 14) = 1;
б) 20, 9 і 77 взаємно прості числа, оскільки НСД (20; 9; 77) = 1.