Elementary proof of $\gcd(a, b) = 1 \wedge a\ |\ b\ c \Rightarrow a \ | \ c$ [duplicate]

How does on prove $\gcd(a, b) = 1 \wedge a\ |\ b\ c \Rightarrow a \ | \ c$ with as elementary steps as possible (i.e. not using the fundamental theorem of arithmetic (unique prime factorization))?

EDIT: I saw that this theorem is called Gauss Theorem and is proved formally for integers $\mathbb Z$ in Coq, https://coq.inria.fr/library/Coq.ZArith.Znumtheory.html#Gauss

EDIT: Clarification: I forgot to tell that I want to prove this for the natural numbers $\mathbb N \geq 0$. Is Bezout's lemma applicable for the natural numbers, or is some other method needed?

• Yes it seem to be a dupe. Sorry about that. Commented Nov 20, 2015 at 19:08
• For a very elementary proof (only euclidean division), not mentioned in the above link, you can take a look at my answer to a similar question. Commented Nov 20, 2015 at 20:06
• Thanks, I'll give it a try! I was hoping for a constructive proof - just saying that there exists a smallest element in the set with the desired properties is a bit messy (I'm trying to do a formal proof), but is doable I'm sure. Commented Nov 20, 2015 at 22:02
• The proof I gave (I think it's Cauchy's) relies precisely on the fact that $\mathbf N$ is well ordered. Commented Nov 20, 2015 at 22:25

I am not sure if Bezout's theorem is allowed or not. If $\gcd(a,b)=1$, then by Bezouts's theorem there exist $m,n \in \mathbb{Z}$ such that $ma+nb=1$. It follows that $mac+nbc=c$. Therefore since $a$ divides $mac$ and $nbc$ it must divide $c=mac+nbc$.
• A clarification: I'd like to do the proof for the natural numbers $0,1,2,...$. I don't think Bezout's lemma holds for the natural numbers, since one of the coefficients usually is negative. Or am I mistaken? Commented Nov 20, 2015 at 23:35