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

\begin{document}
\title{Longlist 1974/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 121}
\maketitle

\section*{Problem}
Let $u_n$ be the Fibonacci sequence,
i.e., $u_0=0$, $u_1=1$, $u_n=u_{n-1}+u_{n-2}$ for $n>1$.
Prove that there exist infinitely many prime numbers $p$ that divide $u_{p-1}$.

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

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

\newpage

\section*{Solution}
Let $\alpha = \half(1+\sqrt5)$ and $\beta = \half(1-\sqrt5)$.
We have Binet's formula:
\[ u_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}. \]
In fact, if $p \equiv 1 \pmod 5$, then by quadratic reciprocity,
$5$ is a quadratic residue, so $\alpha$ and $\beta$
can be viewed as elements of $\FF_p$, and Fermat's theorem applies to give
$\alpha^{p-1} \equiv \beta^{p-1} \equiv 1 \pmod p$, as desired.

\begin{remark*}
In fact, if $p \equiv \pm 2 \pmod 5$ and $p > 2$
then $\alpha^p = \beta$ and $\beta^p = \alpha$, so in this case
\[ u_{p-1}
  \equiv \frac{\frac{\beta}{\alpha}-\frac{\alpha}{\beta}}{\alpha-\beta}
  = -\frac{\alpha+\beta}{\alpha \beta} = -\frac{-1}{1} = 1 \pmod p. \]
\end{remark*}

\end{document}
