Why is it as a consequence of the Euclidean Algorithm that ?
I know we start off with . From here do we solve for and in terms of the previous remainders eventually solving for in terms of ?
If you are asking for the why of it, basically it's because of the division algorithm, and the fact that products and sums of integers are integers.
For an example, consider 45 and 63:
63 = 1 * 45 + 18
45 = 2 * 18 + 9
18 = 2 * 9 + 0
Thus (45, 63) = 9