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

\begin{document}
\title{H2716390}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 144}
\maketitle

\section*{Problem}
Let $a$ and $b$ be fixed positive integers.
We say that a prime $p$ is fun if there exists a positive integer $n$
satisfying the following conditions:
\begin{itemize}
  \ii $p$ divides $a^{n!} + b$.
  \ii $p$ divides $a^{(n + 1)!} + b$.
  \ii $p < 2n^2 + 1$.
\end{itemize}
Show that there are finitely many fun primes.

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

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

\newpage

\section*{Solution}
We will consider $n > 2^{100}$, since this adds at most finitely many primes.
We also assume $p \nmid ab$ throughout, as well as $p > b+1$.

Note that we have
\[ a^{n!} \equiv -b \pmod p \implies a^{n!} \not\equiv 1 \pmod p \]
because we assume $p > b+1$.
However, we also get
\[ a^{n \cdot n!} \equiv 1 \pmod p. \]
Thus, if $e$ denotes the order of $a \pmod p$, then $e \nmid n!$,
but $e \nmid n \cdot n!$.
So there exists a prime $q$ with $q \mid n$ such that
\[ \nu_q(n!) < \nu_q(e) \le \nu_q(n!) + \nu_q(n). \]
We also know that
\[ e \mid p-1 < 2n^2. \]

\begin{claim*}
  We have $n = q$.
\end{claim*}
\begin{proof}
  Assume not, meaning $q \le n/2$.
  Start by using the estimate
  \[ n^{2.1} > 2n^2 > q^{\nu_q(e)} \ge q^{\nu_q(n!)+1} \ge q^{\frac nq + 1}. \]
  In particular, we certainly need $n^{2.1} \ge q^3$, so $q < n^{0.7}$.
  Using that, we can further estimate
  \[ n^{2.1} \ge 2^{\frac nq + 1} \ge 2^{n^{0.3} + 1} \]
  which is false for $n > 2^{100}$.
\end{proof}

So $e$ must be a multiple of $n^2$, but $e < 2n^2$, so in fact $e = n^2$ exactly.
That means $p = n^2+1$.
However $p$ and $n$ are both primes, so this is a contradiction.

\begin{remark*}
  The same proof shows there are finitely many fun primes if
  the condition $a,b > 0$ is relaxed to $a$ and $b$ are nonzero integers
  with $b \neq -1$.
\end{remark*}

\end{document}
