Concrete Mathematics: Clarification on Euclidean algorithm

Question

Let $m$ and $n$ be two positive integers, then:

$$m'm + n'n = gcd(m, n)$$

We can rewrite this as:

$$\overline{r}r + \overline{m}m = gcd(r, m)$$

with $r = n - \lfloor n/m \rfloor m$. Inserting the value of $r$ in the above equation, we have:

$$\overline{r}\left(n - \Bigl\lfloor \frac{n}{m} \Bigr\rfloor m\right) + \overline{m}m = gcd(m, n)\\ \left(\overline{m} - \Bigl\lfloor \frac{n}{m} \Bigr\rfloor \overline{r}\right)m + \overline{r}n = gcd(m, n)$$

After that it gives an example.

For $m = 12$ and $n = 18$, this method results in:

$$6 = 0 \times 0 + 1 \times 6 = 1 \times 6 + 0 \times 12 = (-1) \times 12 + 1 \times 18$$

I do not understand how it arrives at $1\times6 + 0\times12$ from $0\times0 + 1\times6$. We know $gcd(12, 18) = 6$, so $6$ can be written as $gcd(0, 6) = 0 \times 0 + 1 \times 6$.

$$n' = 0, m' = 1 - \lfloor n/m \rfloor \times 0, m = 6$$

How can we calculate $n$? How did the text know that $n = 12$?

Answer 1

In the previous page it is mentioned that, we can calculate $m'$ and $n'$ recursively until $m \neq 0$. I missed the crucial point as I over read it.

Here's what is written

Euclid's algorithm also gives us more.: We can extend it so that it will compute integers $m'$ and $n'$ satisfying $$m'm + n'n = gcd(m, n).$$ Here's how. If $m = 0$, we simply take $m' = 0$ and $n' = 1$. Otherwise we let $r = n\ mod\ m$ and apply the method recursively with $r$ and $m$ in place of $m$ and $n$, computing $\overline{r}$ and $\overline{m}$ such that $$\overline{r}r + \overline{m}m = gcd(r, m).$$

So basically what it did was: $$ \square \times 12 + \square \times 18 = gcd(12, 18) = 6\\ \square \times 6 + \square \times 12 = 6\\ \square \times 0 + \square \times 6 = 6\\ 0 \times 0 + 1 \times 6 = 6\\ 1 \times 6 + 0 \times 12 = 6\\ -1 \times 12 + 1 \times 18 = 6\\ $$