# If gcd(a, b) = 1 and a | bc. Prove that a | c. [duplicate]

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.

• If $c=qa$ then $a|c$ and you are done. This is not the hypothesis. It is what you need to show. – mfl Sep 30 '18 at 23:45
• I'm not sure what you mean. Could you explain further? – Safder Sep 30 '18 at 23:47
• "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.$ – mfl Sep 30 '18 at 23:48
• It is. Thank you for pointing it out. – Safder Sep 30 '18 at 23:51

## 2 Answers

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.