Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
$\: 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. –  Bill Dubuque 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. –  Bill Dubuque Apr 4 '12 at 20:37
    
Thanks guys this is makes since now! –  FireStorm Apr 4 '12 at 21:25

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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