# Bezout identity of 720 and 231 by hand impossible? [duplicate]

## 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

3 = 15 - 12 * 1

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

Help! Thanks!

• $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. – Angina Seng Oct 12 '18 at 4:55
• Sorry for the stupid question, but how did you get the "two times" [2 *] 15 - 27 ? – Elstovenski Oct 12 '18 at 5:04
• $15-(27-15)=15-27+15$ etc... – Angina Seng Oct 12 '18 at 5:05
• So now should I go about continuing to back substitute or rather simplify? – Elstovenski Oct 12 '18 at 5:14
• 2(15)-(15*1+12) Like this? – Elstovenski Oct 12 '18 at 5:16

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.

• 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. – Jyrki Lahtonen Oct 12 '18 at 5:41
• This is great! Thanks for sharing this method. – Elstovenski Oct 12 '18 at 5:46
$$\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$$