I've done a similar problem where $p=1(3)$ and showed that $-3$ is a quadratic residue modulo $p$. These problems are sledgehammered by reciprocity laws, so I am trying to prove it directly using the fact that $U(\mathbb{Z}/p\mathbb{Z})$ is cyclic of order $p-1$ and since $p=3k+1$ we know the order of the group is a multiple of $3$ and therefore it has an element of order 3, say $r$. We know that $4+4r+4r^2=0 (p)$ if we multiply the LHS by $r$ which is not a unit we get the same thing back. From here we just rearrange and get $4r^2+4r+1=-3(p)$ and the LHS is just $(2r+1)^2$ so $-3$ is a residue.
I've been trying to do the same thing for 5, but I can't get it to work. That is, starting from $1+k+k^2+k^3+k^4=0(p)$ where $k$ is an element of order five in $U$, getting something of the form $(f(k))^2=5(p)$ where $f(x)$ is a polynomial with integer coefficients.