2

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.

katstart
  • 23
  • 2

4 Answers4

0

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

Peter LeFanu Lumsdaine
  • 9,434
  • Making the 1 visible as you stated helped fill in the missing gap my brain wasn't making. Thank you! – katstart Jan 23 '16 at 23:37
0

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.

Browning
  • 659
0

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

Piquito
  • 29,594
0

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.

Will Jagy
  • 139,541