3
$\begingroup$

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – egreg Feb 7 '16 at 0:42
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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