0
$\begingroup$

I haven't been able to figure out this question for a while though I'm sure it's pretty straightforward. (It's intuitive to me and difficult to write into a proof). Show that these statements are equivalent

I) $\gcd(a,b)=c$ and $a+b=d$

II) $c|d$

$\endgroup$
4
  • $\begingroup$ The statements are not equivalent. $5$ divides $2+3$ but $5$ is not gcd$(2,3)$. $\endgroup$
    – lulu
    Oct 9, 2015 at 13:59
  • $\begingroup$ Gcd(2,3)=1... 2+3=5... 1 divides 5. $\endgroup$
    – user278602
    Oct 9, 2015 at 14:06
  • 1
    $\begingroup$ Right, so that shows an example wherin $I \implies II$. But you asked to show that the two are equivalent. the implication $II \implies I$ is false, see my posted solution below. $\endgroup$
    – lulu
    Oct 9, 2015 at 14:08
  • $\begingroup$ $d$ can never equal $c$. Assuming both $a$ and $b$ are greater than $0$, then $d$ is greater than either of them, hence can't be a divisor. But, generally, the divisors of $a+b$ include the common divisors of $a$ and $b$ but it will have lot's of others as well. Think of the divisors of $12=11+1$. $\endgroup$
    – lulu
    Oct 9, 2015 at 14:26

1 Answer 1

4
$\begingroup$

If all you meant was "show that $I \implies II$" that is straightforward:

Let $c=\gcd(a,b)$. Write $a=cA$,$b=cB$. Then $$d=a+b=cA+cB=c(A+B)$$ so $c$ divides $d$.

But the other implication is not even remotely true. After all $1$ always divides $d$ yet $1$ isn't always the gcd of two specified numbers. Similarly, $d$ always divides $d$ but $d$ is larger than either $a$ or $b$, hence is not a divisor of either.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .