Чому дорівнює НСД ( 231; 273)=
У відповідь записати лише число.
Ваша відповідь:

Ответы

Ответ дал: adbestias

Відповідь: НСД ( 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).

Хай $r_{1}$ - остача від ділення b на r, а $r_{2}$ - остача від ділення r на $r_{1}$ .

Згідно леми, НСД (b;r) = НСД (r; $r_{1}$ ) і т.д.

Запишемо рівності, користуючись цими даними:

$a = bq + r, 0 < r < b$

$b = rq_{1} + r_{1}, 0 < r_{1} < r$

$r = r_{1}q_{2} + r_{2}, 0 < r_{2} < r_{1}$

$. ..$

Маємо: $b > r > r_{1} > r_{2} \geq 0$ . Тобто, остачі зменшуються і на якомусь кроці вона дорівнюватиме нулю. Тоді, хай $r_{n}$ - остання ненульова остача. Вона і буде шуканим НСД.