If $\gcd(a, c) = 1$ and $b | c$, prove that $(a, b) = 1$

Question

If $\gcd(a, c) = 1$ and $b \mid c$, prove that $(a, b) = 1$

-Not sure how to approach this problem.

-We have just started the greatest common divisor section, and looking at my notes I see that $(a \mid c = 1) \implies ax+by = 1$, would this be useful?

-My train of thought is $b \mid c$ then this proof would be relatively straight forward since $c$ is a multiple of $b$.

-I'm struggling with how I would set this up as a proof, any help is appreciated.

Answer 1

Let $p$ be a prime dividing $a$ and $b$. We derive a contradiction. Since $b \mid c$, also $p \mid c$. But then $p$ divides both $a$ and $c$, contradicting gcd$(a,c)=1$.

Answer 2

"My train of thought is b∣c then this proof would be relatively straight forward since c is a multiple of b".

That's a good thought. $\gcd(a,b)|a$ and $\gcd(a,b)|b$. Therefore $\gcd(a,b)|c$. So $\gcd(a,b)|a$ and $\gcd(a,b)|c$ so $\gcd(a,b)|\gcd(a,c)$.

Answer 3

Here is a direct proof: if $b\mid c$, then $c=bk$ for some $k\in\mathbb Z$.

If $\gcd(a,c)=1$, then by Bézout's Lemma $ax+cy=1$ for some $x,y\in\mathbb Z$.

Therefore $a(x)+b(ky)=1$, and $\gcd(a,b)\mid a(x)+b(ky)=1$, so $\gcd(a,b)=1$.