I'm trying to understand this implementation of Euclid Algorithm.
First as usual the division algorithm is applied to n and a. Then repeatedly to pairs of remainders until the remainder 0 occurs.
Secondly( and this is where the problem starts) al the remainders up to are eliminated from all but the last of the equation from the above step to obtain an equation of the form with in
Firstly I don't understand where the idea of eliminating the remainders comes from and what purpose it is serving here. At this point my understanding was to express the final equation in terms multiples of the values n and a using the equations obtained from the first step.
The method the implementation uses to eliminate the remainders is by multiplication by a suitable constant.
It is said the constant must satisfy why is this? How can the remainders be eliminated through multiplication?
I'm very confused about what the implementation is doing here and how it is doing it.