BY - tst for Navid, 2020

Number theory Difficulty 8.4 Shortlist Prove it Belarus

Let $P(x)$ be a non-constant polynomial with integer coefficients such that $P(0) \neq 1$ . Prove that there exist infinitely many primes $p$ such that $P(a) - a^{\frac{p-1}{2}}$ is divisible by $p$ for some positive integer $a$ (possibly, depending on $p$ ).

Solution

Consider the polynomial $Q(x) = P(x^2) - 1 \in \mathbb{Z}[x]$ . It's well-known that there exist infinitely many prime divisors of the numbers from the set $M = \{Q(n) : n \in \mathbb{N} \ \&\ Q(n) \neq 0\}$ . Moreover, since $Q(0) = P(0) - 1 \neq 0$ , among these prime divisors there exist infinitely many primes which doesn't divide $Q(0)$ . Clearly, if $p \mid Q(n)$ and $p \nmid Q(0)$ , then $p \nmid n$ .

Therefore there exist infinitely primes $p$ and $n \in \mathbb{N}$ such that $p \nmid n$ and $p \mid P(n^2) - 1$ . Each such $p$ satisfy the problem conditions with $a = n^2$ .

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

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