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

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