As another answer shows, if $p\equiv1\pmod3$, then $-3$ is a quadratic residue modulo $p$. That means there is an integer $x$ such that $p{\rm\ divides\ }x^2+3$ Now we pass to ${\cal O}_{-3}$, the ring of integers in the number field $K={\bf Q}(\sqrt{-3})$, and write, $p{\rm\ divides\ }(x+\sqrt{-3})(x-\sqrt{-3})$ Now $p$ doesn't divide either one of $x\pm\sqrt{-3}$ since ${x\over p}\pm{1\over p}\sqrt{-3}$ are not in ${\cal O}_{-3}$. But it is known that ${\cal O}_{-3}$ is a unique factorization domain, implying that if an irreducible divides a product it must divide one of the factors. We deduce that $p$ is not an irreducible in ${\cal O}_{-3}$. Let $\pi=a+b{1+\sqrt{-3}\over2}$ be a nontrivial factor of $p$ in ${\cal O}_{-3}$. Then the norm of $\pi$ is a positive nontrivial factor of the norm of $p$, which is $p^2$, so the norm of $\pi$ is $p$. But the norm of $\pi$ is $a^2+ab+b^2$, QED.
EDIT: Similarly, if $p\equiv\pm1\pmod5$, then $5$ is a quadratic residue modulo $p$, so $p{\rm\ divides\ }x^2-5$ for some $x$. Going to ${\cal O}_5$, $p{\rm\ divides\ }(x+\sqrt5)(x-\sqrt5)$ but $p$ divides neither one of $x\pm\sqrt5$. Now ${\cal O}_5$ is known to be a UFD, so, again, $p$ is not irreducible in ${\cal O}_5$. Let $\pi=r+s{1+\sqrt5\over2}$ be a nontrivial factor of $p$ in ${\cal O}_5$. Taking norms, we get $p=r^2+rs-s^2$ Now a simple substitution gets us to $(a+b)^2+ab$.