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

\begin{document}
\title{China 2023/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 110}
\maketitle

\section*{Problem}
Prove that there exists a constant $C>0$ such that:
if $a_1 < a_2 < a_3 < \dotsb$ is an arithmetic sequence of positive integers
for which $\gcd(a_1, a_2)$ is squarefree,
then there exists a positive integer $m \le (C a_2)^2$
such that $a_m$ is squarefree.

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

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

\newpage

\section*{Solution}
Classify primes into three types:
\begin{itemize}
\ii If a prime $p$ has $p^2 \mid a_2 - a_1$,
or if $p \mid a_2 - a_1$ but not $\gcd(a_1, a_2)$,
then the prime is \emph{completely harmless};
no term of the sequence is divisible by $p^2$

\ii If $p \nmid a_2 - a_1$,
then we say $p$ is \alert{mostly harmless}.

\ii Otherwise, if $p \mid \gcd(a_1, a_2)$
and $\nu_p(a_2 - a_1) = 1$; we say $p$ is \alert{scary}.
\end{itemize}

Let $D = \prod \left( \text{scary $p$} \right) \le |a_2-a_1| < a_2$.
Say a term $a_i$ is \emph{good} if it's not divisible by
the square of any scary prime.
\begin{claim*}
  Among any $D$ consecutive terms of $(a_n)_n$,
  exactly $\varphi(D)$ are good.
\end{claim*}

\begin{claim*}
  If $p$ is a mostly harmless prime,
  among any $p^2 \cdot D$ consecutive terms,
  exactly $\varphi(D)$ good ones satisfy $p^2 \mid a_i$.
\end{claim*}
\begin{proof}
  By Chinese remainder theorem.
\end{proof}

Let $N$ be large and consider only the terms $a_1$, \dots, $a_N$ henceforth.
If $p$ is a mostly harmless prime with $p < \sqrt N$,
the number of good terms divisible by $p^2$ is at most
$\varphi(D) \left\lceil \frac{N}{p^2 D} \right\rceil$.
On the other hand, if $\sqrt{N} \le p \le \sqrt{a_N}$,
the number of terms divisible by $p^2$ is at most $1$, full stop.
And if $p > \sqrt{a_N}$, then $p^2$ can't divide any terms.
Therefore, the number of not-squarefree good terms is bounded by
\begin{align*}
  &\phantom{<} \sum_{p < \sqrt N}
  \left( \varphi(D) \cdot \left\lceil \frac{N}{p^2 D} \right\rceil \right)
  + \sum_{\sqrt N \le p \le \sqrt{a_N}} 1 \\
  &< \frac{\varphi(D)}{D} N \sum_{p}
    \frac{1}{p^2} +
    \left( \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right)
    + O\left( \frac{\sqrt{ND}}{\log(ND)} \right) \right) \\
  &< \frac{\varphi(D)}{2D} N
    + \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right)
\end{align*}
where we have used three well-known facts:
$\sum_{\text{$p$ prime}} p^{-2} < \half$,
the prime number theorem,
and the inequality $0.01 \sqrt D \le \varphi(D)$
which is valid for any $D \ge 1$ (and is proved by
multiplicativity of $\varphi(x)/x$, and checking at prime powers).

On the other hand, the number of good terms was at least
\[ \varphi(D) \cdot \left\lfloor \frac{N}{D} \right\rfloor
  > \frac{\varphi(D)}{D} N - \varphi(D) \]

So we will have a squarefree term as long as
\[ \frac{\varphi(D)}{2D} N >
  \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right) \]
which is certainly true if $N > O(\sqrt{D})$.
As $D < a_2$, we're done.

\end{document}
