Prove that $a^{(p-1)/2} \equiv 1$ (mod p) and $a^{(p-1)/2} \equiv -1 \pmod p$ I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this:

i) Suppose $p$ is prime, $(a,p)=1$ and the congruence $x^2 \equiv a \pmod p$ has a solution $x$. Prove that $a^{(p-1)/2}\equiv 1 \pmod p$.

And the same question but with an additional condition:

ii) Suppose $p$ is prime, $p \equiv 3  \pmod 4$, $(a,p) = 1$ and the congruence $x^2 \equiv a \pmod p$ does not have a solution $x$. Prove that $a^{(p-1)/2}\equiv -1 \pmod p$.

For i: Since $x^2 \equiv a \pmod p$ has a solution, we know that $p \mid x^2 - a$, hence $kp=x^2-a$ for some integer $k$, or $a = x^2-kp$. Now this doesn't really help me much!
For ii: Similarly stumped.
 A: Hints:
(i) If $x^2 \equiv a \pmod p$ then what is $a^{\frac{p-1}{2}}$ as a power of $x$? Do this and apply Fermat's little theorem.
(ii) Write $x=a^{\frac{p-1}{2}}$. Fermat's little theorem gives you $x^2 \equiv 1 \pmod p$. Now use the rest of the information you've been given.
A: For the first one, one just has to compute: $a^{(p-1)/2} = x^{2(p-1)/2} = x^{p-1} = 1 \mod p$.
For the second one, let $p = 4k + 3$. $a^{(p-1)/2}$ is a root of $X^2 - 1$ (as above) which has only two solutions: $1$ and $-1$. If $a^{(p-1)/2} = 1\mod p$, $a^{(p-1)/2}a = a \mod p$, and $a^{(p-1)/2}a = a^{(p+1)/2} = a^{2(k+1)} = {(a^{k+1})}^2$, hence $x^2 = a$ has a solution, which is a contradiction. Hence $a^{(p-1)/2} = -1\mod p$.
A: For the first part, note that $x^{p-1}\equiv 1$ by Fermat's little theorem. Then assuming that $p$ is not $2$ (deal with that case separetly), we have $1\equiv (x^2)^{(p-1)/2}\equiv a^{(p-1)/2}$.
For the second part, let $\alpha$ be a primitive element (this means that there is an element $\alpha$ in $\{1,...,p-1\}$ such that $\alpha$ has order exactly $p-1$ (this means that $\alpha^i$ will range through $\mathbb{Z}_p^\times$ as we let $i=1,2,..,p-1$). 
Then, since $a$ is not a square, we have that $a=\alpha^{2c+1}$, so $$a^{(p-1)/2}\equiv (\alpha^{2c+1})^{(p-1)/2}\equiv \alpha^{c(p-1)}\alpha^{(p-1)/2}\equiv \alpha^{(p-1)/2}$$Now note that $\alpha^{(p-1)/2}$ is a root of $x^2-1$. Also note that $1$ and $-1$ are also roots. Note that we cannot have three roots (the degree of $x^2-1$ is $2$ and over a field, the degree bounds the number of roots), so we have that $\alpha^{(p-1)/2}$ is either $1$ or $-1$, but it cannot be $1$ since the order of $\alpha$ is $p-1$, hence it is $-1$, and we are done. I just realized that I did not use the fact that $p\equiv 3\pmod{4}$ (all i used was $p\neq 2$), so I guess the conditions can be weakened. 
A: This is an important theorem due to Leonhard Euler reworded in a different essence I think and it is usually proved at the beginning of an introduction to quadratic residues.
First you need to know that in a complete residue system modulo $p$, there are exactly $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ non-residues and the quadratic residues are $1^2,2^2, \cdots, (\frac{p-1}{2})^2$. This could be checked as an easy exercise. If you needed further help with this let me know.
By using Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$.
Now I'll give you a sketch of proof for Euler's criterion, you can work out the details on your own. You can factor $a^{p-1} -1$ as $$a^{p-1}-1=(a^{(p-1)/2}-1)(a^{(p-1)/2}+1)$$
$$\implies 0 \equiv a^{p-1}-1\equiv (a^{(p-1)/2}-1)(a^{(p-1)/2}+1) \pmod{p}$$
But since $p$ is a prime number, then $a^{(p-1)/2}-1 \equiv 0 \pmod{p}$ or $a^{(p-1)/2}+1 \equiv 0 \pmod{p}$
You can check that $1^2, 2^2, \cdots, (\frac{p-1}{2})^2$ satisfy $x^{(p-1)/2} \equiv 1 \pmod{p}$. Now if you work out the details now which is easy I think it's obvious that $a$ is a non-residue if and only if $a^{(p-1)/2} \equiv -1 \pmod{p}$.
If you're familiar with Legendre's symbol you can state this theorem this way as well:
$$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \pmod{ p}\;\;\text{  and } \left(\frac{a}{p}\right) \in \{-1,0,1\}$$.
where Legendre's symbol is defined as:
$$\left(\frac{a}{p}\right) = \begin{cases}\;\;\,1 \text{ if } a \text{ is a quadratic residue modulo}\ p\text{ and } a \not\equiv 0\pmod{p} \\-1 \text{ if } a \text{ is a quadratic non-residue modulo}\ p\\\;\;\,0 \text{ if } a \equiv 0 \pmod{p}.  \end{cases}$$
A: $\newcommand{Zp}{\mathbb{Z}/p\mathbb{Z}}$Among the many proofs of these facts, let me mention one that uses basically only Fermat's little theorem, and then the fact that a polynomial of degree $n$ over a field has at most $n$ roots. And then of course you need to know that $\Zp$ is a field, for $p$ prime.
I take $p$ to be an odd prime.
If $0 \ne b \in \Zp$, then the equation
$$
x^{2} = b^{2}
$$
has the two solutions $x = b, -b$, and no more, because $x^{2} - b^{2}$ is a polynomial of degree $2$ over the field $\Zp$.
It follows that there are
$$
\frac{p-1}{2}
$$
non-zero squares in $\Zp$.
If $0 \ne b \in \Zp$, we have
$$
(b^{2})^{(p-1)/2} = 1,
$$
so if $a = b^{2}$ is a non-zero square, then
$$
a^{(p-1)/2} = 1.
$$
In other words, the non-zero squares in $\Zp$ are roots of the polynomial
$$
f = x^{(p-1)/2} - 1.
$$
Since there are $(p-1)/2$ squares, and $f$ has degree $(p-1)/2$, the non-zero squares are exactly the roots of the $f$.
So if $a$ is a non-square, we have $a^{(p-1)/2} \ne 1$. Since
$$
(a^{(p-1)/2})^{2} = 1,
$$
we have that $a^{(p-1)/2}$ is a root of $x^{2} - 1$, and it is different from $1$, so $a^{(p-1)/2} = -1$.
A: This question is asked as a homework problem in 6.042J Mathematics for Computer Science course from MIT OpenCourseware. I felt this proof I determined much easier to understand given the content of that course up to that problem. It may help others looking for a proof that does not rely on residues or fields.
For (i):
Proof. Assume $n$ is a square modulo $p$. Then, $\exists x \in \mathbb{Z}$ where $n \equiv x^{2} \pmod{p}$.
By Fermat's Little Theorem:
$$n^{p-1} \equiv 1 \pmod{p}$$
$$n^{p-1} -1 \equiv 0 \pmod{p}$$
$$n^{\frac{1}{2}(p-1) + \frac{1}{2}(p-1)} - 1 \equiv 0$$
$$n^{\frac{1}{2}(p-1)} \cdot n^{\frac{1}{2}(p-1)} - 1 \equiv 0$$
$$(n^{\frac{1}{2}(p-1)} - 1)(n^{\frac{1}{2}(p-1)} + 1) \equiv 0$$
$(n^{\frac{1}{2}(p-1)} + 1)$ divides both sides:
$$n^{\frac{1}{2}(p-1)} - 1 \equiv 0$$
By $ n \equiv x^2 \pmod{p}$:
$$(x^{2})^{\frac{1}{2}(p-1)} - 1 \equiv 0$$
$$x^{2 \cdot {\frac{1}{2}(p-1)}} -1 \equiv 0$$
$$x^{p-1} - 1 \equiv 0$$
By $ n \equiv x^2 \pmod{p}$:
$$(\sqrt{n})^{p-1} - 1 \equiv 0$$
$$(n^{\frac{1}{2}})^{p-1} - 1 \equiv 0$$
$$n^{\frac{1}{2} \cdot (p-1)} - 1 \equiv 0$$
$$n^{\frac{p-1}{2}} -1 \equiv 0$$
$$n^{\frac{p-1}{2}} \equiv 1 \pmod{p}$$
QED
I will edit this answer with a solution for (ii) if I arrive at it and if I believe it is valuable.
