1
$\begingroup$

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!

  • 1
    $\: 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*.2012-04-04
  • 1
    The distributive law: $24-1(66-2\cdot 24) = 24 + (-1)66+(2)24 = (1+2)24+(-1)66=(3)24+(-1)66$.2012-04-04
  • 1
    For quickly checking your work: http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html2012-04-04
  • 1
    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.](http://math.stackexchange.com/a/85841/242)2012-04-04
  • 0
    Thanks guys this is makes since now!2012-04-04
  • 1
    See the [Euclidean algorithm in matrix form](http://en.wikipedia.org/wiki/Euclidean_algorithm#Matrix_method).2012-04-04

1 Answers 1

1

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*}$$