Year: 2012
Topic: Combinatorics Number Theory

Problem:
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}$. Given that $\pi$ is an even permutation, what value must p be congruent to modulo 4?.

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,\dots,p-2$, then the signature equals the parity of the number of \emph{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,\dots,p-2\}$ for which $(i,j)$ is an inversion correspond to the elements of $\{0,\dots,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,\dots,p-2\}$ for which $(i,j)$ is an inversion correspond to the elements of $\{0, \dots, 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 and gives us the answer as \boxed{3}.