If $n \mid a^n - 1$, prove $ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ are distinct $ \bmod n $. I have tried the following problem:

Let $ a $ and $ n $ be two natural numbers for which $ n \mid a^n - 1 $. Prove that $ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ are distinct $ \bmod n $.

I am thinking about induction (obviously), maybe element's order (elementary number theory). I don't have an idea to follow. The problem has been chosen for a junior math course, from the book:

<< Mathematical Induction: A Powerful and Elegant Method of Proof >>
Andreescu Titu, Crișan Vlad, XYZ Press, 2017.

 A: This is a quite interesting question, as well as a fairly challenging one for a junior math course. If $n = 1$, then any $a$ works, giving $a + 1 \equiv 0 \pmod{1}$. Otherwise for $n \gt 1$, the following set of steps shows using multiplicative orders there's a set of decreasing factors of $n$ until $a \equiv 1$ modulo some factor. Start with $m_1 = n$ and $r = 1$.

*

*If $a \equiv 1 \pmod{m_r}$, set $j = r$ and exit this set of steps.

*Let the multiplicative order of $a$ modulo $m_r$ be $m_{r+1} = \operatorname{ord}_{m_{r}}(a) \gt 1$. Since $a^{m_r} \equiv 1 \pmod{m_r}$, then $m_{r+1} \mid m_{r}$. Along with $a^{m_{r+1}} \equiv 1 \pmod{m_{r}}$, this means $a^{m_{r+1}} \equiv 1 \pmod{m_{r+1}}$. In addition, with Euler's totient function, since $m_{r+1} \mid \varphi(m_r)$ and $\varphi(m_r) \lt m_r$, we get $m_{r+1} \lt m_{r}$.

*Increment $r$ and go to step #$1$.

Since each $m_r$ is decreasing, but must be $\gt 1$, the procedure above must eventually exit, i.e., there's a $j \ge 1$. The following set of steps shows for each $m_r \; \forall \; 1 \le r \le j$ that each $a^i + i \; \forall \; 1 \le i \le m_r$ is unique $\bmod m_r$.


*From step #$1$, since $a \equiv 1 \pmod{m_j}$, we have $a^{i} + i \equiv 1 + i \pmod{m_j} \; \forall \; i$. This means $a^i + i \; \forall \; 1 \le i \le m_{j}$ is distinct $\bmod m_j$. Set $r = j$.

*If $r = 1$, since $m_1 = n$, exit these steps.

*For any $k \ge 1$, consider any $s \gt k$ where $a^{k} + k \equiv a^{s} + s \pmod{m_{r-1}}$. Note they also must be congruent to each other modulo $m_r$ since $m_r \mid m_{r-1}$. Since $a^{i} + i \; \forall \; 1 \le i \le m_{r}$ are all distinct $\bmod m_r$, then $s \equiv k \pmod{m_{r}}$. Thus, $s = qm_{r} + k$ for some integer $q \ge 1$. Using $a^{m_{r}} \equiv 1 \pmod{m_{r-1}}$, then $a^{s} + s \equiv a^{qm_{r} + k} + qm_{r} + k \equiv a^k + qm_{r} + k \pmod{m_{r-1}}$. This gives $qm_{r} \equiv 0 \pmod{m_{r-1}}$, i.e., for some $t \ge 1$, we have $s = tm_{r-1} + k$. This means the values repeat each $m_{r-1}$, so $a^{i} + i \; \forall \; 1 \le i \le m_{r-1}$ must be distinct $\bmod m_{r-1}$.

*Decrement $r$ and go to step #$5$.

Since $r$ is being decremented each time at step #$7$, $r$ must eventually become $1$ so the procedure exits at step #$5$, with a result as explained in step #$4$ or the end of step #$6$, i.e., each $a^{i} + i \; \forall \; 1 \le i \le n$ are distinct $\bmod n$.
An example is $n = 18$ and $a = 5$. This gives $m_1 = 18$, $m_2 = 6$ and $m_3 = 2$, so $j = 3$.
Note the loop in steps #$1$ to $3$ increments $r$ each time, while the loop in steps #$5$ to $7$ decrements $r$ each time, making them both similar to induction (I chose to use loops instead since I thought it would be simpler to explain & easier to understand than using induction with various extra conditions to check).

