Primes for >1 (good expression)

Solution 1:

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$.