One of my friends asked me how to solve the following exercise:
Let $p \geq 3$ prime. For every $a \in \mathbb{Z}_p^{*}$ it holds:
$$ x^2 \equiv a \mbox{ } \mbox{mod} \mbox{ } p $$ has a solution $x$ if and only if $$a^\frac{p-1}{2} \equiv 1\mbox{ } \mbox{mod} \mbox{ } p $$
So we solved " $\Rightarrow$ ". basically using Fermat. But I have problems with " $\Leftarrow$ ". I explained him how to solve "$\Leftarrow$" , but unfortunately I used things that he doesn't know. My solution was to notice that $Z_p^{*}$ is cyclic, so there is a generator $g$ and work with that BUT he said they never mentioned cyclic, generator and other terms I used. So my question is do you know an alternative, reasonable solution ?