Library / /18 of 36

, 2023

Number theory Difficulty 8.5 Shortlist Prove it Baltic Way

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.

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.