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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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