Update: This answer's approach is more complicated than need be. Instead of iteratively using the multiplicative order to decrease the value being checked until $a \equiv 1$, strong induction can be more simply used instead with the initial multiplicative order, as done in MikeTex's answer here and in Tintarn's answer in a duplicate question.
A: Probably the same as the previous answers, but written in an understandable form for the small reader.
Let $a\in \mathbb N$ and assume the result true by induction up to rank n = K (it is clearly for $n=1$ and $n=2$). Let $N = K+1$.
Assume $a^N = 1 \pmod N$ (otherwise the result is obviously true at rank $K+1$ by void condition).
Let $n = ord_N(a)$. Then $n < N$, and $$a^n = 1 \pmod N = 1 \pmod n.$$
If $$a^i +i = a^j +j \pmod N,\quad\quad \quad(1)$$
there holds
$$a^i + i = a^j + j \pmod n$$
hence $i = j \pmod n$ by the induction hypothesis.
This means $ j = i + k n$, with $k\in \mathbb N$.
Then
$$a^j = a^{i+kn} = a^i (a^n)^k = a^i \pmod N,$$
and $(1)$ implies $i = j\pmod N$.
Note: A necessary condition in order for the hypothesis $n | a^n - 1$ to hold is that $n$ not be square free.
Indeed, $a^n - 1 = 0 \pmod n$ means that $n$ is a multiple of the period of $a$ modulo $n$, which is a divisor of $\varphi(n)$, with $\varphi$ Euler totient function. In other words, $n$ and $\varphi(n)$ must have a non trivial common factor.
But if $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ is the prime factorization of $n$, it is known that
$$\varphi(n) = (p_1-1)p_1^{\alpha_1 - 1}\cdots (p_k-1)p_k^{\alpha_k - 1}.$$
Hence $n$ and $\varphi(n)$ can have a common factor only if some $\alpha_i > 1$.
A: Below I sketch a nice way to view such inductions - which simplifies comprehension of the  proof.
Let $\,P_N := [\![\, a^N\equiv_N 1\ \,\&\,\ \color{#0a0}{a^j}+\color{#90f}j\equiv_N \color{#0a0}{a^k}+\color{#90f}k\,]\!]\,$ and $\,Q_N := [\![\, j\equiv_N k\,]\!]$
If $\,P_N\,$ is true then $\, \color{#90f}{j\equiv_N k}\!\iff\! \color{#0a0}{a^j\equiv_N a^k}\!\iff\! j\equiv_{n} k,\,$ for $\, n:={\rm ord}_N(a),\,$  by here.
hence $\,P_N\overset{\color{#c00}{(\#)}}\Rightarrow P_{n}\overset{\rm induct}\Longrightarrow Q_{n}\overset{\rm above}\Rightarrow Q_N,\,$ i.e. $\,P_N\Rightarrow Q_N,\,$ as pictured below.  $ $ QED
$$\large \require{AMScd}
\require{rotating}
\begin{CD}
P_n @>\rm \color{c00}{induct} >> Q_n\\
@A \rm I.3\ AA\lower.5ex\smash{\Huge\curvearrowright} @VV \ \rm I.4 V\\
P_N @>> > Q_N
\end{CD}\qquad$$
Note $\,P_N\overset{\color{#c00}{(\#)}}\Rightarrow P_{n}\,$
i.e. $ \begin{align}  &a^N\!\!\equiv_N\! 1\ \,\&\,\ a^j+j\equiv_N\! a^k+k\\
        \Rightarrow \ & a^n\equiv_n 1_{\phantom{|}} \,\&\,\ a^j+j\equiv_n a^k+k \end{align}\,$  by $\, n\! =\!{\rm ord}_N a\Rightarrow a^n\!\equiv_N\! 1\Rightarrow a^n\!\equiv_n\! 1\,$ by congruence persistence at mod factors, by $\,n\mid N\,$ by here; similarly  2nd congruence persists.

Remark $ $ Below is the general induction schema we employed.
Implication Induction $ $ The implication $\, P_N\Rightarrow Q_N\,$ is true for all integers $\,N\ge 1\,$ if
${\rm[\![\,I.1\,]\!]}\ $ it is true for $\,N=1,\,$ i.e. $\,P_1\Rightarrow Q_1\ $ (Base Case)
${\rm[\![\,I.2\,]\!]}\ \ P_N\,$ implies there is a smaller integer $\,n,\,$ i.e. $\,1\le n < N,\,$ such that
$\qquad{\rm[\![\,I.3\,]\!]}\ \ P_N\Rightarrow P_n,\, $ and
$\qquad{\rm[\![\,I.4\,]\!]}\ \ P_N\ \&\ Q_n\Rightarrow Q_N$
