This question already has an answer here:

Let a, b, c ∈ N such that (a, b) = 1 and a | bc. Prove that a | c.

I'm a little confused about if I'm doing this proof right.

I know that $\exists p, q \in \mathbb{Z}$. Such that $pa = bc$ and $qa=c$. Re-arranging the first equation.

$$a = \frac{bc}{p} $$

Substituting this into the second equation.

$$ qa = c$$ $$ q(\frac{bc}{p}) = c$$ $$ \frac{qb}{p} c =c $$ $$ \frac{qb}{p} c =c $$

Thus this equation divides c. Therefore a | c. Does this proof make sense.

Thank you for any guidance.


marked as duplicate by Arturo Magidin, Community Sep 30 '18 at 23:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ If $c=qa$ then $a|c$ and you are done. This is not the hypothesis. It is what you need to show. $\endgroup$ – mfl Sep 30 '18 at 23:45
  • $\begingroup$ I'm not sure what you mean. Could you explain further? $\endgroup$ – Safder Sep 30 '18 at 23:47
  • $\begingroup$ "I know that $\exists p, q \in \mathbb{Z}$ such that $pa = bc$ and $qa=c$." No. You don't know the existence of $q.$ $\endgroup$ – mfl Sep 30 '18 at 23:48
  • $\begingroup$ It is. Thank you for pointing it out. $\endgroup$ – Safder Sep 30 '18 at 23:51

You can't assume $c=qa$ because that if what you need to prove.

Hint for a solution: if $gcd(a,b)=1$ then there are numbers $k,l\in\mathbb{Z}$ such that $ak+bl=1$. Multiply this equation by $c$ and see what you get from there.


You do not know there is such a $q$. That is in fact exactly what you are trying to prove: it says $a$ divides $c$.

The standard argument for this theorem begins with the existence of integers $r$ and $s$ such that $$ ar + bs = 1 . $$

Multiply that equality by $c$ and try to conclude what you hope to prove.

Note: you should strive to write number theory proofs without fractions. Even when their use is correct it's confusing.


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