First:

You should know that: ( If you don't, this can be deduced easily from Gauss' Lemma )

By the Quadratic Reciprocity Theorem: hence

And by Euler's Criterion:

So what we actually want is:

Let's go over all the possible remainders module 5:

- Case: here we must have: so k is even: and this can happen if and only if or and so we have either: or this means that we must have:
- Case: ( the 'similar' case, just change the sign - check it-), we get:
- Case: : here we require so we must have: and for this to happen: so k must be even, and then: and we must have: and for this either: or then we must have ( substitute back to p):
- Case here we get: -check it-

So the solution is the set of all primes satisfying one of the following congruences: