Solving equation using Euclidean Algorithm?

Question

Euclidean algorithm leverages multiplication and subtraction, which humans are fairly good at, to make fractions like 15996751/3870378 reducible. Also useful in scaling equations down to their simplest integer representation in one step, given with extra integers, GCD(C,GCD(A,B)) is equivalent to GCD(A,B,C). It's been around for over two thousand years and mathematicians have bent it to many purposes , but just the first bit should be justification.

I am trying to find the $\gcd$ of two numbers forming a linear combination: $5a+24b=1$. I know that $a = 5$ and $b = -1$, but I found these values through trial and error. How would I use Euclid's Algorithm to find a and b?

This is what I have done so far: $24/5 \implies Q=4, R=4, 5/4 \implies Q=1, R=4, 4/4 \implies Q=1, R=0$ How do I use this info to work backwards?

Answer 1

What you have done:

$$\color{blue}{24 = 5(4)}+\color{red}4\tag{1}$$ $$5=\color{red}4(1) + 1\tag{2}$$

Let's work backward:

$$1 = 5-\color{red}4(1)$$

Now, using equation $(1)$.

$$1=5-\color{blue}{(24-5(4))}(1)$$

Simplifying:

$$1=5-24+5(4)$$

$$1=5(5)-24$$

Answer 2

Using the extended Euclidean algorithm works like this:

$$\begin{align} 24\cdot 1 & + & 5\cdot 0 & = & 24 &&\\ 24\cdot 0 & + & 5\cdot 1 & = & 5 &&\\ 24\cdot 1 & + & 5\cdot -4 & = & 4 && \text{ from }24 = 5\cdot4 + 4\\ 24\cdot -1 & + & 5\cdot 5 & = & 1 && \text{ from }5 = 4\cdot1 + 1\\ \end{align} $$

In the right-most column we get a sequence of remainders from Euclidean division, each one less than the last. The algorithm must terminate because the remainders are positive and strictly decreasing. Furthermore, since the first two numbers in the remainder sequence are trivially linear combinations of $24$ and $5$, we can inductively see that each new remainder in the sequence can be expressed as a linear combination of $24$ and $5$.

Answer 3

$$ \gcd( 24, 5 ) = ??? $$

$$ \frac{ 24 }{ 5 } = 4 + \frac{ 4 }{ 5 } $$ $$ \frac{ 5 }{ 4 } = 1 + \frac{ 1 }{ 4 } $$ $$ \frac{ 4 }{ 1 } = 4 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 4 & & 1 & & 4 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 4 }{ 1 } & & \frac{ 5 }{ 1 } & & \frac{ 24 }{ 5 } \end{array} $$ $$ $$

$$ 24 \cdot 1 - 5 \cdot 5 = -1 $$

Answer 4

I take the chance for illustrating an equivalent (lesser known, which is pity) way for running the Euclidean algorithm, i.e. constructing and de-constructing a continued fraction. We have $$ \frac{24}{5} = 4+\frac{4}{5} = 4+\frac{1}{1+\frac{1}{4}} = [4;1,4] \tag{A}$$ $$ [4;1] = 4+\frac{1}{1} = \frac{5}{1} \tag{B} $$ $$ \frac{24}{5}-\frac{5}{1} = \frac{-1}{5} \tag{C}$$ $$ 24\cdot 1 - 5\cdot 5 = -1 \tag{D} $$ $$ 24\cdot (-1)+5\cdot 5 = 1 \tag{E} $$ $$ 24x+5y=1\quad\Longrightarrow\quad x=-1+5k,\;y=5-24k.\tag{F}$$ Explanations: the difference between two consecutive convergents $\frac{p_n}{q_n},\frac{p_{n+1}}{q_{n+1}}$ of the same continued fraction is always a number of the form $\frac{\pm 1}{q_n q_{n+1}}$. So we may consider the continued fraction of $\frac{a}{b}$, remove its last term, expand it back to get $\frac{a}{b}-\frac{c}{d}=\frac{\pm 1}{bd}$. By multiplying both sides by $bd$ (and adjusting signs if needed) we get a solution of our problem. The constraint $\gcd(a,b)=1$ ensures that once we get a solution we get all of them.

Answer 5

I favor the following approach, probably because of the way it reduces the housekeeping burden. The algorithm sketched below the demonstration.

$$\begin{array}{|c|c|} \hline (24, -5) & (1,0)\ (0,1) \\\hline (4,-5) & (1,4)\ (0,1) \\\hline (4,-1) & (1,4)\ (1,5) \\\hline (1,-1) & (\textbf{4},\textbf{19})\ (1,5) \\\hline \end{array}$$

(4) * 24 + (-19) * 5 = 1

In other words, b = 4 and a = -19

The first entry of the first row is an ordered pair consisting of the two given numbers (24 and 5), with the larger number first, and the negative of the smaller number as the second element of the pair, namely: (24, -5). The second column begins with the two "vectors" (1,0) and (0,1). The vectors track how many times the initial numbers contribute to the current linear combination.

To move from the first row to the second, we add 4 * -5 to 24, and add 4 * (0,1) to (1,0), following the usual gcd procedure.

Then we add 1 * 4 to -5, and 1 * (1,4) to (0,1) to get the third row, etc. Once we arrive at (1,-1), the left handed vector, (4,19) tells us how many 24s and -5s were needed to produce the resulting 1.

So 4 * 24 + (-19) * 5 = 1. If we observe that the second vector in the final row gives us (1) * 24 + (-5) * 5 = -1, we recover a second solution (-1) * 24 + (5) * 5 = 1.

For further details, see for example Stillwell's: Elements of Number Theory.