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?
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$.