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.
$ux = uy \quad\bmod p$ means, by definition, that $p|(ux -uy)$
Equivalently, we have $p|(u(x-y))$, and given is that $p$ does not divide $u$. Hence, $p$ must divide $x-y$. So, we have $p|(x-y)$, which translates by definition to $x = y \quad \bmod p$
If you have any questions, or use another definition for modular equalities, I will edit my question. Please let me know.
Best Answer
Even after the edit, I think your proof is not quite right. In essence you are trying to prove a consequence of Euclid's lemma by arguing that when $3$ does not divide both $m$ and $n$ then it cannot divide $mn$. That conclusion depends on $3$ being a prime number, and implicit in your logic is that $mn$ can be decomposed into a factorisation of primes. These ideas usually follow rather than precede Euclid's lemma. What is missing is the greatest common divisor rule, Bezout's identity.
The normal approach is
Establish Bezout's identity: for any two integers $a,b$ not both zero, there is a common factor $d$ and integers $x,y$ such that $d=ax+by $ and for every common divisor of $a,b$ divides $d$. This is proved by induction on $n = a+b$.
Establish $d$ is unique up to its sign and define define the greatest common divisor as the unique $d > 0$.
Prove Euclid's lemma: If $a$ and $b$ have no common factors and $a| bc$ then $a | c$.
Define primes as the positive integers $p > 1$ that only have positive divisors $1$ and $p$. Prove that for any $a$ if the prime $p$ does not divide $a$ then the highest common factor of $a$ and $p$ is $1$.
The last step is to prove your result: if the prime number $p|ab$ then $p|a$ or $p|b$. The proof is an immediate consequence of Euclid's lemma $(3)$ but can also be proved without explicitly using it by mimicking its proof, as follows,
Suppose $p \not | ~a$. Then by $(4)$ the highest common factor is $1$ and by $(1)$ there exist $x$ and $y$ such that $$1 = ax+py.$$ Then $$b=axb+pby$$ and $p$ divides both terms on the right because $p|ab$ and $p|pby$. Hence $p|b$.