Как найти s и t по алгоритму Евклида [закрыто]

Расширение алгоритма Евклида

Мы уже знаем, что для любых двух целых чисел a и b существуют целые числа s и t такие, что as + bt = gcd(a,b). Другими словами, gcd(a,b) представляет собой линейную комбинацию a и b. gcd(a,b) — наименьшая положительная комбинация двух целых чисел. Сами a и b выражаются тривиальными комбинациями: a = 1· + 0·b и b = 0·a + 1·b. Начиная с этих двух, расширение алгоритма Евклида находит s и t, существование которых до сих пор было установлено только формальным образом.

Запишите две линейные комбинации в столбец и примените один шаг алгоритма Евклида к левой части. Предполагая, что a = bp + r.Умножьте второе уравнение на p и вычтите его из первого уравнения: а = 1·а + 0·б б = 0·а + 1·б r = 1·a + (-p)·b

Примените ту же процедуру к последним двум уравнениям. Продолжайте в том же духе, пока алгоритм Евклида слева не остановится. Справа будет линейная комбинация, которую мы ищем. Давайте проверим это на примере: пусть a = 2322, b = 654. Я придерживаюсь обычного соглашения о решении линейных уравнений и опускаю все члены в линейной комбинации, кроме левой части и двух коэффициентов справа. Результаты помещаются в таблицу, где четвертый столбец равен p (от a = bp + r, которое меняется на каждом шаге. Умножьте три числа слева от p на p и вычтите их из чисел, стоящих непосредственно над ними. Запишите результаты на следующей строке.

int algoritmoeuclides(int a,int b)
if (a%b==0)
return b;
return algoritmoeuclides(b,a%b);
}


int main(array<System::String ^> ^args)
{
int a=525;
int b=231;
printf("%d",algoritmoeuclides(a,b));
getch();
}

пока это мой код, он работает отлично. Проблема в том, что когда я пытаюсь найти s и t. Я не знаю, как это найти, я искал на форумах, но не знаю, что лучше способ запрограммировать этот алгоритм, чтобы найти S и T. Я поместил все объяснения, чтобы дать вам, ребята, идею. ПД: Извините за мой английский, я не говорю по-английски. Любая идея будет оценена.