Prove that $a\mid c$; given that $a\mid bc$ and $\gcd(a,b) = 1$.

Question

Please help answer the number theory problem. The proof I came across goes like this:

Let $d = \gcd(a,b)$ then $d = ma + nb$.

$ma + nb = 1$.

then

$mac + nbc = c$.

$a\mid mac$, $a\mid nbc$, therefore $a\mid c$.

Not sure how last step unfolded. Thanks.

(This is my personal question I have not posted it anywhere else, and the context of my question is my own)

Answer 1

Given

$am+nb=1\\amc+nbc=c$

Since $a \mid bc$, then $bc = ka$ for some integer $k$. Substituting into your equation, we have that

$amc+ank=c$. Since there are solutions to $am+bn=1$, then there must be solutions to $a(mc+nk)=c$. Hence $a \mid c$

This is also known as Euclid's Lemma.

Another way to think of it is because $mc$ and $nk$ are integers (Since $m$ and $n$ exists), then $mc+nk$ is an integer, which means $\frac ca$ is an integer, which can only mean $a \mid c$.

Answer 2

We know $\gcd(a,b)=1\iff au+bv=1$ and $a\mid bc\iff bc=ak$ for some $k\in\Bbb Z$. Then $$au+bv=1\implies auc+bvc=c\implies auc+akv=c\implies a(uc+kv)=c\implies a\mid c$$ Note, after the second implication we introduced $bc=ak$.