SBP-Program

получайте знания здесь

f

tw

in

Найдите наибольший общий делитель чисел 585 и 360

Найдите наибольший общий делитель чисел 585 и 360.

Алгоритм НОД

Для начала разложим числа 585 и 360 на множители, потом определим наибольший общий делитель чисел 585 и 360.

Как разложить число на множители можно посмотреть в статье Разложить на множители.

Найдем наибольший общий делитель 585 и 360.

Будем искать НОД по шагам (алгоритм нод).

1. Разложим на множители число 585:

585  5
117  3
 39  3
 13  13
  1 

Получаем разложение на множители числа 585:

585 = 3 * 3 * 5 * 13

Чтоб проверить правильность разложения 2178 на множители, надо перемножить полученные множители

3 * 3 * 5 * 13 = 585

Перемножение множителей дает исходное число. А это значит, что мы правильно разложили 585 на множители.

2. Разложим на множители число 360:

360  2 * 5
 36  3
 12  3
 4 2
 2 2
  1 

Получаем разложение на множители числа 360:

360 = 2 * 2 * 2 * 3 * 3 * 5

3. Какие множители являются общими в этих двух разложениях чисел на множители?

585 –> (3, 3, 5, 13)
360 –> (2, 2, 2, 3, 3, 5)
Совпадают (3, 3, 5)

4. Произведение совпадающих множителей и является наибольшим общим делителем чисел 585 и 360:

3 * 3 * 5 = 45

Ответ: НОД чисел 585 и 360 есть число 45:

НОД(585, 360) = 45

Кроме того, можно, используя алгоритм Евклида, найти нод чисел 585 и 360.