Extension of Euclid's lemma This is a somewhat obvious fact that is intuitively obvious to me, but I haven't been able to construct a proof of it. Euclid's lemma states for for $p$ a prime and $ab$ a product of integers (let's take everything to be positive for simplicity), if $p \mid ab$, then $p \mid a$ or $p \mid b$. This is clear, and I know how to prove it. Let's extend it somewhat. Suppose that $a$ and $b$ are two relatively prime integers, and we have $a \mid bc$ for some other integer $c$. Then $a \not \mid b$, so it must divide $c$. This fact is obvious to me, but I can't figure out how to prove it.
Does anyone have any hints or advice? Do I need the assumption of positivity? (For my purposes at the moment, I only need them to be positive, but there is value in having the most general result possible).
EDIT: Updated attempt:
We have that $a,b$ are relatively prime, so there exist $r,s \in \mathbb{Z}$ such that $ar + bs = 1$ by Bézout's lemma. Multiply through by $c$ to get $arc + bsc = c$. Then $a \mid arc$ and $a \mid bsc$, so $a \mid c$.
How is that?
We have $m|n \iff \gcd(m,n)=m$.
We have $\gcd(a,bc)=\gcd(a,c)$, because $\gcd(a,b)=1$.
So, $a=\gcd(a,c)$, therefore $a|c$.
We have $m|n \iff \gcd(m,n)=m$.
We have $\gcd(a,bc)=\gcd(a,c)$, because $\gcd(a,b)=1$.
So, $a=\gcd(a,c)$, therefore $a|c$.