Найти линейное представления НОД(82295,58890)

Question

Найти линейное представления НОД(82295,58890)

Answer 1

Найдём НОД. Пусть 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

Comments

Большое спасибо за решение, но, не могли бы сказать, как называется алгоритм, который вы использовали и почему он именно такой? Где можно почитать на тему "Линейное представление НОД?

---

Алгоритм вычисления НОД - это алгоритм Евклида. Можешь прогуглить это. Сам я знаю лишь то, что такое линейное представление НОД. Сам алгоритм вычисления представления я продумывал на ходу.

---

А что такое линейное представление НОД

---

Это такая формула: НОД(A; B) = A*m + B*n, где A и B - числа, для которых находится НОД, а m и n - некие целые числа, чтобы выполнилось равенство. Найти линейное представление НОД - значит отыскать эти m и n.