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.

$\displaystyle n = q_{1}a + r_{1}$

$\displaystyle a = q_{2}r_{1} + r_{2}$

$\displaystyle r_{1} = q_{3}r_{2} + r_{3}$

.

.

.

$\displaystyle r_{m-2} = q_{m}r_{m-1} + r_{m}$

$\displaystyle r_{m-1} = q_{m+1}r_{m}$

Secondly( and this is where the problem starts) al the remainders up to $\displaystyle r_{m-1}$ are eliminated from all but the last of the equation from the above step to obtain an equation of the form $\displaystyle ab = kn + 1$ with $\displaystyle b$ in $\displaystyle Z_{n}$

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 $\displaystyle c_{j+2} = q_{j+1}c_{j+1} + c_{j}$ 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.