If $n \mid a^n - 1$, prove $ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ are distinct $ \bmod n $.

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$.

1. If $a \equiv 1 \pmod{m_r}$, set $j = r$ and exit this set of steps.
2. 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}$.
3. 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$.

4. 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$.
5. If $r = 1$, since $m_1 = n$, exit these steps.
6. 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}$.
7. 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).