The lemma is shown in several ways. This is what I am exposed to (the simplest case I assume):
Let $p, a, b \in \mathbb{N}$ with $p > 1$. Then p is a prime $\iff p|ab \implies p|a \lor p|b$
I want to show two directions:
"$\implies$" is something that I am alright with.
"$\impliedby$" is what I am having difficulty with.
As a start, suppose for a contradiction that $p$ is not prime. Then $\exists$ $s,t$ $\in$ $\mathbb{N}\setminus\{1\}$.
I'm not sure as to where to continue on from there to achieve a contradiction.
This is usually the standard proof of Euclid's Lemma:
Let $p$ be a prime number that divides $ab$ but does not divide $a$. We must show that $p$ divides $b$. Since $p$ does not divide $a$, there are integers $m$ and $n$ such that $1=am+pn$. Then $b=abm+pnb$, and since $p$ divides the right-hand side of this equation, $p$ also divides $b$.