-1
$\begingroup$

This question already has an answer here:

Is it possible to solve this by hand? Without using the Extended Euclidean Algorithm

We do the Euclidean algorithm and we get:

720 = 231 * 3 + 27

231 = 27 * 8 + 15

27 = 15 * 1 + 12

15 = 12 * 1 + 3

12 = 3 * 4 + 0

The GCD is 3.

We now isolate the remainders:

27 = 720 - 231 * 3

15 = 231 - 27 * 8

12 = 27 - 15 * 1

3 = 15 - 12 * 1

We proceed by substitution:

3 = 15 - 12 * 1

What now? How can we proceed when we have *1? There is no substitution possible?

Help! Thanks!

$\endgroup$

marked as duplicate by Jyrki Lahtonen, Lord Shark the Unknown, Key Flex, Brahadeesh, Namaste Oct 14 '18 at 9:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $3=15-12\times1=15-(27-15)=2\times 15-27=2\times(231-8\times 27)-27$ etc. But using back-substitution is a really horrible way to do it. $\endgroup$ – Lord Shark the Unknown Oct 12 '18 at 4:55
  • $\begingroup$ Sorry for the stupid question, but how did you get the "two times" [2 *] 15 - 27 ? $\endgroup$ – Elstovenski Oct 12 '18 at 5:04
  • $\begingroup$ $15-(27-15)=15-27+15$ etc... $\endgroup$ – Lord Shark the Unknown Oct 12 '18 at 5:05
  • $\begingroup$ So now should I go about continuing to back substitute or rather simplify? $\endgroup$ – Elstovenski Oct 12 '18 at 5:14
  • $\begingroup$ 2(15)-(15*1+12) Like this? $\endgroup$ – Elstovenski Oct 12 '18 at 5:16
3
$\begingroup$

The way I teach my students to do this is to do elementary row operations to an identity matrix augmented with a column consisting of the numbers we want to calculate the gcd of. This is received well because students have grown to like elementary row operations (they took linear algebra in the previous semester). The catch is that only integer multipliers are allowed in this game. Anyway, calculating the gcd this way automatically keeps track of the back substitutions. Behold.

Start with $$ \left(\begin{array}{ccc} 1&0&720\\ 0&1&231\end{array}\right) $$ Subtract the second row multiplied by three from the first row (as per $720=3\cdot 231+27$) $$ \left(\begin{array}{ccc} 1&-3&27\\ 0&1&231\end{array}\right). $$ Next we use $231=8\cdot27+15$ so subtract the first row multiplied by $8$ from the second $$ \left(\begin{array}{ccc} 1&-3&27\\ -8&25&15\end{array}\right). $$ Next use $27=1\cdot15+12$, so subtract the second from the first $$ \left(\begin{array}{ccc} 9&-28&12\\ -8&25&15\end{array}\right). $$ Next $15=1\cdot12+3$ so subtract the first from the second $$ \left(\begin{array}{ccc} 9&-28&12\\ -17&53&3\end{array}\right). $$ Let's look at the last column. We already see that the gcd will be $3$ because the other entry is a multiple of $3$.

Here's the idea. All the rows of all these matrices satisfy the following identity. If we have a row $(a\ b\ c)$ then $$720a+231b=c.$$ This is trivial for the first matrix. By induction you can easily prove that it holds for all the rows of all the subsequent matrices.

From that last matrix we then read $$ -17\cdot 720+53\cdot 231=3. $$


You can use negative multipliers if/when this speeds up the game. For example with multiplier $-2$ we could do a step $$ \left(\begin{array}{ccc} 1&-3&27\\ -8&25&15\end{array}\right)\mapsto \left(\begin{array}{ccc} 17&-53&-3\\ -8&25&15\end{array}\right), $$ and extract the answer from the top row.

$\endgroup$
  • 1
    $\begingroup$ Mind you, you will do a lot of rewrites if you keep copying the matrices. A more efficient way of using the idea would be to always add the new row to the bottom, and then do a row operation involving the two last rows. $\endgroup$ – Jyrki Lahtonen Oct 12 '18 at 5:41
  • $\begingroup$ This is great! Thanks for sharing this method. $\endgroup$ – Elstovenski Oct 12 '18 at 5:46
  • $\begingroup$ @Elstovenski I go into more detail about this method in this old answer. $\endgroup$ – Bill Dubuque Oct 13 '18 at 0:33
1
$\begingroup$

I like to do the extended part as a continued fraction.

$$ \gcd( 720, 231 ) = ??? $$

$$ \frac{ 720 }{ 231 } = 3 + \frac{ 27 }{ 231 } $$ $$ \frac{ 231 }{ 27 } = 8 + \frac{ 15 }{ 27 } $$ $$ \frac{ 27 }{ 15 } = 1 + \frac{ 12 }{ 15 } $$ $$ \frac{ 15 }{ 12 } = 1 + \frac{ 3 }{ 12 } $$ $$ \frac{ 12 }{ 3 } = 4 + \frac{ 0 }{ 3 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 3 & & 8 & & 1 & & 1 & & 4 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 3 }{ 1 } & & \frac{ 25 }{ 8 } & & \frac{ 28 }{ 9 } & & \frac{ 53 }{ 17 } & & \frac{ 240 }{ 77 } \end{array} $$ $$ $$ $$ 240 \cdot 17 - 77 \cdot 53 = -1 $$

$$ \gcd( 720, 231 ) = 3 $$
$$ 720 \cdot 17 - 231 \cdot 53 = -3 $$

$\endgroup$

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