How can I do the Euclidian's algorithm and the Extended Euclidean algorithm at the same time?

Question

This is what my lecture notes have but I cannot find anything like it online and there is no explanation in the notes. The example given is for 903 and 444. Thank you.

Answer 1

Let $a = 903$ and $b= 444$.

$903 - 2*444 = 15$ So $a - 2b = 15$.

$444- 29*15 = 444-435 = 9$ or in other words $b - 29(a-2b) = 59b-29a = 9$.

$15 - 9=6$ or in other words $(a-2b) -(59b-29a) = 30a -61b = 6$.

$9 - 6 = 3$ of in other words $(59b-29a) - (30a -61b) = 120b - 59a = 3$.

$6 -2*3 = 0$ so we are done.

$\gcd(903,444) = 3$ and $3 = 120b - 59a$

Answer 2

I like to write these as (simple) continued fractions.

$$ \gcd( 903, 444 ) = ??? $$

$$ \frac{ 903 }{ 444 } = 2 + \frac{ 15 }{ 444 } $$ $$ \frac{ 444 }{ 15 } = 29 + \frac{ 9 }{ 15 } $$ $$ \frac{ 15 }{ 9 } = 1 + \frac{ 6 }{ 9 } $$ $$ \frac{ 9 }{ 6 } = 1 + \frac{ 3 }{ 6 } $$ $$ \frac{ 6 }{ 3 } = 2 + \frac{ 0 }{ 3 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 2 & & 29 & & 1 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 59 }{ 29 } & & \frac{ 61 }{ 30 } & & \frac{ 120 }{ 59 } & & \frac{ 301 }{ 148 } \end{array} $$ $$ $$ $$ 301 \cdot 59 - 148 \cdot 120 = -1 $$

$$ \gcd( 903, 444 ) = 3 $$
$$ 903 \cdot 59 - 444 \cdot 120 = -3 $$

Answer 3

The Euclidean algorithm will quickly give you the greatest common divisor of two numbers, and in its extended version will give you the formula for a linear combination of the two numbers that equates to the $\gcd$.

I use a table-based form to assess two numbers $A$ and $B$ where each line gives a valid solution of $n=A\times s + B\times t$ (reading $n,s,t$ appropriately from each column in a given line). It starts with two "trivial" lines, one for each of the two numbers concerned, and then proceeds by combining the last two lines to form the next line. Using the values $A=903, B=444$ as an example:

\begin{array}{c|c} n & s & t & q \\ \hline 903 & 1 & 0 & \\ 444 & 0 & 1 & 2 \\ 15 & 1 & -2 & 29 \\ 9 & -29 & 59 & 1 \\ 6 & 30 & -61 & 1 \\ \color{red}{3} & -59 & 120 & 2 \\ 0 & - & - & - \\ \end{array}

$q$ shows what multiple of that line to subtract from the line above to make the next line - it is as big an integer as possible to make the subtraction still leave a positive (or zero) value for the next $n$.

So for example to combine the second and third lines to make the fourth line, we have $q=\left\lfloor \frac{444}{15} \right\rfloor =29$ so we get the new $n=444-29\times 15 = 9$, the new $s=0-29\times 1 = -29$ and the new $t=1-29\times(-2) = 59$.

We reach $n=0$ with the previous value of $n=3$. This shows that $\gcd(903,444)=3$, so these numbers have a common factor of $3$ only, and the extended table shows that a linear combination to reach that value is $120\times 444 - 59\times 903 =3$. If we had reached $n=1$ that would have indicated the two numbers had no common factors.