3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – A.E Jul 2 '13 at 2:55
  • 1
    $\begingroup$ the above is incorrect. $\endgroup$ – noot Jul 2 '13 at 3:52
  • $\begingroup$ let $b=2, c=3, a=6$ $\endgroup$ – noot Jul 2 '13 at 3:52
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is the correct proof, not the other one. Just thought I'd endorse, for whatever it's worth. $\endgroup$ – A.E Jul 2 '13 at 3:01
  • $\begingroup$ I totally get your explanation, thanks. $\endgroup$ – user2162882 Jul 2 '13 at 18:23
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 2 '13 at 18:29
1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ This approach works nicely, $\endgroup$ – André Nicolas Jul 2 '13 at 5:25
1
$\begingroup$

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

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