We will work with an odd prime.

One direction is obvious. We will show that if has a solution then has a solution. Let satisfy . We want to find an so that would satisfy i.e. . We can write this as ( this is because divides ). Finally since this congruence is solvable for . And we found our solution.