Предмет: Алгебра,
автор: avion321321
Найти линейное представления НОД(82295,58890)
Ответы
Автор ответа:
2
Найдём НОД. Пусть A = 82295, B = 58890
НОД(A; B) = НОД(A-B; B) = НОД(23405; 58890) = НОД(C; B) (пусть C = A - B)
НОД(C; B) = НОД(C; B-2C) = НОД(23405; 12080) = НОД(C; D) (D = B - 2C)
НОД(C; D) = НОД(C-D; D) = НОД(11325; 12080) = НОД(E; D) (E = C - D)
НОД(E; D) = НОД(E; D-E) = НОД(11325; 755) = 755
755 = D - E = B - 2C - C + D = B - 3C + B - 2C = 2B - 5(A - B) = 2B - 5A + 5B = -5A + 7B = -5 * 82295 + 7 * 82295
Ответ: 755 = -5 * 82295 + 7 * 82295
avion321321:
Большое спасибо за решение, но, не могли бы сказать, как называется алгоритм, который вы использовали и почему он именно такой? Где можно почитать на тему "Линейное представление НОД?
Алгоритм вычисления НОД - это алгоритм Евклида. Можешь прогуглить это. Сам я знаю лишь то, что такое линейное представление НОД. Сам алгоритм вычисления представления я продумывал на ходу.
А что такое линейное представление НОД
Это такая формула: НОД(A; B) = A*m + B*n, где A и B - числа, для которых находится НОД, а m и n - некие целые числа, чтобы выполнилось равенство. Найти линейное представление НОД - значит отыскать эти m и n.
Похожие вопросы
Предмет: Биология,
автор: mtovkalov3813
Предмет: Українська література,
автор: best4755
Предмет: Другие предметы,
автор: umerbaevtamerlan91
Предмет: Литература,
автор: Alex14561
Предмет: Математика,
автор: rudnina