Prove if $a\mid b+c$ and $\gcd(b, c)=1$ then $\gcd(a, b)=1$

Question

Let $a, b, c$ be integers. Prove if $a\mid (b+c)$ and $\gcd(b, c)=1$, then $\gcd(a, b)=1$.

This is my current proof:

Assume $a, b, c$ are integers, $a|(b+c)$, and $\gcd(b, c)=1$. Using Bezout's Theorem, we have $bu+cv=1$ for some integers $u$ and $v$. We also have $b+c=aq$ for some integer $q$, i.e. $c=aq-b$. Then we have $bu+(aq-b)v=1$, i.e. $b(u-v)+a(qv)=1$. Observe $(u-v)$ and $(qv)$ are integers. Then from Bezout's Theorem we have $\gcd(a, b)=1$.

My professor said this is incorrect because in the last sentence I assumed the converse of Bezout's Theorem. I am unsure of how to get to the conclusion from what I have then.

Answer 1

Let $n=\gcd(a,b)$ and note that $n$ divides $a$ and $b$. As $a | (b+c)$ so $b+c=ma$ for some $m$, so $c=ma-b$ and so $n | c$ too, as difference of two multiples of $n$.

So $n | b$ and $n |c$ so $n | \gcd(b,c)=1$ and $n=1$ and we're done.

No Bézout is needed at all.

Answer 2

Actually a sort of converse of Bezout's is valid: If you have an integer combination $ak_1+bk_2=Q$, then any common divisor of $a$ and $b$ divides $Q$. (Is that clear enough?) In particular, the greatest common divisor $\operatorname{gcd}(a,b)$ does.

But in your case you got $Q=1$. What are its divisors?

Answer 3

Let $\overbrace{ak=b+c}^{a\mid b+c}$ and $\overbrace{bx+cy=1}^{(b,c)=1}$, then $$ \begin{align} aky+b(x-y) &=(b+c)y+b(x-y)\\ &=bx+cy\\ &=1 \end{align} $$ Since $\color{#C00}{(a,b)}\mid\color{#C00}{a}ky+\color{#C00}{b}(x-y)=1$, we must have $(a,b)=1$.

Answer 4

It is simpler (and more general) to use basic gcd laws, e.g. as below

$$a\mid b\!+\!c \,\Rightarrow\, (a,b) = (a,b,b\!+\!c) = (a,\color{#c00}{b,c}) = 1\ \ {\rm by}\ \ (\color{#c00}{b,c})=1\qquad$$

twice using $\, k\equiv k'\pmod{\!n}\,\Rightarrow\, (k,n,\ldots) = (k',n,\ldots) = $ reduction step in Euclidean algorithm.