Q:

Euclid's first theorem/ Euclid's lemma

How to prove that if $c$ divides $ab$ and $\operatorname{gcd}(a,c)=1$, then show that $c$ divides $b$.
that means if $c|ab$ and $(a,c)=1 \implies c|b$.

A:

Hint.  If $\gcd(a,c)=1$ then there exist integers $x,y$ such that
$$ax+cy=1\ .$$
Now multiply both sides by $b$ and explain why $c$ is a factor of the left hand side.

