The converse of Euclid's Lemma Im having trouble proving the converse of Euclid's lemma, and was wondering if anyone could point me in the right direction. 
Euclid's Lemma: Let $p$ be a prime number and $a$ and $b$ be natural numbers greater than 1, then if $p|ab$ we know  $p|a$ or $p|b$
Converse: For some number $p$, if for all natural numbers $a$ and $b$ greater than 1, $p|ab$ implies $p|a$ or $p|b$, then $p$ is prime.
I tried showing that $p$ had only factors 1 and $p$, but I didn't really manage to make any progress, I'm just really not sure where to start, I'd really appreciate any help, thanks.
 A: If $p$ is not prime, then there are $a,b \neq p$ with $p = ab$. Now $p \mid ab$ but $p \not \mid a, p \not \mid b$.
longer version:
We already have the implication
($p$ prime) $\implies$ (if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$)
We want to show the implication
(if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$) $\implies$ ($p$ prime)
We do this my contraposition:
($p$ not prime) $\implies$ (there exist $a,b$ with $p \mid a \cdot b$ and $p \not \mid a, p \not \mid b$)
Now, if $p$ is not prime, then there is a factorization $p = a \cdot b$ with $a \neq p \neq b$. Hence we have $p \mid a \cdot b$, but $p \not \mid a, p \not \mid b$, which shows the above implication.
A: Suppose $p=ab$. By assumption, either $p\mid a$ or $p\mid b$.
If $p\mid a$, then $a=pc$, for some $c$ and so
$$
a=pc=abc
$$
Since $a\ne0$, we get $bc=1$. Can you go on?
A: By assumption, $p|ab$  and either $p|a$ or $p|b$.  Let
$$
ab = p_{1}p_{2}\cdots p_{n}
$$
be the prime decomposition of $ab$. We know that $p|ab$ and so, $p|p_{1}p_{2}\cdots p_{n}$. Then $p$ must divide one of $p_{i}$ for $1 \leq i \leq n$. Since $p_{i}$ are primes, it follows that $p$ must be prime.
