# Proof about divisibility and greatest common divisor that doesn't use Bezout's formula [duplicate]

Suppose the $\gcd(a,b) = 1$ and $c$ divides $a + b$. Prove that $\gcd (a,c) = 1 = \gcd (b,c)$.

This is relatively easy using Bezout's formula. See here. But is there a way to do it without Bezout?

## marked as duplicate by Dietrich Burde, Community♦Oct 9 '16 at 8:57

Assume that $(a,c) \not = 1$ and let $p$ be a prime divisor of $(a,c)$. Then $p \mid c \mid a+b$, but as $p \mid a$ we have that $p \mid b$. But this contradicts the fact that $(a,b) = 1$. Therfore $(a,c) = 1$. Similarly $(b,c) = 1$
• This (excellent) proof doesn't need to be a proof by contradiction. We know that $\gcd(a,c)\mid a$, and $\gcd(a,c)\mid c\mid(a+b)$; hence $\gcd(a,c)$ divides $(a+b)-b=b$, and so $\gcd(a,c)$ is a common divisor of $a$ and $b$. Therefore it's less than the greatest common divisor: $1\le \gcd(a,c)\le \gcd(a,b)=1$. – Greg Martin Oct 9 '16 at 8:38
• Hmm, actually I mean it divides $(a+b)-\underline{a} = b$. – Greg Martin Oct 9 '16 at 21:25