Putnam 2012, Problem B-6

Let $p$ be an odd prime number such that $p \equiv 2 \pmod{3}$. Define a permutation $\pi$ of the residue classes modulo $p$ by $\pi(x) \equiv x^3 \pmod{p}$. Show that $\pi$ is an even permutation if and only if $p \equiv 3 \pmod{4}$.


Solution:
**First solution.** Since fixed points do not affect the signature of a permutation, we may ignore the residue class of $0$ and consider $\pi$ as a permutation on the nonzero residue classes modulo $p$. These form a cyclic group of order $p-1$, so the signature of $\pi$ is also the signature of multiplication by $3$ as a permutation $\sigma$ of the residue classes modulo $p-1$. If we identify these classes with the integers $0, \ldots, p-2$, then the signature equals the parity of the number of inversions: these are the pairs $(i,j)$ with $0 \leq i < j \leq p-2$ for which $\sigma(i) > \sigma(j)$. We may write
$$\sigma(i) = 3i - (p-1) \left\lfloor \frac{3i}{p-1} \right\rfloor$$
from which we see that $(i,j)$ cannot be an inversion unless $\lfloor \frac{3j}{p-1} \rfloor > \lfloor \frac{3i}{p-1} \rfloor$. In particular, we only obtain inversions when $i < 2(p-1)/3$.

If $i < (p-1)/3$, the elements $j$ of $\{0, \ldots, p-2\}$ for which $(i,j)$ is an inversion correspond to the elements of $\{0, \ldots, 3i\}$ which are not multiples of $3$, which are $2i$ in number. This contributes a total of $0 + 2 + \cdots + 2(p-2)/3 = (p-2)(p+1)/9$ inversions.

If $(p-1)/3 < i < 2(p-1)/3$, the elements $j$ of $\{0, \ldots, p-2\}$ for which $(i,j)$ is an inversion correspond to the elements of $\{0, \ldots, 3i-p+1\}$ congruent to $1$ modulo $3$, which are $(3i-p+2)/3 = i - (p-2)/3$ in number. This contributes a total of $1 + \cdots + (p-2)/3 = (p-2)(p+1)/18$ inversions.

Summing up, the total number of inversions is $(p-2)(p+1)/6$, which is even if and only if $p \equiv 3 \pmod{4}$. This proves the claim.

**Second solution** (by Noam Elkies). Recall that the sign of $\pi$ (which is $+1$ if $\pi$ is even and $-1$ if $\pi$ is odd) can be computed as
$$\prod_{0 \leq x < y < p} \frac{\pi(x) - \pi(y)}{x-y}$$
(because composing $\pi$ with a transposition changes the sign of the product). Reducing modulo $p$, we get a congruence with
$$\prod_{0 \leq x < y < p} \frac{x^3 - y^3}{x-y} = \prod_{0 \leq x < y < p} (x^2 + xy + y^2).$$

It thus suffices to count the number of times each possible value of $x^2 + xy + y^2$ occurs. Each nonzero value $c$ modulo $p$ occurs $p+1$ times as $x^2 + xy + y^2$ with $0 \leq x,y < p$ and hence $(p + \chi(c/3))/2$ times with $0 \leq x < y < p$, where $\chi$ denotes the quadratic character modulo $p$. Since $p \equiv 2 \pmod{3}$, by the law of quadratic reciprocity we have $\chi(-3) = +1$, so $\chi(c/3) = \chi(-c)$. It thus remains to evaluate the product $\prod_{c=1}^{p-1} c^{(p+\chi(-c))/2}$ modulo $p$.

If $p \equiv 3 \pmod{4}$, this is easy: each factor is a quadratic residue (this is clear if $c$ is a residue, and otherwise $\chi(-c) = +1$ so $p + \chi(-c)$ is divisible by $4$) and $-1$ is not, so we must get $+1$ modulo $p$.

If $p \equiv 1 \pmod{4}$, we must do more work: we choose a primitive root $g$ modulo $p$ and rewrite the product as
$$\prod_{i=0}^{p-2} g^{i(p+(-1)^i)/2}.$$

The sum of the exponents, split into sums over $i$ odd and $i$ even, gives
$$\sum_{j=0}^{(p-3)/2} \left(j(p+1) + \frac{(2j+1)(p-1)}{2}\right)$$
which simplifies to
$$\frac{(p-3)(p-1)(p+1)}{8} + \frac{(p-1)^3}{8} = \frac{p-1}{2} \left(\frac{p^2-1}{2} - p\right).$$

Hence the product we are trying to evaluate is congruent to $g^{(p-1)/2} \equiv -1$ modulo $p$.

**Third solution** (by Mark van Hoeij). We compute the parity of $\pi$ as the parity of the number of cycles of even length in the cycle decomposition of $\pi$. For $x$ a nonzero residue class modulo $p$ of multiplicative order $d$, the elements of the orbit of $x$ under $\pi$ also have order $d$ (because $d$ divides $p-1$ and hence is coprime to $3$). Since the group of nonzero residue classes modulo $p$ is cyclic of order $p-1$, the elements of order $d$ fall into $\varphi(d)/f(d)$ orbits under $\pi$, where $\varphi$ is the Euler phi function and $f(d)$ is the multiplicative order of $3$ modulo $d$. The parity of $\pi$ is then the parity of the sum of $\varphi(d)/f(d)$ over all divisors $d$ of $p-1$ for which $f(d)$ is even.

If $d$ is odd, then $\varphi(d)/f(d) = \varphi(2d)/f(2d)$, so the summands corresponding to $d$ and $2d$ coincide. It thus suffices to consider those $d$ divisible by $4$. If $p \equiv 3 \pmod{4}$, then there are no such summands, so the sum is trivially even.

If $p \equiv 1 \pmod{4}$, then $d = 4$ contributes a summand of $\varphi(4)/f(4) = 2/2 = 1$. For each $d$ which is a larger multiple of $4$, the group $(\mathbb{Z}/d\mathbb{Z})^*$ is isomorphic to the product of $\mathbb{Z}/2\mathbb{Z}$ with another group of even order, so the maximal power of $2$ dividing $f(d)$ is strictly smaller than the maximal power of $2$ dividing $d$. Hence $\varphi(d)/f(d)$ is even, and so the overall sum is odd.

**Remark.** Note that the second proof uses quadratic reciprocity, whereas the first and third proofs are similar to several classical proofs of quadratic reciprocity. Abhinav Kumar notes that the problem itself is a special case of the Duke-Hopkins quadratic reciprocity law for abelian groups (Quadratic reciprocity in a finite group, Amer. Math. Monthly 112 (2005), 251-256; see also http://math.uga.edu/~pete/morequadrec.