2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: 16/-21 is not the answer. $\endgroup$ – PM 2Ring Aug 8 '15 at 12:01
  • $\begingroup$ I don't know how to find the answer then $\endgroup$ – Meeran Bala-Kumaran Aug 8 '15 at 12:08
  • $\begingroup$ Your denominator $n$ needs to be positive. $\endgroup$ – PM 2Ring Aug 8 '15 at 12:10
  • $\begingroup$ 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 $\endgroup$ – Meeran Bala-Kumaran Aug 8 '15 at 12:14
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.