Problem: A sequence $a_1$, $a_2$, \dots\ of positive integers is defined recursively by
$a_1 = 2$ and \[ a_{n+1} = a_n^{n+1} - 1 \qquad \text{ for } n \ge 1. \]
Prove that for every odd prime $p$ and integer $k$,
some term of the sequence is divisible by $p^k$.

Solution: We start with the following.
\begin{claim*}
  Assume $n$ is a positive integer divisible by $p-1$.
  Then either $a_{n-1} \equiv 0 \pmod p$ or $a_n \equiv 0 \pmod p$.
\end{claim*}
\begin{proof}
  Suppose that $a_{n-1} \not\equiv 0 \pmod p$.
  Then by Fermat's little theorem,
  \[ a_n = a_{n-1}^n - 1 \equiv x^{p-1} - 1 \equiv 0 \pmod p \]
  where $x \coloneq a_{n-1}^{\frac{n}{p-1}}$ is an integer not divisible by $p$.
\end{proof}

\begin{claim*}
  If $n \ge 2$ is even, then
  \[ a_{n}^{n+1} \mid a_{n+2}. \]
\end{claim*}
\begin{proof}
  Note $a_{n+2} = a_{n+1}^{n+2} - 1$.
  The right-hand side is a difference of $(n+2)$\ts{nd} powers,
  which for even $n$ is divisible by $a_{n+1} + 1 = a_{n}^{n+1}$.
\end{proof}

By considering multiples $n$ of $p-1$ which are larger than $k$,
we see that if $a_n \equiv 0 \pmod p$ ever happens,
we are done by combining the two previous claims.
So the difficult case of the problem is the bad situation
where $a_{n-1} \equiv 0 \pmod p$ occurs for almost all $n \equiv 0 \pmod{p-1}$.

To resolve the difficult case and finish the problem,
we zoom in on specific $n$ that will let us use lifting the exponent on $a_{n-1}$.
\begin{claim*}
  Suppose $n$ is an (even) integer satisfying
  \begin{align*}
    n &\equiv 0 \pmod{p-1} \\
    n &\equiv 1 \pmod{p^{k-1}}.
  \end{align*}
  If $a_{n-1} \equiv 0 \pmod p$, then in fact $p^k \mid a_{n-1}$.
\end{claim*}
\begin{proof}
  Write $a_{n-1} = a_{n-2}^{n-1} - 1$.
  We know $a_{n-2} \not\equiv 0 \pmod p$, and so $a_{n-2}^n \equiv 1 \pmod p$.
  Taking modulo $p$ gives
  \[ 0 \equiv \frac{1}{a_{n-2}} - 1 \pmod p \implies a_{n-2} \equiv 1 \pmod p. \]
  Hence lifting the exponent applies and we get
  \[ \nu_p(a_{n-1}) \equiv \nu_p \left( a_{n-2}^{n-1} - 1 \right)
    = \nu_p(a_{n-2}-1) + \nu_p(n-1) \geq 1 + (k-1) = k \]
  as desired.
\end{proof}

\begin{remark*}
  The first few terms are $a_1=2$, $a_2=3$, $a_3=26$, $a_4=456975$,
  and $a_5 = 19927930852449199486318359374$, \dots.
  No element of the sequence is divisible by $4$:
  the residues modulo $4$ alternate between $2$ and $3$.
\end{remark*}

\begin{remark*}
  The second claim is important for the solution to work once $k \ge 2$.
  One could imagine a variation of the first claim that states
  if $n$ is divisible by $\varphi(p^k) = p^{k-1}(p-1)$,
  then either $a_{n-1} \equiv 0 \pmod p$ or $a_n \equiv 0 \pmod{p^k}$.
  However this gives an obstruction (for $k \ge 2$)
  where we are guaranteed to have $n-1 \not\equiv 0 \pmod p$ now,
  so lifting the exponent will never give additional factors of $p$ we want.
\end{remark*}