Implement Euclidean division to write greatest common divisor of two positive integers in terms of a linear combination of those integers

I'm trying to write a program that can write the greatest common divisor of two positive integers in terms of those integers. For example, let's say I have the numbers 353 and 15, I would find the gcd using the following steps:

353 = 23*15 + 8

15 = 1*8 + 7

8 = 1*7 + 1

7 = 7*1

so the gcd is 1. I have implemented this as:

//div_algo always takes int1 >= int2
int div_algo(int int1, int int2)
{   
    if (int2 == 0) //we are done
        return int1;
    int factor = 0;
    int remainder = 0;
    factor = int1/int2; //this is useful for linear combination
    remainder = int1 % int2;
    return div_algo(int2, remainder);
}

The problem is, if I want to find the linear combination, I basically work backwards. So, continuing with my example:

1 = 1*8 - 1*7 (substitute 7 = 15 - 1*8)

1 = 1*8 - 1*15 + 1*8 = 2*8 - 1*15 (substitute 8 = 353 - 23*15)

1 = 2*353 - 46*15 - 1*15 = 2*353 - 47*15

and there we go. The problem I am experiencing is that I don't know how to "store" the previous equations so that I can back substitute.