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.

  • 3
    $\begingroup$ I don't understand your question. $\endgroup$ – Pedro Tamaroff May 17 '14 at 21:26
  • $\begingroup$ how do you prove this identity about the Ledendre symbol without using Lagrange interpolation? $\endgroup$ – cactus314 May 17 '14 at 22:06

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}.$$


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}$.

  • $\begingroup$ Great! This assumes Wilson's theorem and the factorial should have a combinatorics meaning as well... $\endgroup$ – cactus314 May 17 '14 at 22:12
  • $\begingroup$ One can make it even more combinatorial by basing the proof on Fermat's Theorem, for which one can give a combinatorial counting necklaces proof. $\endgroup$ – André Nicolas May 17 '14 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.