This question already has an answer here:

I need help with the following.

Prove:$a|bc$ and $\gcd(a,b)=1$ implies $a|c$

following these writing guidelines http://i.imgur.com/qpIYqPp.png

What I know so far: By the Euclidean algorithm there are integers $x$ and $y$ with $ax + by = gcd(a,b) \implies ax + by = 1$, in our case. Multiplying both sides by $c$ we have $acx + bcy = c$.

Then I get stuck trying to finish it.

Update: By the Euclidean algorithm there are integers $x$ and $y$ with $ax+by=\gcd(a,b)$ thus $ax+by=1$. Multiplying both sides by $c$ we get $cax+cby=c$ since $a|bc$ $∃k$ such that $ak=bc$ thus $acx+aky=c$ therefore $a(cx+ky)=c$, so $a|c$ for some $(cx+ky) \in \mathbb{Z}$

Can someone verify that this is written properly?


marked as duplicate by apnorton, colormegone, ml0105, user61527, M Turgeon Apr 22 '14 at 5:18

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$ This prior question proves a stronger result: math.stackexchange.com/questions/434164/… (Abstract duplicate) $\endgroup$ – apnorton Apr 22 '14 at 3:01
  • $\begingroup$ Yep, it appears to be written properly. The only thing I'd check is the step where you say there are $x,y$ such that $ax + by = 1$. You call it the Euclidean algorithm, but I've only heard it described as Bezout's Lemma (or Linear Diophantine Equations). I've heard the Euclidean algorithm as referring to the division algorithm: $\forall a,b \in \mathbb{Z} \ \exists q,r \ a = bq + r, \ 0 \le r < b$, and its abstraction to commutative domains. $\endgroup$ – Henry Swanson Apr 22 '14 at 3:36
  • $\begingroup$ oh ok, so would it make more sense to say using Bezout's Lemma? $\endgroup$ – Mikky Davey Apr 22 '14 at 3:43
  • $\begingroup$ See also: math.stackexchange.com/questions/417479/… $\endgroup$ – Martin Sleziak Nov 21 '15 at 3:03

You're almost there!

You know that $a \mid bc$, so there is some $k$ such that $ak = bc$. Substitute into what you have to get $acx + (ak)y = c$. We can now pull out an $a$ and get $a(cx + ky) = c$, and so $a \mid c$.


$a | bc$ gives: $bc = na$, and $ap + bq = 1$ for some $n, p, q$ integers. So $c = c(ap + bq) = cap + bcq = acp + naq = a(cp + nq)$. So $a | c$.


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