2
$\begingroup$

Problem : Confirm the following properties of the greatest common divisor:

If $\gcd(a,b) = 1$, and $c \mid (a+b)$, then $\gcd(a,c) = \gcd(b,c) = 1$.

Is this right? This is my answer:

  • $\gcd(a,b) = 1$ => There exist integers $x$ and $y$ such that: $ax + by = 1$.

  • $c \mid (a+b)$ => There exist an integer k such that: $ck = a + b$ => $a = ck - b$ and $b = ck - a$.

  • Because $ax + by = 1$ and $a = ck - b$ => $(ck - b)x + by = 1$ <=> $c(xk) + b(y - x) = 1$ ( $xk$ and $(y - x)$ are integers ) => $\gcd(c, b) = 1$.

  • Because $ax + by = 1$ and $b = ck - a$ => $ax + (ck - a)y = 1$ <=> $a(x - y) + c(ky) = 1$ ( $(x - y)$ and $ky$ are integers ) => $\gcd(a, c) = 1$.

=> $\gcd(a,c) = \gcd(b,c) = 1$.

$\endgroup$
  • $\begingroup$ Your proof is correct. We actually have, more strongly, $\gcd(a,b)=1\iff \exists x,y\in\mathbb Z (ax+by=1)$ instead of $\implies$, which is what is required to lead you to the conclusions that $\gcd(c,b)=1$ and $\gcd(a,c)=1$ in the last two points. $\endgroup$ – user26486 Apr 5 '15 at 16:43
  • $\begingroup$ @user31415 But we don't need to associate that trivial inference to the converse of Bezout's theorem, since $\,d\mid a,b\,\Rightarrow\,d\mid ax+by\ [= 1]\,$ is usually learned (long) before Bezout. Moreover, this holds true more generally in any ring, even those that lack gcds/Bezout. Bezout's theorem is the nontrivial direction $(\Rightarrow)$ of that equivalence. $\endgroup$ – Bill Dubuque Apr 5 '15 at 17:12
1
$\begingroup$

I think your reasoning is right, and I can provide a shorter proof: $\gcd(a,a+b)=\gcd(a,b)=1$ and similarly $\gcd(b,a+b)=\gcd(b,a)=1$. Then $c\mid a+b$ implies $\gcd(a,c) = \gcd(b,c) = 1$

$\endgroup$
1
$\begingroup$

Yes, it is correct. More simply

$$c\mid a\!+\!b \,\Rightarrow\, (c,b)\mid a\!+\!b,b \,\Rightarrow\, (c,b)\mid (a\!+\!b,b) = (a,b)=1$$

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