Showing the Existence of a Quadratic Residue

Question

Given that $$x^{(p-1)/2} \equiv {1 \bmod p}$$, then $x$ is a quadratic residue modulo $p$. I'm having a hard time showing this though, because even though it's clear that $q = x^{(p+1)/4}$ has the property that $q^2 \equiv x \bmod p$, it's not obvious to be that $q$ exists because $(p+1)/4$ isn't always integral. How can I go about showing that $x$ is a quadratic residue in this case?

Answer 1

Let $p$ be an odd prime, and let $x$ be a fixed number such that $x^{(p-1)/2}\equiv 1\pmod{p}$. We will show that $x$ is a quadratic residue of $p$, using only Wilson's Theorem.

For any $s$ and $t$ between $1$ and $p-1$ we say that $t$ is a friend of $s$ if $st\equiv x\pmod{p}$. It is clear that for every $s$ between $1$ and $p-1$, there is a unique $t$ such that $t$ is a friend of $s$.

We want to show that there is an $s$ such that $s$ is her own friend, that is, $s^2\equiv x\pmod{p}$.

Suppose to the contrary that no one is her own friend. Pair the numbers between $1$ and $p-1$ into groups of $2$ friends. Since the product of the numbers in any friend pair is congruent to $x$, it follows that the product of all the numbers between $1$ and $p-1$, that is, $(p-1)!$, is congruent to $x^{(p-1)/2}$ modulo $p$.

We were told that $x^{(p-1)/2}$ is congruent to $1$ modulo $p$. However, by Wilson's Theorem, $(p-1)!\equiv -1\pmod{p}$. This contradiction shows that someone must be her own friend.

Remark: If we already know that every prime has a primitive root $g$, we can give a simpler proof. We want to show that $x$ is congruent to an even power of $g$. If to the contrary $x\equiv g^k$ where $k$ is odd, then $g^{k(p-1)/2}\equiv 1\pmod{p}$, which can be shown to contradict the fact that $g$ has order $p-1$ modulo $p$.