# 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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• This is already answered by "SomeStrangeUser" , "Spock" and others at the old question you have linked, without using Bezout. – Dietrich Burde Oct 9 '16 at 8:37
• Ah, I did not see people adding non-Bezout proofs. – philosonista Oct 9 '16 at 8:47

## 1 Answer

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
• @GregMartin Yes, you're right there are more ways to prove this. Anyway I like contradiction more, because according to me in some way it gives us more freedom in the proof. – Stefan4024 Oct 9 '16 at 8:43
• @GregMartin -- You meant that gcd(a,x) divides (a+b)-b = a, right? – philosonista Oct 9 '16 at 21:04
• Hmm, actually I mean it divides $(a+b)-\underline{a} = b$. – Greg Martin Oct 9 '16 at 21:25