2020 USAMO Problems/Problem 3

Problem

Let $p$ be an odd prime. An integer $x$ is called a quadratic non-residue if $p$ does not divide $x - t^2$ for any integer $t$ .

Denote by $A$ the set of all integers $a$ such that $1 \le a < p$ , and both $a$ and $4 - a$ are quadratic non-residues. Calculate the remainder when the product of the elements of $A$ is divided by $p$ .

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

2020 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

We will be using finite field theory and the Frobenius endomorphism freely. Also we will just give a sketch and leave out details like it's out of fashion.

[b]Case 1[/b]: $p\equiv 3\pmod{4}$ . Work in $\mathbb{F}_{p^2} = \mathbb{F}_p[i]$ . Suppose $a\in A$ . Then, $a=-x^2$ for some $x\in\mathbb{F}_p$ and $4-a=y^2$ for some $y\in\mathbb{F}_p$ , so we have $x^2+y^2 = -4.$ This factors as $(x+iy)(x-iy) = (2i)^2,$ so we have $x+iy=2it$ and $x-iy=2i/t$ for some $t\in\mathbb{F}_p[i]$ , so $x=i(t+1/t)\quad\text{and}\quad y=t-1/t.$ For both of these to be in $\mathbb{F}_p$ , we need $x^p=x$ and $y^p=y$ , which when we work out with frobenius, tells us that $t^{p+1}+1=0$ .

Thus, if $a\in A$ , we must have $a=(t+1/t)^2$ for some $t\in\mathbb{F}_p[i]$ such that $t^{p+1}+1=0$ . Actually it is easy to see that if $t$ satisfies $t^{p+1}+1=0$ , then both $a$ and $4-a$ are QNRs (just reverse the frobenius calculation above). Thus, $A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{p+1}+1=0\}.$ Note $(t+1/t)^2 = (t'+1/t')^2$ if and only if $t'\in\{t,-t,1/t,-1/t\}$ , and also $t^{p+1}+1=0\iff (t')^{p+1}+1=0$ . Note that $t^{p+1}+1\mid t^{p^2}-t$ as $2(p+1)\mid p^2-1$ , so $t^{p+1}+1$ has distinct roots in $\mathbb{F}_p[i]$ . We see that $t^{p+1}+1=(t^{\frac{p+1}{2}}+i)(t^{\frac{p+1}{2}}-i),$ and $s$ a root of $t^{\frac{p+1}{2}}-i$ if and only if $1/s$ is a root. Thus, it is easy to see that $A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{\frac{p+1}{2}}-i=0\}.$ In this parameterization, only $t$ and $-t$ produce the same value (and these never coincide as $t\ne 0$ ), so we actually have $T:=\prod_{a\in A}=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}(t+1/t).$ This becomes $T=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}\frac{(t+i)(t-i)}{t}.$ Letting $f(x)=x^{\frac{p+1}{2}}-i$ , we see that this product becomes $T=(-1)^{\frac{p+1}{4}}\frac{f(-i)f(i)}{f(0)}.$ It is tedious but straightforward to see that this always gives $2$ .

[b]Case 2[/b]: $p\equiv 1\pmod{4}$ . Let $\ell$ be some QNR mod $p$ (sadly we don't have any free QNRs like $-1$ is for $3\pmod{4}$ primes). Let $\omega$ be a formal square root of $\ell$ , and work in $\mathbb{F}_{p^2} = \mathbb{F}_p[\omega]$ . Then, if $a\in A$ , we have $\omega^2 a = x^2\quad\text{and}\quad\omega^2(4-a)=y^2,$ so $x^2+y^2=4\omega^2$ , so factoring and doing the same as before, we get $x=\omega(t+1/t)\quad\text{and}\quad y=\frac{\omega}{i}(t-1/t)$ for some $t\in\mathbb{F}_p[\omega]$ . These are in $\mathbb{F}_p$ if and only if $t^{p-1}+1=0$ (using frobenius). We see $a=(t+1/t)^2$ , so $A = \{(t+1/t)^2 : t\in\mathbb{F}_p[\omega], t^{p-1}+1=0\}.$ Doing a similar analysis as before, the desired product becomes $T:=\prod_{a\in A}=(-1)^{\frac{p-1}{4}}\prod_{\substack{t\in\mathbb{F}_p[\omega]\\t^{\frac{p-1}{2}}-i=0}}\frac{(t+i)(t-i)}{t},$ and letting $f(x)=x^{\frac{p-1}{2}}-i$ , we get $T=(-1)^{\frac{p-1}{4}}\frac{f(-i)f(i)}{f(0)},$ which again is always $2$ .