Finding HCF with the Euclidean Algorithm

Question

Using the Euclidean algorithm, find $\mathrm{hcf}(86, 100)$, and use this to find integers $s, t$ such that $\mathrm{hcf}(86, 100) = 86 · s + 100 · t$.

I have that the HCF is 2 but have forgotten what to do to find $s$ and $t$, any help would be appreciated.

Answer 1

We will use the Euclidean Algorithm to find $\gcd(86, 100)$. We have:

$$\gcd(86, 100)$$ $$\gcd(86, 100 - 86)$$ $$\gcd(86 - 6(100 - 86), 100 - 86) = \gcd(7(86) - 6(100), 100 - 86)$$ $$\gcd(7(86) - 6(100), (100 - 86) -6(7(86) - 6(100))) =\gcd(7(86) - 6(100), 37(100) - 43(86))$$

Note that $7(86) - 6(100) = 37(100) - 43(86) = 2$. Thus:

$$\boxed{\gcd(86, 100) = 2, (s, t) = (7, -6)}$$

Answer 2

If you use the Euclidean algorithm to find the hcf, reversing the steps will find you a solution. Thus start with

$$86 s_1 + 100 t_1 = 2$$

The first step is to write $100 = 86 + 14$, so this becomes $$ 86 (s_1 + t_1) + 14 t_1 = 2$$ which you rewrite as $86 s_2 + 14 t_1 = 2$, where $s_2 = s_1 + t_1$. Then write $86 = 6 \cdot 14 + 2$, and so $$ 2 s_2 + 14 t_2 = 2 $$ where $t_2 = t_1 + 6 s_2$. At this point you can see that $s_2 = 1$, $t_2 = 0$ is a solution. Now go back and calculate $t_1$ and $s_1$.

Answer 3

Indeed we have $86=2\cdot43$ and $100=2^{2}\cdot5^2$, so $\text{hcf}(86,100)=2.$

Next we apply the Euclidean algorithm $$100=1\cdot 86 + 14$$ $$86=6\cdot 14+2$$ $$14=2\cdot7+0$$

and we stop since we have $0$ remainder and indeed $\text{hcf}(100,86)=2$. Then we have $100-1\cdot86= 14$ from the first equality above and substituting into the second gives $$86=6\cdot 14+2=6\cdot(100-1\cdot86)+2=6\cdot100-6\cdot86+2$$

and re-arranging we obtain $$-6\cdot100+7\cdot86=2$$