Proving a complete residue from $n | a^n-1$ The problem is very simple. Given $n,a \in \mathbb {N}$ that $n|a^n-1$, then prove that:
\begin{align}
\{a^i+i | 1 \le i \le n \}
\end{align}
forms a complete residue modulo $n$
My approaches
Obviously for $n=p$ then $1\equiv a^n \equiv a$ (mod $n$) and thus the set equals $\{i+1|1\le i \le n\}$ which yields a complete residue.
Now the case for $n=pq$ is also provable (and you may find $n=p^\alpha q^\beta$ staggeringly similar with slight adjustments)
Denote $a \equiv b$ (mod $x$) as $a\equiv b [x]$
Indeed, $pq|(a^p)^q-1$, hence, $q|a^p-1$ and $p|a^q-1$. Using $ord_p$, we have $p \equiv 1 [q]$ and $q \equiv 1 [p]$, which means either $p=q$ or $a\equiv 1 [pq]$
What I'm trying to do here is to use induction over the number of primes that are divided by n. But moving from 2 to 3 (primes) is already extremely difficult, let alone from $k$ to $k+1$.
Is my approach correct, or should it be revised? Any help is appreciated!
 A: It suffices to show that, for $i\not\equiv j \pmod n$, we have $a^i + i \not\equiv a^j + j \pmod n$.
We first prove a
Lemma: Let $a, n$ be positive integers such that $n \mid a^n - 1$. Suppose $n > 1$. Let $p$ be the largest prime divisor of $n$ and write $n = p^e m$ with $p\nmid m$. Then we have:

*

*$p\mid a^m - 1$;

*$m \mid a^m - 1$.

Proof:

*

*By Fermat, we have $a \equiv a^{p^e} \pmod p$. Raising to $m$-th power, we get $a^m \equiv a^n \equiv 1\pmod p$.


*Let $d$ be the order of $a \pmod m$. Fermat–Euler tells us that $d \mid \phi(m)$. On the other hand, $m \mid a^n - 1$ implies $d\mid n$. But all prime factors of $\phi(m)$ are strictly smaller than $p$, thus we must have $d \mid \frac n{p^e} = m$, which leads to $m \mid a^m - 1$.
For the main result, we will prove by induction on the number of prime factors of $n$.
Thus we let $p$ be the largest prime divisor of $n$ and write $n = p^e m$. Suppose that there exist $i, j$ such that $a^i + i \equiv a^j + j\pmod n$.
By the lemma, the induction hypothesis can be applied to $m$ and gives $i \equiv j \pmod m$, i.e. $m \mid i - j$.
We now show by induction that $p^k \mid i - j$ for $1 \leq k \leq e$.

For $k = 1$, it follows from the lemma that $p \mid a^{i - j} - 1$, and hence $p\mid i - j$.
Assume that $p^k\mid i - j$ for some $k < e$ and we want to prove that $p^{k + 1}\mid i - j$.
Since $p$ is prime to $m$, we have $m \mid \frac{i - j}{p^k}$ and hence $p \mid a^{\frac{i - j}{p^k}} - 1$. It follows that $p^{k + 1} \mid a^{i - j} - 1$ and hence $p^{k + 1} \mid i - j$.

Thus we have proved that $i \equiv j \pmod n$.
