Track / Stage 8 / 119 of 180 #2299 of 2444

Problem 2299

IMO Shortlist mid-range; USAMO P2/P5

Number theory Difficulty 8.5 Prove it Baltic Way Shortlist · Baltic Way · 2023

For a prime number $p$ and a polynomial $f$ with integer coefficients, define $\text{Im}(p, f)$ be the set of integers $a \in \{0, 1, \dots, p-1\}$ such that there exists an integer $x$ , for which $f(x) - a$ is divisible by $p$ .

Prove that there exist nonconstant polynomials $f$ and $g$ such that, for infinitely many primes, the intersection of $\text{Im}(p, f)$ and $\text{Im}(p, g)$ is empty.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

We take $f(x) = (x^2 + 1)^2$ and $g(y) = -(y^2 + 1)^2$ and prove that if $p \equiv 3 \pmod 4$ then the equation $f(x) \equiv g(y) \pmod p$ has no solution. Famously, there are infinitely many primes congruent to $3$ modulo $4$ .

Recall the fact that if $p \equiv 3 \pmod 4$ then the only solution to the equation $a^2 + b^2 \equiv 0 \pmod p$ is $a \equiv b \equiv 0 \pmod p$ . Hence, for $f(x) \equiv g(y) \pmod p$ to hold, we need
$(x^2 + 1)^2 + (y^2 + 1)^2 \equiv 0 \pmod{p}$
and thus
$x^2 + 1 \equiv y^2 + 1 \equiv 0 \pmod{p},$
which is impossible for $p \equiv 3 \pmod 4$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.