Using identities from Euclid's algorithm to solve problems

Question

I have been given the following problems

(a) Use the $GCD$ algorithm to compute the greatest common divisor of $546$ and $416$.

(b) Use your working for the previous part to express $\frac{416}{-546}$ as a rational ${m \over n}$ where $n\geq 1$ and $\gcd(m,n)=1$.

I am able to do part (a) and was left with the following working

$\gcd(416,546)$

$\rightarrow 546 = 1 * 416 + 130$

$\gcd(130,416)$

$\rightarrow 416 = 130 * 3 + 26$

$\gcd(26,130)$

$\rightarrow 130 = 5 * 26 + 0$

$\gcd(0, 26)$

therefore $\gcd(416,546)=26$

Then with part (a), I found that because

$416 = 16 * 26$ and $546 = 21 * 26$

That ${16 \over -21}$ is the answer, this is wrong, and I'm struggling to see what I need to do to begin on this problem

Answer 1

If $gcd(m,n)=1$ then $m/n$ is a fraction reduced to its lowest terms, so you've actually used that fact.

And as I said in the comments, the other condition in part b) is that you have to ensure that $n≥1$, which is why your original answer was wrong.

Answer 2

I just wanted to point out that, given two integers $a,b\ge 1$,the Extended Euclidean Algorithm, continued one step further, gives coprime coefficients $u,v$ such that $ua=vb=0$, hence both gives $ \operatorname{lcm}(a,b)=\lvert u\rvert\, a=\lvert v\rvert\,b$, and the expression of $\dfrac ab$ or $\dfrac ba$ in lowest terms.

Here:

$$ \begin{array}{r@{\qquad}r@{\qquad}r@{\qquad}r} r_i & u_i & v_i & q_i\\ \hline 546 & 1 & 0 & \\ 416 & 0 & 1 & 1\\ \hline 130 & 1& -1 & 3\\ 26 & -3 & 4 & 5 \\ 0 & 16 & -21 & \\ \hline \end{array} $$ We deduce at once $\;\gcd(546,416)=26$, $\;\operatorname{lcm}(546,416)=21\cdot416=8736$ and $$\frac{416}{-546}=-\frac{16}{21}.$$