Suppose there were a counterexample, with $pa=bc$, $p$ a prime, but neither $b$ nor $c$ divisible by $p$. Then there would be a counterexample with $p$ as small as possible and, for that $p$, $b$ as small as possible. Note that $b\gt1$, since otherwise we would have $pa=c$, which means $p$ divides $c$.
We first note that $b\lt p$, since otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample. But now $b\gt1$ implies $b$ is divisible by some prime $q$, which means we have $q$ dividing $pa$ with $q\le b\lt p$. By the minimality of $p$ as a counterexample, we conclude that $q$ divides $a$ (since it can't divide $p$). If we now write $a=a'q$ and $b=b'q$ and note that $b'\lt b\lt p$ implies $p$ doesn't divide $b'$ either, we find that $pa'=b'c$ is a smaller counterexample, which is a contradiction. Thus there can be no counterexample.
Remark (added later): The subtlety of Euclid's lemma is sometimes demonstrated with examples of multiplicative systems in which the lemma does not hold. One standard example is the set of positive integers congruent to $1$ mod $4$; another is the set of even integers. For the set $\{1,5,9,13,17,21,\ldots\}$ we have $9$, $21$ and $49$ as primes -- that is, none is the product of other numbers in the set (except, of course, themselves times $1$) -- yet $9\cdot49=21\cdot21$. As for the even integers, the primes are $\{2,6,10,14,18,\ldots\}$ -- that is, anything that's twice an ordinary odd number -- yet $2\cdot30=6\cdot10$.
It's worth seeing where the proof given above fails for these examples.
The failure point in both cases is in the statement "otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample," but for different reasons. The set of integers congruent to $1$ mod $4$ is not closed under subtraction, so the statement simply makes no sense. For the set of even integers, the statement makes sense, but it's not true: $2$ does not divide $6$, but it does divide $6-2=4=2\cdot2$. What's going on is that, although the even integers are a ring, it's a ring without a unit (because $1$ is odd, not even): The theorem $d\mid n\implies d\mid (n+d)$ holds because its proof goes $d\mid n\implies n=dm\implies n+d=dm+d=d(m+1)\implies d\mid (n+d)$, and that proof falls apart if you don't have the number $1$.
Alternative proof (added later): I wondered from the outset if it was really necessary to make the double assumption that both $p$ and $b$ (given $p$) are as small as possible. It turns out it's enough to assume you have a counterexample with minimal $b$.
Among all counterexamples $pa=bc$ (with $p$ prime and not dividing either $b$ or $c$), there would have to be one with minimal $b$. Note that $b\not\mid a$, since otherwise $p$ would divide $p(a/b)=c$. Note also that $b\not\mid p$.
We first argue that $b$ must itself be prime. If not -- if $b=b'b''$ with $b',b''\lt b$ -- then either $p\mid b'(b''c)$ or $p\mid b''c$ would be a smaller counterexample. That is, since $p$ doesn't divide $b$, it can't divide any divisor of $b$ (that's true whether $p$ is prime or not), so if the minimality of $b$ rules out $b'(b''c)$ as a counterexample (because $b'\lt b$), we must conclude $p$ divides $b''c$, which itself violates the assumed minimality of $b$.
Now write $p=bk+r$ with $0\lt r\lt b$. (We have $0\lt r$ since $b\not\mid p$.) Since $b$ divides $pa$, it also divides $ra$, but $b$ clearly doesn't divide $r$ (since $0\lt r\lt b$) nor, as noted above, does it divide $a$. So this gives us a new counterexample: a prime number, $b$, that divides a product, $ra$, without dividing either factor. Most important, the first of those factors, $r$, is smaller than $b$. This contradicts the assumed minimality of $b$, so we can conclude that no counterexamples exist.
In the first solution you're not using, strictly speaking, the Euclidean algorithm, but a looser version thereof:
Let $a$, $b$, $x$ and $y$ be integers; if $a=bx+y$, then $\gcd(a,b)=\gcd(b,y)$.
The proof consists in showing that the common divisors of $a$ and $b$ are the same as the common divisors of $b$ and $y$.
There is no requirement that $a\ge b$ or that $y$ is the remainder of the division. Indeed your argument actually has a weakness, because $7a+3\ge 5a+2$ only if $2a\ge-1$, so it doesn't hold for $a\le-2$. But $7a+3\ge 5a+2$ is not really needed for the argument.
Since successive application of the statement above show that $\gcd(2a+1,2)=1$ and the gcd has never changed in the various steps, you can indeed conclude that $\gcd(5a+2,7a+3)=1$.
The second solution is OK as well.
You can simplify it by noting that if $d$ is a common divisor of $5a+2$ and $7a+3$, then it divides also
$$
5(7a+3)-7(5a+2)=1
$$
Best Answer
By Bézout's theorem and since $\gcd(a,b)=1$ then there are $u,v\in\mathbb Z$ s.t. $$ua+vb=1\tag{1}$$ we multiply $(1)$ by $c$ we find $$uac+vbc=c$$ now $a$ divides $uac$ and divides $vbc$ so $a$ divides their sum $c$.