How would one go about proving that:

$a|bc$ , $gcd(b,c)=1 \Rightarrow a|b$ or $a|c$ but not both

I know that $a|bc$ , $gcd(a,b)=1 \Rightarrow a|c$ but I'm not sure how to use that when we know the two components of the product ($b$ and $c$) are relatively prime.

  • 2
    $\begingroup$ What about $6\mid 3\cdot 2, \gcd(3,2)=1$? Then none of $6\mid 3$ and $6\mid 2$ holds. You probably have in mind $a$ prime. $\endgroup$ – user26486 Mar 12 '15 at 20:40
  • $\begingroup$ The title needs rewording in any case. You are not asking about "divisibility of common divisor of two relatively prime numbers". The common divisor of two relatively prime numbers can only be $\pm 1$. $\endgroup$ – hardmath Mar 12 '15 at 20:44

It is true iff $\,a=0\,$ or $\,a = p^n,\, n\ge 1\,$ is a prime power. Indeed, if so then $\,p^n\mid ab\,$ and $\,a,b\,$ coprime $\,\Rightarrow\,p^n\mid a\,$ or $\,p^n\mid b\,$ by unique factorization (or by iterating Euclid's Lemma, that prime $\,p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b).\,$ Conversely, if $\,|a|>1\,$ and $a$ is not a prime power then it has at least two different prime factors, so $\, a = p^n c,$ $\,\,p\nmid c>1,\,$ and $\,a\mid p^n c,\ a\nmid p^n,\, a\nmid c.$


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.