Let $p_1, p_2, p_3$, and $p$ be prime numbers. Prove that there exist $x,y\in \mathbb{Z}$ such that $y^2\equiv p_1 x^4-p_1 p_2^2 p_3^2\, (mod\, p)$.
Problem
Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade
Tags: number theory, prime numbers, modulo
17.10.2024 15:40
First, if $p\mid p_1p_2p_3$ then taking $x=y=0$ suffices. So, assume $p\nmid p_1p_2p_3$. Case 1: $p\equiv 3\pmod{4}$. We have $y^2=p_1(x^2-p_2p_3)(x^2+p_2p_3)$. As $p\equiv 3\pmod{4}$, we have $(p_2p_3/p)=-(-p_2p_3/p)$, so either $p_2p_3$ or $-p_2p_3$ is a quadratic residue modulo $p$. Taking $x^2\equiv \pm p_2p_3$ and $y=0$ works. Case 2: $p\equiv 1\pmod{4}$. If $p_1$ is a quadratic residue, simply take $x=y=0$. Likewise, if $(p_2p_3/p)=1$ then take $x^2\equiv p_2p_3$ and $y=0$. The only remaining case is $(p_1/p)=-1$ and $(p_2p_3/p)=(p_2/p)(p_3/p)=-1$. So, either $(p_2/p)=1$ or $(p_3/p)=1$. Assume, wlog, it's the former. Then, $x^2\equiv k^2 p_2$ has a solution. Then, $p_1x^4 - p_1p_2^2p_3^2 = p_1p_2^2(k^4-p_3^2)$. To ensure this quantity is a quadratic residue, it suffices to ensure there is a value $k$ such that $k^4-p_3^2=(k^2-p_3)(k^2+p_3)$ is a quadratic non-residue. Now using $(p_3/p)=-1$, we write $k^2\equiv ap_3\pmod{p}$, where $(a/p)=-1$. Then, $k^4-p_3^2\equiv p_3^2(a-1)(a+1)\pmod{p}$. So, the problem boils down proving there exists an $a$ such that $(a-1)(a+1)$ is a non-residue and $a$ is also a non-residue. We now prove this is indeed the case. Suppose the contrary. That is, for every non-residue $a$, $(a-1)(a+1)$ is a residue. Now suppose there is an $a$ such that \[ \left(\frac{a-1}{p}\right) = \left(\frac{a}{p}\right) = \left(\frac{a+1}{p}\right)=-1. \]Inspecting $a-1$, since $(a-2)a$ must be a non-residue, we deduce $a-2$ is a non-residue. So is $a+2$. Continuing, we find that every number is a non-residue, a contradiction. Therefore, for every $a$ that is a quadratic non-residue, we have that both $a-1$ and $a+1$ are quadratic residues. Lastly, consider the map $a\mapsto a-1$ over $a$ that are non-residue. Since $a-1$ is a residue for all $a$ and there are $(p-1)/2$ non-zero values of $a$, this map outputs at least $(p-1)/2$ non-zero residues. Since this is the number of non-zero residues, we must have the pattern $+-+-+-\cdots$, where $+$ represent quadratic residues and $-$ represents non-residues. Lastly, note that for $u=(p-1)/2$, we have \[ \left(\frac{u-1}{p}\right) = \left(\frac{u+1}{p}\right), \]as $p\equiv 1\pmod{4}$, so the signs cannot alternate. We reached a contradiction. Remark. I'm fairly confident this must admit a much simpler solution, anyhow.