\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Poland 2019/1/12}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 100}
\maketitle

\section*{Problem}
Let all numbers of form $x^2+y^2$
where $x$, $y$ are coprime integers
be arranged in a sequence $z_1 < z_2 < z_3 < \dotsb$.
(So the sequence begins $z_1=2=1^1+1^2$, $z_2=5=1^2+2^2$,
$z_3=10=1^2+3^2$, $z_4=13=2^2+3^2$.)
Prove that there exist infinitely many values of
$n$ such that $z_n$, $z_{n+1}$, \dots, $z_{n+2019}$ are odd.

\section*{Video}
\href{https://www.youtube.com/watch?v=8edyF716Mr8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/8edyF716Mr8}}

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

\newpage

\section*{Solution}
Call numbers in the sequence \emph{good},
and the other positive integers \emph{bad}.
We will need the following number theoretic facts.
\begin{claim*}
  Any number with a $3 \bmod 4$ factor is bad.
\end{claim*}
\begin{proof}
  Follows directly from Fermat's Christmas theorem
  or quadratic reciprocity.
\end{proof}
\begin{claim*}
  Let $t$ be a positive integer which is not a perfect square.
  Then there exists infinitely many primes $p$
  such that $p \equiv 3 \pmod 4$
  and $-t$ is a quadratic residue modulo $p$.
\end{claim*}
\begin{proof}
  By using quadratic reciprocity to show that
  some residue class works out, then using Dirichlet's theorem.
\end{proof}

Pick $2020$ odd primes $q_0 < q_1 < \dots < q_{2019}$.
We will find a positive integer $A$ such that
\begin{itemize}
  \ii $A^2+q_0^2$, $A^2 + q_1^2$, \dots, $A^2 + q_{2019}^2$
  are all good.
  \ii $A^2+2$, $A^2+4$, $A^2+6$, \dots, $A^2+(q_{2019}^2-1)$
  are all bad.
\end{itemize}
This takes three steps:
\begin{enumerate}
  \ii We require $A \perp q_0 q_1 \dots q_{2019}$.
  This guarantees the goodness of $A^2 + q_i^2$.
  \ii We require $2 \mid A$.
  This means $A^2 + s^2$ is bad for any even integer $s$.
  \ii For each even non-square $t$ in $[2, q_{2019}^2-1]$,
  we pick a prime $p_t$, different from any previously chosen prime,
  such that $-t$ is a quadratic residue modulo $p_t$
  and $p_t \equiv 3 \pmod 4$.
  Then we require $A+t \equiv 0 \pmod{p_t}$;
  this guarantees $A+t$ is bad.
\end{enumerate}

\end{document}
