2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нахождение НОД.
Сообщение05.03.2024, 17:59 
Еще раз здравствуйте. Никак не приходит в голову как решать этого монстра.
НОД($2*6^{12} + 5$, $2*6^8 + 3$)

По-всякому раскладывал, но ничего не получилось. Вообще 0 идей, что с этим делать. Прошу вашей помощи.

 
 
 
 Re: Нахождение НОД.
Сообщение05.03.2024, 18:09 
Аватара пользователя
Попробуйте по мотивам алгоритма Евклида вычесть из одного числа другое с таким коэффициентом, чтобы разность получилась поменьше (по модулю). Потом еще пару раз.

 
 
 
 Re: Нахождение НОД.
Сообщение05.03.2024, 18:31 
mihaild в сообщении #1631911 писал(а):
Попробуйте по мотивам алгоритма Евклида вычесть из одного числа другое с таким коэффициентом, чтобы разность получилась поменьше (по модулю). Потом еще пару раз.

Я не совсем понимаю вашу идею. Не могли бы показать на конкретном примере?

 
 
 
 Re: Нахождение НОД.
Сообщение05.03.2024, 18:35 
Аватара пользователя
Воспользуйтесь следующим свойством: $\gcd(a, b) = \gcd(a - c\cdot b, b)$. Подберите подходящее $c$.
Полное решение приводить запрещено правилами форума, а это уже почти оно.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group