# Using identities from Euclid's algorithm to solve problems

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

• Hint: 16/-21 is not the answer. – PM 2Ring Aug 8 '15 at 12:01
• I don't know how to find the answer then – Meeran Bala-Kumaran Aug 8 '15 at 12:08
• Your denominator $n$ needs to be positive. – PM 2Ring Aug 8 '15 at 12:10
• so, -16/21 correct? Even if that is the right answer, I don't know how to use the fact that gcd(m,n)=1 of the denominator and numerator of my answer in my working – Meeran Bala-Kumaran Aug 8 '15 at 12:14

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.
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.
$$\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}.$$