I claim $n$ is fabulous unless it is a power of 2. If $n$ is odd, then it suffices to choose $a=n-1$, so that $a^n-a\equiv (-1)^n-(-1)\equiv 0\pmod{n}$. Suppose now that $n$ is even, let $n=2^k\cdot u$ for $k\ge 1$ and $u$ odd. Assume $u>1$. Choose $a$ such that $a\equiv 1\pmod{u}$ and $a\equiv 0\pmod{2^k}$. Such an $a$ exists due to CRT, furthermore it is clearly not equal to 1, and it is not 0 modulo $n$ either, since $u>1$. With this, $n\mid a^-a$. We now show powers of two do not work. Assume the contrary, let $2^k\mid a^{2^k}-a$. If $a$ is even, then $v_2(a^{2^k}-a) = v_2(a)$, so $a\ge 2^k$. Now, let $a$ be odd. We have $2^k\mid a(a-1)(a^{m-2}+\cdots+1)$ for $m=2^k$. As $a$ and $a^{m-2}+\cdots+1$ are simultaneously odd, we must have $2^k\mid a-1$, impossible

The fabulous numbers are all $n\in Z_{\geq 3}$ that are not powers of two. First, let’s prove why a power of two can’t be fabulous. Suppose it could. So, $\exists 2\leq a\leq n-1$ such that $n= 2^k\mid a^{2^k}-a$, $k\in Z_{>0}$. So, $2^k\mid a(a^{2^k-1}-1)\implies 2^k\mid a(a-1)(a^{2^k-2}+a^{2^k-3}+...+a^2+a+1)$. Notice that $(a^{2^k-2}+a^{2^k-3}+...+a^2+a+1)$ has $(2^{k}-2)$ factors $a^j$, which means $(a^{2^k-2}+a^{2^k-3}+...+a^2+a+1)$ is odd. So, $2^k\nmid (a^{2^k-2}+a^{2^k-3}+...+a^2+a+1)$. This means that we must have $2^k\mid a(a-1)$. As $gcd(a, a-1)= 1\implies 2^k\mid a$ or $2^k\mid a-1$. In both cases, we would have $2^k\leq a\leq n-1= 2^k-1 \implies 2^k\leq 2^k-1$, which is impossible! Therefore, $2^k$ can’t be fabulous. Let’s now prove that the other numbers are fabulous. If $n= p$, where p is a prime, it obviously works, by the Little Fermat Theorem If $n=p^x$, where p is an odd prime and $x\in Z_{>0}$. So $n$ is odd and we just have to choose $a= n-1\implies a^{p^x}-a\equiv (-1)^{p^x} - (-1)\equiv -1+1\equiv 0 (mod n)$. Actually, this works for every $n$ odd, but whatever. If $n= P_1^{\alpha_1}P_2^{\alpha_2}...P_m^{\alpha_m}$, then it ensures the congruence below: $$a\equiv 0 (mod P_1^{\alpha_1})$$$$a\equiv 1 (mod P_2^{\alpha_2}...P_m^{\alpha_m})$$which has a solution 'a' $mod P_1^{\alpha_1}P_2^{\alpha_2}...P_m^{\alpha_m}$, by the Chinese Remainder Theorem and we would have $n\mid a(a-1)$. Well, it’s easy to show that a can’t be 0 (or n) or 1 modulo $P_1^{\alpha_1}P_2^{\alpha_2}...P_m^{\alpha_m}$, because if a= 0, then $a\equiv 0 (mod P_2^{\alpha_2}...P_m^{\alpha_m}$, which is not true. And, if a= 1, then $a\not\equiv 0 (mod P_1^{\alpha_1})$, which is also not true. So, we can’t have a= 0 (or n) or 1, so it ensures $2\leq a\leq n-1$ and we’re done

Here is another solution: As I proved above that powers of two don't work, I will not prove again, and this is the other way: Let $n= 2^k\cdot I$, where $2^k\mid\mid n$, $I$ is odd, $k\in\mathbb{Z^*_+}$ Well, as $n\mid a^n-a\implies 2^k\mid a^n-a$, so $v_2(a^n-a)\geq k\implies v_2(a)+v_2(a^{n-1}-1)\geq k\implies \begin{cases} \mbox{a is odd}&\implies v_2(a-1)\geq k \\ \mbox{a is even}&\implies v_2(a)\geq k\end{cases}$. Let's make this even simpler: If $a= 2^k\cdot x+1$, where $x\in\mathbb{Z^*_+}$, then $2^k$ divides $a^n-a$ But, suppose $I\mid 2^k\cdot x+1\iff 2^kx\equiv -1\mbox{(mod I)}$. As $gcd(2^k, I)= 1$,exists $y\in\{0, 1,2,3, \dots, I-1\}$ such that $2^k\cdot y\equiv 1\mbox {(mod I)}$. So, it's enough to choose $x\equiv -y \mbox{(mod I)}$. And also, as $x$ is a residue modulo $I$, then $x\in\{0, 1,2,3, \dots, I-1\}$. If $x= 0$, then $I\mid 1$, false, and $2^k\cdot x+1\leq 2^k(I-1)+1= 2^k\cdot I- 2^k+1= 2^k\cdot I - (2^k-1)\leq 2^k\cdot I-1$. This holds the inequality given.

We claim that $n$ is fabulous if and only if $n \neq 2^k$ for $k \geq 1$. Now suppose if $n=2^k$ works, note that $a$ must be odd. Note that if $n \equiv 3 \pmod{4}$, $a^{2^k-1} \equiv 3 \pmod{4}$ which is impossible since $a^{2^k-1} \equiv 1 \pmod{4}$ (since $\gcd(a, 2) = 1$), this means that $a \equiv 1 \pmod{4}$. Now, $\nu_2(a^{2^k-1} - 1) = \nu_2 (a-1) + \nu_2 (2^{k}-1) = \nu_2 (a-1) < k$, contradiction. Now for the construction, if $n$ is odd, just pick $a = n-1$. If $n=2^km$ where $\gcd(m, 2) = 1$, pick $n \equiv 0 \pmod{2^k}$ and $n \equiv 1 \pmod{m}$ and we are done by CRT. $\blacksquare$

We claim that an integer $n$ is fabulous if and only if it is not a power of 2. First, consider a positive integer $n=2^k$ for some integer $k \geq 2$. For all even $a<n$, we know that $\nu_2(a)<k$. Then, it is quite clear that, \[\nu_2(a^n-a)= \nu_2(a) + \nu_2(a^{n-1}-1) = \nu_2(a)<k\]since $a^{n-1}-1$ is clear odd (we know $n>2$). Thus, $n \nmid a^n-a$ for all even integers $2\leq a<n$. Then, by Euler's Generalization of Fermat's Little Theorem, we know that for all odd $a$, \[a^{2^{k-1}} = a^{\phi(2^k)} \equiv 1 \pmod{n} \]But then, quite clearly, \[a^n \equiv 1 \not \equiv a \pmod{n}\]for all odd integers $1<a<n$. Thus, all powers of two are not fabulous, as desired. Now, consider an integer $n\geq 3$ which is odd. Then, let $a=n-1$. We note that, \[a^n-a \equiv (n-1)^n - (n-1) \equiv (-1)^n - (-1) \equiv -1 +1 \equiv 0 \pmod{n}\]for this choice of $a$. Thus, all odd integers are fabulous. Now, consider an integer $n=2^km$ for $k\geq 1$ and $m>1$. Then, we choose $a$ such that $a \equiv 1 \pmod{m}$ and $a \equiv 0 \pmod{2^k}$. By CRT, such an $a < 2^km=n$ exists. Further, note that, \[a^n-a \equiv 1^n -1 \equiv 1 -1 \equiv 0 \pmod{m}\]for this choice of $a$ and \[\nu_2(a^n-a) = \nu_2(a) + \nu_a(a^{n-1}-1) \geq k\]Thus, $2^k \mid a^n-a$ also for this choice of $a$. This implies that indeed there exists an integer $a$ such that $1\leq a \leq n-1$ for which $a^n-a$ is divisible by $n$ for all positive integers $n$ which are not powers of two as claimed.

Claim: $n$ is $fabulous\iff n\neq 2^{k}; \forall k\in\mathbb{N}.$ Proof: Let $n=2^{\alpha}\cdot I, 2\nmid I$ and $P(x)=x^{n}-x$. $$P(x)=x(x^{n-1}-1)=x(x-1)(x^{n-2}+\dots+1)=x(x-1)G(x)$$ Suppose $I>1$. If $\alpha=0$ we just take $x=n-1$ as $(-1)^n-(-1)\equiv 0 \ (mod \ n).$ If $\alpha\geq 1$ it suffices to show that there exists $x$ such that $\begin{cases}x\equiv0 \ (mod \ 2^\alpha) \\ x\equiv1 \ (mod \ I)\end{cases}$

If $I=1$ we have $n=2^\alpha$. This implies that $G(x)\equiv (n-2)x+1\equiv 1 \ (mod \ 2)$. Therefore $2^\alpha\mid P(x)\iff 2^\alpha\mid x(x-1)$, but $gcd(x; x-1)=1$, so $2^\alpha\mid x$ or $2^\alpha\mid (x-1)$. But in both cases we need $x\geq n$. Thus completing the proof.

First, we prove powers of $2$ fail. Let $n = 2^k$. If $a$ is even, note $v_2(a^n - a) = \text{min}(nv_2(a), v_2(a)) = v_2(a)$. Note that $v_2(a) < v_2(n)$, a contradiction. If $a$ is odd, we first note that $a^{2^k} \equiv 1\mod{2^k}$ since $\phi(2^k) = 2^{k - 1} \mid 2^k$, which means $a \equiv 1\mod{2^k}$, a contradiction since this means $a > n$. So, powers of $2$ fail. We now prove all other numbers work. When $n$ is odd, just take $a = n - 1$. When $v_2(n) = 1$, take $a = \frac{n}{2}$, and we get $2 \mid a^n - a$ since $a$ is odd, $\frac{n}{2} \mid a^n - a$, and since $\gcd(\frac{n}{2}, 2) = 1$, $n \mid a^n - n$. Say we have $n = 2^{\alpha}\cdot k $, where $k \neq 1$, $\alpha \geq 2, \alpha = v_2(n)$. Clearly $k$ is odd. Consider the modular inverse $m$ of $k$ such that $mk \equiv 1 \mod{2^{\alpha}}$. Since $1 \leq m \leq (2^{\alpha} - 1)$, $mk < n$, $mk \neq 1$. Take $a = mk$. We have: $$k \mid a^n - a$$Note that $(mk)^{n} \equiv 1\mod{2^{\alpha}}, mk \equiv 1\mod{2^{\alpha}} \implies 2^{\alpha} \mid a^n - a$. Since $\gcd(k, 2^{\alpha}) = 1$, $k\cdot2^{\alpha} = n \mid a^n - a$, done.