# Euclidean algorithm as a linear combination substitution and simplifying

This problem is from my discrete mathematics textbook.

I'm trying to find $\gcd(420,66)$

I compute \begin{align*} 420 &= 6 \times 66 + 24\\ 66 &= 2\times 24 + 18\\ 24 &= 1 \times 18 + 6\\ 18 &= 3 \times 6 + 0 \end{align*} then I rewrite the equation \begin{align*} 6 &= 24 - 1 \times 18\\ 18 &= 66 - 2 \times 24\\ 24 &= 420 - 6 \times 66\\ \end{align*}

Now I try to perform substitutions which give me \begin{align*} 6 &= 24 -1 \times 18\\ & = 24-1 (66 - 2 \times 24)\\ &= 3 \times 24 -66 \end{align*}

My question is how do you transition from $$24-1 (66 - 2 \times 24)$$ to $$3 \times 24 -66$$

I just can't wrap my head around this part. Maybe I'm way over thinking this step.

Any help is appreciated thanks!

-
 $\: y -1\:(x - 2\:y)\ =\ y -x + 2\:y\ =\ 3\:y - x.\$ Yours is the special case $\: y=24, x = 66.\:$ The law $a(b+c)\: =\ ab + ac$ is known as the distributive law. – Gone Apr 4 '12 at 20:29 The distributive law: $24-1(66-2\cdot 24) = 24 + (-1)66+(2)24 = (1+2)24+(-1)66=(3)24+(-1)66$. – Bill Cook Apr 4 '12 at 20:30 For quickly checking your work: math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html – Bill Cook Apr 4 '12 at 20:31 Back substitution is painful manually. Easier is to augment an idenity matrix to keep track of the elimination operations, just as in linear algebra. For a detailed work example see my answer here. – Gone Apr 4 '12 at 20:37 Thanks guys this is makes since now! – FireStorm Apr 4 '12 at 21:25
show 1 more comment

Distribute, reorder, associate: \begin{align*} 24 - 1(66-2\times 24) &= 24 -1(66) -1(-2\times 24)\\ &= 24 - 66 +2\times 24\\ &= 24 + 2\times 24 - 66\\ &= (1+2)24 - 66\\ &= 3\times 24 - 66. \end{align*}