НОД(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
4 votes Thanks 2
avion321321
Большое спасибо за решение, но, не могли бы сказать, как называется алгоритм, который вы использовали и почему он именно такой? Где можно почитать на тему "Линейное представление НОД?
DNHelper
Алгоритм вычисления НОД - это алгоритм Евклида. Можешь прогуглить это. Сам я знаю лишь то, что такое линейное представление НОД. Сам алгоритм вычисления представления я продумывал на ходу.
avion321321
А что такое линейное представление НОД
DNHelper
Это такая формула: НОД(A; B) = A*m + B*n, где A и B - числа, для которых находится НОД, а m и n - некие целые числа, чтобы выполнилось равенство. Найти линейное представление НОД - значит отыскать эти m и n.
Answers & Comments
Verified answer
Найдём НОД. Пусть 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