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.

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

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$

  • $\begingroup$ 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$. $\endgroup$ – Greg Martin Oct 9 '16 at 8:38
  • $\begingroup$ @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. $\endgroup$ – Stefan4024 Oct 9 '16 at 8:43
  • $\begingroup$ @GregMartin -- You meant that gcd(a,x) divides (a+b)-b = a, right? $\endgroup$ – philosonista Oct 9 '16 at 21:04
  • $\begingroup$ Hmm, actually I mean it divides $(a+b)-\underline{a} = b$. $\endgroup$ – Greg Martin Oct 9 '16 at 21:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.