2
$\begingroup$

I am studying for my NES mathematics endorsement exam and am working through a problem which deals with the Euclidean Algorithm to find the GCD of two relatively prime numbers. Then, I need to find some s such that 200s +567t = 1. The method I am using to find s is the "backwards" Euclidean Algorithm.

I need some help with understanding how the terms are being collected. In one tutorial, the gcd (175, 77) is found:

175 = 2(77) + 21  (a)
 77 = 3(21) + 14  (b)
 21 = 1(14) +  7  (c)
 14 = 2( 7) +  0

Starting with (c), we go backwards:

 7 =  21 - 1(14)
14 =  77 - 3(21)
21 = 175 - 2(77)

 7 =  21 - 1(14)
 7 =  21 - 1(77 - 3(21))           *plugging (b) into (c)
 7 = - 1(77)  +   4(21)            *collect terms
 7 = - 1(77)  +   4(175 - 2(77))   *plugging (a) in
 7 =   4(175) + (-9)(77)           *collecting terms again

The steps where they collect terms is where I am lost. I don't understand how the +4(21) comes to be when compared to the -9(77). I can figure out how the second collection comes to be with -1 + (-4)(2) = -9 but not the first. Is there an imaginary "1" at the front?

   7 =  1(21)  - 1(77 - 3(21))           *plugging (b) into (c)

So then it would be 1 + (-1)(-3)?

If I can figure this collection thing out, I should be able to finish working out the problem I was assigned on my own.

$\endgroup$
0
$\begingroup$

Given $ 7 = 21 - 1(77 - 3(21)) $
you want to know how to get $7 = - 1(77) + 4(21) $.
You are correct that we write $21$ as $1*21$.
Now when we distribute the $-1$, we get $$7 = 1*21 - 1*77 -1*(-3)*21=1*21 - 1*77 +3*21.$$
Collect like terms to get $7 = - 1(77) + 4(21) $.

We just used the distributive property $a*(b + c) = ab * ac$ twice: first with $a=-1$, $b=77$, and $c=-3(21)$, then again backwards with $a=21$, $b=1$, and $c= 3$.

Similarly, given $ 7 = - 1(77) + 4(175 - 2(77))$, start by distributing the $4$, then collect the terms with 77 in them.

$\endgroup$
  • $\begingroup$ Thank you!!! This made so much more sense seeing it all worked out step by step. $\endgroup$ – katstart Jan 23 '16 at 23:36
0
$\begingroup$

Yes, it’s exactly what you describe: there’s an invisible 1, and to collect the terms, you want to make it visible. The reason you can do this is because multiplying a number by 1 doesn’t change it — $21 = 1 \cdot 21$, and $77 = 1 \cdot 77$. So you can always replace $21$ by $1 \cdot 21$, and vice versa — you can always insert or remove a 1 without changing an expression (that is: a 1 multiplied by something). So going through the collecting-terms step in more detail:

\begin{align*} 21 - 1(77 - 3(21)) &= 1 \cdot 21 - 1 \cdot 77 + 3 \cdot 21 & \text{insert a 1; multiply out the brackets} \\ &= 1 \cdot 77 + (1 + 3) \cdot 21 &\text{collect like terms}\\ &= 77 + 4 \cdot 21 &\text{remove a 1; simplify $1+3$} \end{align*}

$\endgroup$
  • $\begingroup$ Making the 1 visible as you stated helped fill in the missing gap my brain wasn't making. Thank you! $\endgroup$ – katstart Jan 23 '16 at 23:37
0
$\begingroup$

$567=3^4\cdot7$ and $200=2^3\cdot5^2$ hence $(567,200)=1$.It is the necessary and sufficient condition for the equation $200s+567t=1$ have integer solutions (Bezout's theorem).You have by standard methods $s=-292-567k$ and $t=103+200k$ for k integer arbitrary.

$\endgroup$
0
$\begingroup$

This is about the simplest way, continued fraction for $567/200,$

$$ \begin{array}{cccccccccccccccccccccccccccccc} & & & 2 & & 1 & & 5 & & 16 & & 2 \\ \frac{0}{1} & & \frac{1}{0} & & \frac{2}{1} & & \frac{3}{1} & & \frac{17}{6} & & \frac{275}{97} & & \frac{567}{200} \end{array} $$ I think I have the spacing right now. Note the two fake convergents at the beginning, $0/1$ and $1/0.$ So $275 \cdot 200 - 567 \cdot 97 = \pm 1,$ and happens to be $+1$ this time.

$\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.