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

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.

• Did you mean $\gcd(a, c) = 1 \implies ax + cy = 1$? – N. F. Taussig Feb 6 '16 at 23:06
• yes: updated accordingly – Nick Powers Feb 6 '16 at 23:08

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$.

• Why by contradiction? Let $d=\gcd(a,b)$; then $d\mid b$, so $d\mid c$. On the other hand $d\mid a$. Therefore $d=1$. – egreg Feb 7 '16 at 0:42

"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)$.

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$.