Euler Criterion proof Let $p\not=2$ be prime, $c\in\mathbb{Z}$ such that $p\nmid c$. Then $$\left(\frac{c}{p}\right)=c^{\frac{p-1}{2}}\pmod{p}$$

My attempt:
Let $g\in\mathbb{Z}_p^\times$ be the generator of $\mathbb{Z}_p^\times$. So then $c=g^k$ for some $k$. Now let's consider this problem for $g$. Note that
$$g^{p-1}\equiv1\pmod{p}\implies g^{\frac{p-1}2}\equiv \pm 1\pmod{p}$$
but note that the order of $g$ is $p-1$ hence
$$g^{\frac{p-1}2}\equiv - 1\pmod{p}$$
Then 
$$c^{\frac{p-1}2} = \left(g^{\frac{p-1}2}\right)^k \equiv (-1)^k\pmod{p}$$
If $k$ is even then $c$ is a square modulo $p$ hence 
$$c^{\frac{p-1}2}\equiv1\pmod{p}$$
otherwise $c$ is not a square and hence 
$$c^{\frac{p-1}2}\equiv-1\pmod{p}$$
 A: Your proof is correct but a bit cavalier. Why can you say "otherwise $c$ is not a square"?
The answer to that question is that there are precisely $\frac{p-1}{2}$ squares modulo $p$. Indeed, the map $x \mapsto x^2$ is precisely a two-to-one map (since $x^2 \equiv y^2$ implies $(x+y)(x-y) \equiv 0$, so $p \mid x+y$ or $p \mid x-y$, so $x \equiv \pm y$), so it is immediate that there are precisely half as many squares as there are residues mod $p$.
Since we have found $\frac{p-1}{2}$ squares mod $p$ (namely those $g^{2k}$), the other ones must not be square.

My original proof ran as follows:
It is enough to show that the property holds for all $c \in \mathbb{Z}_p^*$, because "I am square mod $p$" is a property that is invariant on adding multiples of $p$.
We have $$c^{p-1} \equiv 1 \pmod{p}$$
and so $$c^{(p-1)/2} \equiv \pm 1 \pmod{p}$$
If $c$ is square mod $p$, then $c \equiv a^2 \pmod{p}$, some $a$; as you point out, then we do obtain $1 \pmod{p}$.
But considering all of $\mathbb{Z}_p^*$, how many solutions have we got there? We've found $\frac{p-1}{2}$ solutions to $$x^{(p-1)/2} \equiv 1 \pmod{p}$$
using a lemma that there are exactly $\frac{p-1}{2}$ quadratic residues mod $p$ (which can be proved because the map $x \mapsto x^2$ is exactly two-to-one).
So by Lagrange's theorem (which states that in an integral domain, a degree-$d$ polynomial has at most $d$ roots), there are no other roots.
Therefore all the other $a$ must have $$a^{(p-1)/2} \not \equiv 1 \pmod{p}$$
