<s>[INST] Find all $(p,n)$ such that $p^n+1\mid n^p+1$ where $p$ is prime. Let $p$ be a prime number. Find all $(p,n)$ such that $$p^n+1\mid n^p+1.$$
Where $n$ is a positive integer.
Here is some obvious solutions $(p,p)$ for any prime $p$ and $(2,4)$.
If $p=2$ then we get $2^n+1\mid n^2+1$ therefore $2^n\le n^2$ but for $n>4$ we have $2^n>n^2$ so no solution. And the only solution for $n\le 4$ is $(2,2)$ and $(2,4)$.
Now assume $p$ is odd then $p+1\mid p^n+1$ therefore $$n^p\equiv -1\pmod{p+1} \implies n^{2p}\equiv 1\pmod{p+1}$$
So $a=\operatorname{ord}_{p+1}{n}\in \{1,2,2p\}$ if $a=1$ then $n\equiv 1\pmod{p+1}\implies n^p\equiv 1\pmod {p+1}$ which is a contradiction.
But I don't know what to do if $a=2$ or $2p$.
 [/INST] If $p = 2$, then $n^2 + 1 \geq 2^n + 1$ is required (since $2^n + 1 \mid n^2 + 1$ and both sides are positive), which implies $n \leq 4$, which we can see only gives solutions $(p, n) = (2, 2), (2, 4)$.
Now if $p \neq 2$, then $p$ is an odd prime, and so $n$ must be odd since $p^n + 1$ is even. Note that $n \geq 3$ since $n \neq 1$, and so we have $p^n + 1 \mid n^p + 1 \implies p^{\frac{1}{p}} \leq n^{\frac{1}{n}}$. But $x^{\frac{1}{x}}$ is decreasing for $x \geq e$, so we must have $n \leq p$.
Now we note $p + 1 \mid p^n + 1 \mid n^p + 1$, so $n^p \equiv -1 \pmod{p+1}.$ Since $p$ is odd, this means $(-n)^p\equiv 1\pmod{p+1}.$
Euler's theorem tells us that $(-n)^{\phi(p+1)} \equiv 1 \pmod{p+1}$, and so by the $\gcd$ trick we get $(-n )^{\gcd(p, \phi(p+1))} \equiv 1 \pmod{p+1}$.
But we note that $2\mid p + 1$ so $\phi(p+1) \leq \frac{p+1}{2}$, so $p$ cannot be a factor of it. Therefore, $\gcd(p, \phi(p+1)) = 1$, and so $-n\equiv 1 \pmod{p+1}$. We conclude that $n \equiv -1 \pmod{p+1}$, and combining with $n \leq p$ yields $n = p$.
</s>