\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/5a\_XCGKiXnI}}

\section*{External Link}
\url{https://aops.com/community/p18486965}

\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, \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})$.

  A confirmation this (and much more) is indeed true
  is given by user \texttt{Loppukilpailija} at
  \url{https://aops.com/community/p18545077}.
  An excerpt from this post goes:
  \begin{quote}
    If there are infinitely many $x$ which do not have this property,
    by the pigeonhole principle there is some integer $c$ with $\opname{rad}(c) \mid n$
    and $\nu_p(c) \le 2$ for all primes $p$ such that the equation $Q(x) = cy^3$
    has infinitely many solutions.
    This rearranges to the polynomial $cy^3 - b$ attaining infinitely many square values.
    Since $b \neq 0$, the roots of $cy^3 - b$ are simple.
    This contradicts Theorem 3 of the paper starting at page 381
    of \url{https://www.mathunion.org/fileadmin/ICM/Proceedings/ICM1978.1/ICM1978.1.ocr.pdf}.

    In general, the results presented in the linked article are,
    together with elementary arguments,
    enough to characterize all polynomials which attain infinitely
    many perfect powers as their values. (Exercise!)
  \end{quote}
\end{remark*}

\end{document}
