Prove that the following is true for all natural numbers:
Trying to simplify with known equivalences: applying De Morgan on the red part and $p\to q\equiv \neg p \vee q$ on all parts:
$\forall p(\color{red}{\exists a,b((p\mid ab)\wedge(p\not \mid a)\wedge(p\not\mid b))}\vee\color{blue}{(\forall d(d\not\mid p)\vee(d=p)\vee(d=1)) })$
For the red part if $p=10 $: $10\mid 10 \wedge 10\not \mid 5\wedge 10 \not \mid 2$, so it's true, although not sure if for all $p$.
The blue part is a contradiction since for example $2 \mid 6 \vee 2\neq 6 \vee 2\neq 1$.
Does simplifying it the right way? Is it enough to show the red part always true?
If for any a and b, p|ab => p|a or p|b, then p is prime. Of course:
Assume p isn't prime. Then, there are u and v, with 1 < u < p and 1 < v < p, such that p = uv. But p divides itself, so p|uv, but by initial assumption this means that p|u or p|v, which implies that p is less than or equal to u or less than or equal to v, which is impossible.
Now that p is prime, let d be any natural number. If d divides p, then it's either 1 or p because the divisors of a prime number are either 1 or itself.