# Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I can't prove that $a \mid bc$, if and only if $a\mid b$ and $a\mid c$. Please help. Thanks.

• Assuming $a\,|\,bc$, consider the cases. We know either $a \, | \, b$ or $a \,|\, c$. If $a \,|\, c$, the proof is trivial, so assume otherwise. I'll let you tinker with the GCD, and return if you're still struggling. – A.E Jul 2 '13 at 2:55
• the above is incorrect. – noot Jul 2 '13 at 3:52
• let $b=2, c=3, a=6$ – noot Jul 2 '13 at 3:52

The first argument we give uses the Fundamental Theorem of Arithmetic. In a remark at the end, we do it another way.

Let $p$ be a prime that divides $a$, and let $p^r$ be the highest power of $p$ that divides $a$. Let $p^s$ be the highest power of $p$ that divides $b$, and let $p^t$ be the highest power of $p$ that divides $c$.

Because $a$ divides $bc$, we have $r\le s+t$.

(i) Suppose that $s\ge r$. Then $p^r$ divides $\gcd(a,b)$, and therefore $p^r$ divides the expression on the right.

(ii) Suppose now that $s\lt r$. Then $p^s$ divides $\gcd(a,b)$. Combined with the $p^t$ that comes from $c$, this shows that the highest power of $p$ that divides the right-hand side is $p^{s+t}$. We are finished, since $r\le s+t$.

Remark: We wrote a proof that uses FTA, since that is what you mentioned trying. However, we could let $d=\gcd(a,b)$ and $a=da'$, $b=db'$. From $a$ divides $bc$ we get that $a'$ divides $b'c$. Since $a'$ and $b'$ are relatively prime, we conclude that $a'$ divides $c$. Now it is easy to show that $a$ divides the right-hand side.

• This is the correct proof, not the other one. Just thought I'd endorse, for whatever it's worth. – A.E Jul 2 '13 at 3:01
• I totally get your explanation, thanks. – user2162882 Jul 2 '13 at 18:23
• You are welcome. Neither argument is difficult, but we need some number-theoretic machinery. Unique Factorization will do it, or Euclid's Lemma (if $x$ and $y$ are relatively prime, and $x$ divides $yz$, then $x$ divides $z$. Or else we can use Bezout's Theorem (the gcd of $a$ and $b$ is a linear combination of $a$ and $b$) as in noot's solution. – André Nicolas Jul 2 '13 at 18:29

If $a\mid c$ then you are done

If $a\mid b$ then $b=ak$ for some $k$, therefore $a\mid gcd(a,ak)$. Then it is easy to finish the excercise.

• That second line is not correct. – A.E Jul 2 '13 at 2:59
• @Orangutango corrected – chubakueno Jul 2 '13 at 3:04
• Yes indeed, this is probably the simplest way to see it. Nice! – A.E Jul 2 '13 at 3:07

$gcd(a,b)=ma+nb$

so we need to prove $a|mac+nbc$

$ac$ and $bc$ both divide a. So their linear combination also divides $a$.

• This approach works nicely, – André Nicolas Jul 2 '13 at 5:25

Hint $\,\ a\mid ac,bc\,\Rightarrow\,a\mid(ac,bc)=(a,b)c\,$ by the gcd Distributive Law.