Let us consider the equivalent condition $n | a^{n-a} + 1$. Suppose we have such an $n$, let us try to find a prime $p$ co-prime with $n$ such that $np$ also satisfies the divisibility. For this we need $n | a^{np-a} + 1$ and $p | a^{np-a} + 1$. Since we already know $n | a^{n-a} + 1$, the former divisibility is guaranteed if $\frac{np-a}{n-a}$ is an odd integer. We are going to choose $p \equiv 1 \pmod {2(n-a)}$, so that $\frac{np-a}{n-a} = 1 + \frac{n(p-1)}{n-a}$ is indeed odd. We also need $p | a^{np-a} + 1$. By Fermat's little theorem, this is equivalent to $p | a^{n-a} + 1$. Here comes the crucial part: by a version of Zsigmondy's theorem, $a^{n-a} + 1$ contains a "primitive" prime divisor $p$ with $p \equiv 1 \pmod {2(n-a)}$, whenever $n-a \geq a \geq 4$. Moreover, if $n \geq 2a$ then $p > 2(n-a) \geq n$, so $p$ is co-prime with $n$ as desired. Suppose $a \geq 4$, then the above analysis implies that as soon as we find one $n \geq 2a$ such that $n | a^{n-a} + 1$, we can find infinitely many such $n$. To initialize the process, let us choose $n = q$ be a prime factor of $a^{a-1} + 1$. By Fermat, we see that $q | a^{q-a} + 1$. Moreover, by Zsigmondy again we can choose $q$ with $q \equiv 1 \pmod {2a-2}$. Thus $n = q \geq 2a$ unless $q = 2a-1$ is the only primitive prime factor of $a^{a-1} + 1$. If that does happen, we must have $q^2 | a^{a-1} + 1$ because the primitive part of $a^{a-1} + 1$ (which is roughly the value of a cyclotomic polynomial evaluated at $a$) is larger than $q$ for $a \geq 4$. Then from $q^2 | a^{q-a} + 1$ and $q^2 | a^{q^2-q} - 1$, we obtain $q^2 | a^{q^2-a} + 1$. Hence $n = q^2 \geq 2a$ works in this scenario. Solution by angiland

https://aops.com/community/p11383329 kaede wrote: For N9 Lemma For any $(a,n) \in \mathbb{N}^{2}$ with $a>3$, $n>2$, there exist a prime $p$ satisfying $\mathrm{ord}_{p}(a) =n$ and either $p^{2} \mid a^{n}-1$ or $p>n+1$ except in the case of $(a,n) =(5,6)$.

Proof of the lemma

Solution We can choose a prime $p$ such that $\mathrm{ord}_{p}(a) =2(a-1)$ and either $p^{2} \mid a^{2a-2} -1$ or $p >2a-1$. In particular, there exist a integer $m(\geq 2a)$ satisfying $m\mid a^{m-a} +1$. To complete the proof, it is sufficient to show that if $r\mid a^{r-a} +1$ for an integer $r(\geq 2a)$, then there exist an integer $s( >r)$ such that $s\mid a^{s-a} +1$ : We can choose a prime $p$ satisfying $\mathrm{ord}_{p}(a) =2(r-a)$. Then $p-1\geq 2(r-a) =r+(r-2a) \geq r$, which implies $p >r$. Since $\gcd(p,r) =1$, by setting $s=pr$, we have $s\mid a^{s-a} +1$. $\blacksquare$

andrei.pantea wrote: Let us consider the equivalent condition $n | a^{n-a} + 1$. Suppose we have such an $n$, let us try to find a prime $p$ co-prime with $n$ such that $np$ also satisfies the divisibility. For this we need $n | a^{np-a} + 1$ and $p | a^{np-a} + 1$. Since we already know $n | a^{n-a} + 1$, the former divisibility is guaranteed if $\frac{np-a}{n-a}$ is an odd integer. We are going to choose $p \equiv 1 \pmod {2(n-a)}$, so that $\frac{np-a}{n-a} = 1 + \frac{n(p-1)}{n-a}$ is indeed odd. We also need $p | a^{np-a} + 1$. By Fermat's little theorem, this is equivalent to $p | a^{n-a} + 1$. Here comes the crucial part: by a version of Zsigmondy's theorem, $a^{n-a} + 1$ contains a "primitive" prime divisor $p$ with $p \equiv 1 \pmod {2(n-a)}$, whenever $n-a \geq a \geq 4$. Moreover, if $n \geq 2a$ then $p > 2(n-a) \geq n$, so $p$ is co-prime with $n$ as desired. Suppose $a \geq 4$, then the above analysis implies that as soon as we find one $n \geq 2a$ such that $n | a^{n-a} + 1$, we can find infinitely many such $n$. To initialize the process, let us choose $n = q$ be a prime factor of $a^{a-1} + 1$. By Fermat, we see that $q | a^{q-a} + 1$. Moreover, by Zsigmondy again we can choose $q$ with $q \equiv 1 \pmod {2a-2}$. Thus $n = q \geq 2a$ unless $q = 2a-1$ is the only primitive prime factor of $a^{a-1} + 1$. If that does happen, we must have $q^2 | a^{a-1} + 1$ because the primitive part of $a^{a-1} + 1$ (which is roughly the value of a cyclotomic polynomial evaluated at $a$) is larger than $q$ for $a \geq 4$. Then from $q^2 | a^{q-a} + 1$ and $q^2 | a^{q^2-q} - 1$, we obtain $q^2 | a^{q^2-a} + 1$. Hence $n = q^2 \geq 2a$ works in this scenario. Solution by angiland sorry,why $a+n|a^{n}+1$ equivalent $n | a^{n-a} + 1$