# The greatest common divisor

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

• 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. – user26486 Apr 5 '15 at 16:43
• @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. – Bill Dubuque Apr 5 '15 at 17:12

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$
$$c\mid a\!+\!b \,\Rightarrow\, (c,b)\mid a\!+\!b,b \,\Rightarrow\, (c,b)\mid (a\!+\!b,b) = (a,b)=1$$