A combinatorial proof of Euler's Criterion? $(\tfrac{a}{p})\equiv a^{\frac{p-1}{2}} \text{ mod p}$ Euler's criterion states that  $ (\tfrac{a}{p}) \equiv a^{\frac{p-1}{2}} (\text{ mod }p \,) $, where $(\tfrac{a}{p})$ is the Legendre symbol.
Here is one algebraic proof, since $\mathbb{Z}/p\mathbb{Z}$ is cyclic, $a = g^k$ 
$ a^{\frac{p-1}{2}} = (g^{ \frac{p-1}{2}})^k = (-1)^k $
which is $\pm 1$ as to either $k$ is even or odd... Then one still has to prove this group is cyclic.
Is there a combinatorial proof if this identity?

I started thinking about this question reading about proofs of quadratic reciprocity.
 A: Let $p$ be an odd prime. We give a pairing argument for the result. 
Let $1\le x\le p-1$ and  $1\le y\le p-1$. Call $x$ and $y$  friends if $xy\equiv a\pmod{p}$ and $x\ne y$.  Note that any $y$ has at most one friend. This is because for any $y$ there is a unique $x$ such that $xy\equiv a\pmod{p}$. So $y$ is friendless precisely if that unique $x$ is congruent to $y$, that is, if $y^2\equiv a\pmod{p}$.   
Thus if $a$ is a quadratic non-residue of $p$, then every $y$ has a friend, and therefore the numbers from $1$ to $p-1$ can be paired so that any pair has product congruent to $a$.  It follows that $(p-1)!\equiv a^{(p-1)/2} \pmod{p}$, and therefore $a^{(p-1)/2}\equiv -1\pmod{p}$ by Wilson's Theorem.
If $a$ is a quadratic residue of $p$, then the two solutions of $x^2\equiv a\pmod{p}$ are friendless. If one of them is $r$, the other is congruent to $-r$ modulo $p$, so their product is congruent to $-a^2$ modulo $p$. Also, there are  $(p-3)/2$ pairs of friends. It follows that
$$(p-1)! \equiv a^{(p-3)/2}(-a^2)\equiv -a^{(p-1)/2}\pmod{p}.$$
So again from Wilson's Theorem we have $a^{(p-1)/2}\equiv 1\pmod{p}$. 
A: A combinatorial-ish proof can be given using Zolotarev's lemma:

$(a/p)$ is the sign of the permutation of $(\mathbf Z/p\mathbf Z)^\times$ induced by multiplication by $a$.

There is a completely combinatorial proof on Wikipedia, not relying on the existence of a primitive root. 
Now, on the other hand, let us write
$$\Delta = \prod_{1 \leq i < j <p} (i-j) \in (\mathbf Z/p\mathbf Z)^\times.$$
By definition of the sign of a permutation, and by Zolotarev's lemma, we have
$$(a/p)\Delta = \prod_{1 \leq i < j <p} (ai-aj) = a^{p(p-1)/2}\Delta = a^{p-1/2}\Delta$$
because there are $p(p-1)/2$ terms in the product, and because $a^p=a$. Therefore,
$$(a/p) = a^{(p-1)/2}.$$
