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!

$\endgroup$
6
  • 1
    $\begingroup$ $\: 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. $\endgroup$ – Bill Dubuque Apr 4 '12 at 20:29
  • 1
    $\begingroup$ The distributive law: $24-1(66-2\cdot 24) = 24 + (-1)66+(2)24 = (1+2)24+(-1)66=(3)24+(-1)66$. $\endgroup$ – Bill Cook Apr 4 '12 at 20:30
  • 1
    $\begingroup$ For quickly checking your work: math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html $\endgroup$ – Bill Cook Apr 4 '12 at 20:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Apr 4 '12 at 20:37
  • 1
    $\begingroup$ See the Euclidean algorithm in matrix form. $\endgroup$ – lhf Apr 4 '12 at 23:23
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.