Ответы
Відповідь: НСД ( 231; 273) = 21.
----------------------------------------------
Розв'язання:
*Найбільший спільний дільник (НСД) двох чисел - це найбільше число, на яке обидва числа діляться без остачі.
I спосіб:
Застосуємо алгоритм Евкліда до даних чисел:
273 = 231 * 1 + 42
231 = 42 * 5 + 21
42 = 21 *2 + 0
Отже, НСД ( 231; 273) = 21.
II спосіб:
1. Розкладемо на прості множники дані числа:
231 = 3 * 7 * 11;
273 = 3 * 7 * 13.
2. Виберемо однакові множники в числах: 3, 7
3. Знайдемо добуток знайдених множників: 3*7 = 21. Він і буде відповіддю.
Отже, НСД ( 231; 273) = 21.
---------------------------------------
Пояснення:
1. Як застосовувати алгоритм Евкліда?
Лема говорить, що якщо a = bq + r, де 0 < r < b, то НСД (a;b) = НСД (b;r).
Отже, знаходження НСД (a;b) зводиться до знаходження НСД (b;r).
Хай - остача від ділення b на r, а
- остача від ділення r на
.
Згідно леми, НСД (b;r) = НСД (r; ) і т.д.
Запишемо рівності, користуючись цими даними:
Маємо: . Тобто, остачі зменшуються і на якомусь кроці вона дорівнюватиме нулю. Тоді, хай
- остання ненульова остача. Вона і буде шуканим НСД.
2. Є загальний алгоритм для знаходження НСД, він описаний у другому способі.
-------------------------------------------------
Відповідь:21
Покрокове пояснення: