\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2020/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 35}
\maketitle
\section*{Problem}
Prove that for every odd integer $n > 1$,
there exist integers $a,b > 0$ such that,
if we let $Q(x) = (x+a)^2+b$, then the following conditions hold:
\begin{itemize}
\ii we have $\gcd(a,n) = \gcd(b,n) = 1$;
\ii the number $Q(0)$ is divisible by $n$; and
\ii the numbers $Q(1)$, $Q(2)$, $Q(3)$, \dots\
each have a prime factor not dividing $n$.
\end{itemize}
\section*{Video}
\href{https://www.youtube.com/watch?v=5a_XCGKiXnI}{\texttt{https://youtu.be/uj93tNL8f7M}}
\newpage
\section*{Solution}
Let $p_1 < p_2 < \dots < p_m$ denote the odd primes dividing $n$
and call these primes \emph{small}.
The construction is based on the following idea:
\begin{claim*}
For each $i= 1, \dots, m$ we can choose a prime $q_i \equiv 1 \pmod 4$ such that
\[
\left( \frac{p_j}{q_i} \right)
= \begin{cases}
-1 & \text{if } j = i \\
+1 & \text{otherwise}.
\end{cases}
\]
\end{claim*}
\begin{proof}
Fix $i$.
By quadratic reciprocity,
it suffices that $q_i \equiv 1 \pmod 4$
and that $q_i$ is a certain nonzero quadratic residue (or not)
modulo $p_j$ for $j \neq i$.
By Chinese remainder theorem,
this is a single modular condition,
so Dirichlet theorem implies such primes exist.
\end{proof}
We commit now to the choice
\[ b = k q_1 q_2 \dots q_m \]
where $k \ge 1$ is an integer
(its value does not affect the following claim).
\begin{claim*}
[Main argument]
For this $b$,
there are only finitely many integers $X$ satisfying the equation
\[ X^2+b = p_1^{e_1} \dots p_m^{e_m} \qquad(\spadesuit) \]
where $e_i$ are some nonnegative integers
(i.e.\ $X^2+b$ has only small prime factors).
\end{claim*}
\begin{proof}
In $(\spadesuit)$ the RHS is a quadratic residue modulo $b$.
For any $i > 0$, modulo $q_i$ we find
\[ +1 = \prod_j \left( \frac{p_i^{e_i}}{q_i} \right) = (-1)^{e_i} \]
so $e_i$ must be even.
This holds for every $i$ though!
In other words all $e_i$ are even.
Hence $(\spadesuit)$ gives solutions to $X^2 + b = Y^2$,
which obviously has only finitely many solutions.
\end{proof}
We now commit to choosing any $k \ge 1$ such that
\[ k \equiv -\frac{1}{q_1q_2 \dots q_m} \pmod{n} \]
which in particular means $\gcd(k,n) = 1$.
Now as long as $a \equiv 1 \pmod n$,
we have $Q(0) \equiv 0 \pmod n$, as needed.
%\begin{claim*}
% [Hensel]
% There are infinitely many integers $a$
% with $a^2 \equiv -b \pmod n$.
%\end{claim*}
%\begin{proof}
% It suffices to fix $i$ and prove
% $-b$ is a quadratic residue mod $p_i^e$ for $e \ge 1$.
%
% By construction, $-b \equiv (q_1 \dots q_m)^2 \pmod{p_i}$
% is a nonzero quadratic residue modulo $p_i$,
% i.e.\ there is a solution to $a^2 \equiv -b \pmod{p_i}$.
% This implies the result for $e \ge 2$ as well,
% either by quoting Hensel lemma (since $p_i \nmid b$),
% or by quoting the fact that odd prime powers have primitive roots.
%\end{proof}
All that remains is to take $a$ satisfying the second claim
larger than any of the finitely many bad integers in the fist claim.
%(The condition $\gcd(b,n) = 1$ holds by construction,
%and $\gcd(a,n) = 1$ follows automatically.)
\begin{remark*}
[Motivational comments from Nikolai Beluhov]
The solution I ended up with is not particularly long or complicated,
but it was absurdly difficult to find.
The main issue I think is that there is nothing in the problem to latch onto;
no obvious place from which you can start unspooling the yarn.
So what I did was throw an awful lot of different strategies at it until one stuck.
Eventually, what led me to the solution was something like this.
I decided to focus on the simplest nontrivial case, when $n$ contains just two primes.
I spent some time thinking about this,
and then at some point I remembered that in similar Diophantine equations I've seen before,
like $2^x + 3^y = z^2$ or $3^x + 4^y = 5^z$,
the main trick is first of all to prove that the exponents are even.
After that, we can rearrange and factor a difference of squares.
This idea turned out to be fairly straightforward to implement,
and this is how I found the solution above.
\end{remark*}
\begin{remark*}
[The problem is OK with $n$ even]
The problem works equally well for $n$ even,
but the modifications are both straightforward and annoying,
so we imposed $n$ odd to reduce the time taken in solving this problem
under exam conditions.
On the other hand, for odd $n$,
one finds that a simplified approach is possible
where one proves the main argument
by choosing $b \equiv 2 \pmod 4$
and then using the quadratic reciprocity argument
to force the right-hand side of $(\spadesuit)$ to be $1 \pmod 4$.
In this case, there are no integers $X$ at all satisfying $(\spadesuit)$,
and the ``sufficiently large'' leverage provided by
the choice of $a$ is not needed.
\end{remark*}
\begin{remark*}
[On the choice of conditions]
The equation $(\spadesuit)$,
and the goal to show it has finitely many solutions (or no solutions),
is the heart of the problem.
But the other conditions have been
carefully chosen to prevent two ``trivial'' constructions to this.
If the condition that $\gcd(a,n) = \gcd(b,n) = 1$ or $n \mid Q(0)$ is dropped,
the problem becomes much easier because
one can simply ensure that $\nu_p(Q(x))$ is bounded for all $p \mid n$,
by taking $b = n$ (or $b = \opname{rad} n$, etc.).
However, these two conditions jointly together
ensure that $\nu_p(Q(x))$ may be unbounded,
by a Hensel-type argument.
If $b < 0$ is permitted, an easier approach to make sure that $Q(x)$
factors as the product of two polynomials
by requiring $b$ to be the negative of a perfect square.
Several easier approaches become possible in this situation.
For example, one can try to use Kobayashi's theorem to generate the value of $a$
after ensuring the first two conditions are true.
\end{remark*}
\begin{remark*}
[Author remarks on generalization]
In general, it seems like \emph{any} $b$ satisfying $\gcd(b,n) = 1$
should still have finitely many solutions to $(\spadesuit)$.
The author comments that this would be a statement of Kobayashi's theorem
in the ring of integers of the quadratic field $\QQ(\sqrt{-b})$,
but the organizers of the competition
were not able to locate such a statement in the literature.
\end{remark*}
\end{document}