\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Italy TST 2006/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 67}
\maketitle
\section*{Problem}
Let $n$ be a positive integer, and let $A_{n}$ be the set of all
positive integers $a\le n$ such that $n \mid a^{n}+1$.
\begin{enumerate}[(a)]
\ii Find all $n$ such that $A_{n}\neq \emptyset$.
\ii Find all $n$ such that $|{A_{n}}|$ is even and non-zero.
\ii Is there $n$ such that $|{A_{n}}| = 130$?
\end{enumerate}
\section*{Video}
\href{https://www.youtube.com/watch?v=YBS-zrNl1O4&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/YBS-zrNl1O4}}
\newpage
\section*{Solution}
\textbf{Part (a)}:
The answer is odd $n$ and even $n$ with $\nu_2(n) \le 1$
and only $1 \bmod 4$ prime factors.
\begin{itemize}
\ii For odd $n$, let $a = n-1$ for a construction.
\ii For even $n$, the right-hand side is a sum of two squares,
one of which is odd.
So $\nu_2(n) \le 1$ and the $1 \bmod 4$ condition are both needed.
Conversely,
we can choose $n$ to be a square root of $-1$
modulo each prime power dividing $n$; this works.
\end{itemize}
\textbf{Part (b)}:
The answer is all even numbers in (a) other than $n=2$.
As for evenness:
\begin{itemize}
\ii When $n$ is even, pairing $a$ and $-a$ implies $|A_n|$ even, except $n=2$
(the only time $n \mid (n/2)^n+1$).
\ii When $n$ is odd, the number of solutions to $a^n \equiv -1 \pmod{p^e}$
for odd prime power $p^e$ is odd: $a \equiv -1$ is a solution,
$a \equiv 1$ is not, and any other solutions come in pairs $\{a,1/a\}$.
\end{itemize}
\textbf{Part (c)}: No.
If such $n$ existed, by (b) it is even.
\begin{itemize}
\ii If $n$ has more than one distinct odd prime factor,
then $|A_n|$ is divisible by four, by Chinese remainder theorem.
\ii For $n = 2p^e$,
\[ a^{2p^e} \equiv -1 \pmod{p^e} \]
We have a primitive root, of order $(p-1) \cdot p^{e-1}$.
So there are $2p^{e-1}$ solutions.
\end{itemize}
Neither case coincides with $130$, end proof.
\end{document}