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

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 TurgeonApr 22 '14 at 5:18

• 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. – Henry Swanson Apr 22 '14 at 3:36
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$.