Задача из теории чисел. Нужно доказать что НОД(115, 576) = 1.
Понимаю что нужно использовать алгоритм Евклида или разложение на простые множители, но что то запутался. Можете показать решение пошагово?
Через разложение на простые множители:
115 = 5 23
576 = 2^6 3^2 = 64 * 9
Общих простых множителей нет (у 115 это 5 и 23, у 576 это 2 и 3). Значит НОД = 1, числа взаимно просты.
Алгоритм Евклида:
576 = 115 * 5 + 1
115 = 1 * 115 + 0Последний ненулевой остаток = 1. Значит НОД(115, 576) = 1.
Если расписать подробнее:
Можно еще проще. 576 это степень двойки умноженная на степень тройки (2^6 * 3^2). А 115 нечетное и не делится на 3 (сумма цифр 1+1+5=7, не делится на 3). Значит общих делителей быть не может.
Спасибо! А можно еще через Евклида показать для полноты?