Prove that infinitely many integers $n$ satisfy $(n+a)\mid(a^n+1)$

Question

Let $a\in\mathbb Z$ and $a\gt3$. Prove that there exist infinitely many positive integers $n$ satisfying $(n+a)\mid(a^n+1)$.

This problem was mentioned for the first time in this post, so all the credits should go to Drona. The author (wrongly, I think) thought that the two problems were equivalent. I made a comment about that but it went unnoticed because it was the last one in a pretty long chain. I asked Drona to post the original question but did not hear from him since then. I believe that this problem is too interesting to be left buried in some hidden comment, so I decided to post it here.

It's relatively easy to prove that $a$ and $n$ must be coprime. But apart from that simple fact I did not get much further.

Answer 1

Ok, so this may not be a proper solution or a solution at all but I'll try my best. Sorry in advance.

If $ (a+n)|(a^n+1)$ then by long division we get the remainder $(-1)^kn^ka^{n-k} +1$ for each k times that we divide. When we keep on dividing then k finally becomes $n$. Then the remainder becomes $(-1)^nn^n+1$. Since $(a+n)|(a^n+1) \rightarrow (a+n)|((-1)^nn^n+1)$ in order for the remainder to vanish. The term $(-1)^nn^n+1$ is dependent only on n, and we can find its factors($x$) greater than $3+n$ where they exist. Then we have the desired values of $n$ for each $a = x-n$.

Answer 2

This is also not a proper solution but might be a good direction to follow. Suppose $a-1$ is not a power of 2 and is not a prime number. Let $s\geq 3$ be an odd prime factor of $a-1$ and $r=(a-1)/s \geq 2$. Suppose that $A=a^{r}+1$ has a prime factor $p$ greater than $\sqrt{A}$. Then $p>\sqrt{A}>a$. We claim that $n+a \mid a^n+1$, where $n=p-a>0$. One has, by Fermat's little theorem, that $$a^n+1 \equiv a^{p-a}+1 \equiv a^{1-a}(a^{a-1}+1) \equiv a^{1-a}(a^{r}+1)B \equiv 0 \pmod p,$$ for some integer $B$.

The probability of a number $A$ having a prime factor greater than $\sqrt{A}$ is $\log 2$. So this argument proves the claim for at least 30 percent of numbers.