Ah APMO problems have been posted! A bit easy for APMO though First remark that if $p < n$, then $p^n > n^p$ so $p^n + 1 > n^p + 1$ and the problem obviously doesn't hold. Hence $p \ge n$. Consider a prime power $z^k|(p+1)$. Unless $n \equiv -1 \pmod{z^k}$ we have $\text{ord}_{z^k}(n) = 2p$. But that's obviously false as $2p > z^k$, hence $n \equiv -1 \pmod{z^k}$ or all prime powers which divides $(p+1)$. But this implies $n \equiv -1 \pmod{p+1}$, and hence as $p \ge n$ the only solutions are when $n=p$ which obviously work. Hence all solutions are $(p,p)$ for $p$ a prime number. EDIT : Oops my inequality fails when $p=2$, so $(2,4)$ is also a solution. Here is a proof $a^b > b^a$ when $a > 2$ and $a < b$ to make sure I don't mess up more. It suffices to show $a^{b/a} > b$. When $a > e \approx 2.718$ we know $a^z > za$ for $z > 1$ so the result follows. To prove this, consider the function $f(x) = a^x - ax$. $f'(x) = \ln a a^x - a$. Remark that $f'(x) \ge 0$ for $x \ge 0$ and the result follows as $f(1) = 0$. Now for $p=2$, $2^n > n^2$ for $n > 4$ so it follows the only solutions are $(p,p)$ and $(2,4)$.

I'm not agree with you $p=2$ and $n=4$ is an answer notice that $2^{4}=4^{2}$

My solution is slightly different from that of dinoboy's: If $p=2$ then $n=2$ and by the inequality $2^n>n^2$ for $n>4$, we get that $n=2$ or $n=4$ work. Otherwise $p\ge 3$ so $p$ is odd, meaning $n$ must be also odd since $2|n^p+1$. Hence $p^n+1$ can be factorised as $(p+1)(p^{n-1}-p^{n-2}+\ldots +p^2-p+1)$. Thus $p+1|n^p+1$. Let $q$ be a prime factor of $p+1$. Suppose $q$ is odd. Now $q|n^p+1$ so $n^{p}=-1\pmod{q}$. Since $q$ is odd, this means $\text{ord}_q(n)\in\{2,2p\}$. If $\text{ord}_q(n)=2$ then $n^2=1\pmod{q}$. If $n=1\pmod{q}$ then $1=n^p=(-1)^p=-1\pmod{q}$ but $q\nmid 2$, so this is impossible. Hence $n=-1\pmod{q}$ and so $q|n+1$. If $\text{ord}_q(n)=2p$ then $2p|q-1$ (note that $n^{q-1}=1\pmod{q}$ by FLT) but also $q|p+1$. These divisibilities imply that either $q=1$ or $2p\le p$, both of which are of course contradictory. So if $q\not= 2$ then $q|n+1$. If $q=2$ then clearly $q|n+1$ as $n$ is odd. Now suppose for some prime divisor $r$ of $p+1$, we have that $v_r(p+1)>v_r(n+1)$ (we denote the number $k$ such that $a^k||b$ as $v_a(b)$). Therefore since $p+1|n^p+1=(n+1)(n^{p-1}-n^{p-2}+\ldots +n^2-n+1)$, we have that $r|n^{p-1}-n^{p-2}+\ldots +n^2-n+1$. But $n=-1\pmod{r}$ and $p$ is odd, implying that $0=n^{p-1}-n^{p-2}+\ldots +n^2-n+1=1+1+\ldots +1+1+1=p\pmod{r}$. Therefore $r|p$, impossible in view of the fact that $r|p+1$. Hence $v_r(p+1)\le v_r(n+1)$ for all prime divisors $r$ of $p+1$. Therefore $p+1|n+1\implies p\le n$. As dinoboy has already noted, we have must $p\ge n$, so overall $p=n$ giving all solutions to be $(p,p)$ for all primes $p$ and $(2,4)$.

An other solution: If $p = 2$, then ${n^2} + 1 \geqslant {2^n} + 1$, so we have $n \leqslant 4$, it is easy to see $n = 2,4$. Now we suppose $p$ is an odd prime, so $n$ is odd, because ${n^p} + 1 \geqslant {p^n} + 1 > 3$, so $n \geqslant 3$. Because $f(x) = {x^{1/x}}$ is decrease for $x \geqslant e$, from ${n^{1/n}} \geqslant {p^{1/p}}$ we have $n \leqslant p$. Because $p + 1\left| {{p^n} + 1} \right.$, ${n^p} + 1 \equiv 0 \equiv {p^p} + 1(\bmod p + 1)$, so ${n^p} \equiv {p^p}(\bmod p + 1)$. By $Euler$ theorem ${n^{\varphi (p + 1)}} \equiv 1 \equiv {p^{\varphi (p + 1)}}(\bmod p + 1)$, so ${n^{(p,\varphi (p + 1))}} \equiv {p^{(p,\varphi (p + 1))}}(\bmod p + 1)$, hence $n \equiv p(\bmod p + 1)$, because $1 \leqslant n \leqslant p$, we have $n = p$. Above all, $(p,n) = (p,p),(2,4)$ are the all solutions.

Why does $ {n^{(p,\varphi (p+1))}}\equiv{p^{(p,\varphi (p+1))}}(\bmod p+1) $ imply $n\equiv p \mod p+1$?

AwesomeToad wrote: Why does $ {n^{(p,\varphi (p+1))}}\equiv{p^{(p,\varphi (p+1))}}(\bmod p+1) $ imply $n\equiv p \mod p+1$? Because $p$ is a odd prime, $p + 1$ is even, so every prime factor of $\varphi (p + 1)$ is less then $\frac{{p + 1}}{2} < p$, hence $\left( {p,\varphi (p + 1)} \right) = 1$.

Can someone tell me if this solution is valid or not? I'm not really to sure about it so I would appreciate any input. Thanks in advance. (Also, I wasn't sure whether to make a new thread or to revive this old one, so I apologize if I have done the wrong thing)

@sicilianfan: Your solution is correct. Nice argument regarding how much each quantity increases! And also the fact that $n \cong -1 (mod p+1)$.

Thanks for the feedback, but there actually was a problem with my solution (of which I was informed a while ago): I assumed that just because $\text{ord}_{p+1}(n)=2$ that $n \equiv -1 \pmod{p+1}$ which is in fact only true if $p+1$ has a primitive root (this is what I overlooked), which is certainly not a valid assumption. It can be fixed by taking mod $q$ where $q$ is a prime that divides $p+1$ instead, and patching from there.

If $p=2$, then $n^2 + 1 \geq 2^n + 1 \implies n \leq 4$. Easily, we can see $(p,n) = (2,2); (2,4)$ are the only solution in this case. Suppose now that $p \geq 3$ is an odd prime. Since $n^p + 1 \geq p^n + 1$, we have $n \geq 3$. Now $n^p \geq p^n \implies n^{\frac{1}{n}} \geq p^{\frac{1}{p}} \implies n \leq p$ since $f(x) = x^{\frac{1}{x}}$ is a decreasing function for $x \geq e$. $(p+1) \mid p^n + 1 \implies (p+1) \mid n^p + 1$. Hence $n^p \equiv -1 \pmod {p+1}$, so it follows that $\text{ord}_{p+1}(n) = 2$ or $2p$. The second option is absurd, since $2p > p+1 > \phi (p+1)$, so $\text{ord}_{p+1} (n) = 2$: i.e. $n^2 \equiv 1 \pmod {p+1}$. Now $-1 \equiv n^p \equiv n^{p-1}\cdot n \equiv n \pmod {p+1}$, so $p=n$. Thus our only solutions are $\boxed{(p,n) = (p,p); (2,4)}$.

What is the mean $ord$??

Let $p$ be an odd prime. Then $p^n+1|n^p+1 \implies p^{\frac{1}{p}} \le n^{\frac{1}{n}} \implies n \le p$ because $f(x)=x^{\frac{1}{x}}$ is decreasing function for $x \ge e$. It is easy to see that $n$ must be odd.Let $r$ be the order of $n$ modulo $p+1$.Then $p^n+1|n^p+1 \implies p+1|n^{2p}-1 \implies r|2p$.Clearly $r \le p$ and $r$ cannot be $p$.Also $r=1 \implies p+1|n^p-1 \implies p+1|2 $ which is absurd.So $r=2$ and $p+1|n+1$ which means $p \le n$.This along with the first line's inequality yeilds $n=p$. For $p=2$ we have $2^n+1|n^2+1 \implies 2^n \le n^2 \implies n \le 4$.Checking we get solutions $n=2,4$. Thus the solutions are $(p,n) \equiv (2,4),(p,p)$

Hi dear mathlinkers I have a question What made you to think about $p+1$?

Fisrt , if $p > 2$ then $n$ is odd . Let $q$ is a prime number of $p+1$ . Then , $q | n^p+1 \implies q | n^{2p}-1$ , and $q| n^{q-1}-1$ , and because $q < p$ then $ q | n^2 - 1$ , which implies $q | n+1$ And we have $v_q(p^n+1) = v_q (p+1) < v_q(n^p+1) = v_q(n+1) \implies p+1 | n+1 \implies p \leq n $ But we have $n^p > p^n \implies plog(n) \geq nlog(p) \implies \frac{log (n)}{n} \geq \frac{log (p) }{p} $ Let $f(x) = \frac{log x }{x}$ , then $f'(x) = \frac{1 - log x }{x^2}$ , then , for $x > 10$ , $f$ is decreasing . So , for $n , p > 10$ we have $ n \leq p$ Then $ n = p$ For the cases $n$ or $p < 10$ we can check that $(n,p) = (4,2)$

Obviously we need $n^p \equiv -1 \pmod{p^n+1} => n^{2p}=1 \pmod{p^n+1}$. Thus $O_{p^n +1}(n) \mid 2p$, but it doesn’t divide $p$- thus it must equal $2$ or $2p$. First let’s deal with the easier case, where order is $2$. Here we can clearly see that as $n^2-1 \geq p^n+1$, which is obviously false. Now, what’s left is the case where $O_{p^n+1}(n)=2p$. In this case, we must again split into cases- before that, let’s consider some prime $q$ such that $v_q(p+1)=\alpha>0$- here notice that as $n \equiv 1\pmod{2}$ for odd primes, $q^{\alpha} \mid p^{n}+1$. Clearly, we need $O_{q^\alpha}(n)= 2$ or $2p$, by similar logic- if $2p$, we get an immediate contradiction as $2p>p+1$. Now let’s look at the case when $O_{q^{\alpha}}(n)=2$. Now, as $(n+1)(n-1)= 0\pmod{q^{\alpha}}=> q^{\alpha} \mid n+1$ (almost forgot to consider $q=2$ separately, but in the end it doesn’t matter as $n$ is odd) for all such $q^{\alpha} \mid p+1$. Hence, in a rather elegant manner, we get $p+1 \mid n+1$, which of course kills the problem as $p \geq n => (p,p)$ is only solution for odd primes. Now, you could manually check for $p=2$ and that’ll give you and extra solution $(2,4)$, hence concluding the problem with the solution set $(p,p),(2,4)$ for all primes $p$. I felt this was actually quite a nice problem and a great fit for P3 (okay maybe a bit on the easier side, I suppose, but I’m not a very good judge), simply because if you don’t notice a few key points(at least if you solve it the way I did), the problem becomes hellish to solve- that makes me wonder, who proposed this?

Assume $p=2$, and deal with $p>2$ later. Leaving $n \leq 4$, we have $n^2+1 < 2^n+1$, and there are no integers in $(0,1)$. Looking at $n \leq 4$, we see $n=2 ,4$ work. See that for $p$ odd, $p^n+1$ is even, so $n^p+1$ is even Then, $n$ must be odd as well Assume $n \neq p$, since we can see that $n=p$ works. Realize that $p+1 \mid p^n+1$ from $n$ odd, so $p+1 \mid n^p+1$ Note that since any prime $q \mid p+1$ is $<p$ Abusing order, this implies $q \mid n^p+1 \Rightarrow q \mid n+1$. Thus, $p+1 \mid n+1$, so $n>p$. Inequalities kill the rest of the problem: we claim $n^p+1>p^n+1$. Observe that $f(x)=\ln(\sqrt[x]{x})$ has $f'(x)=\frac{1-\ln(x)}{x^2}$, it decreases for $x>e$, so $\sqrt[n]{n} \leq \sqrt[p]{p}$, implying result. Now, we are left with the final answer of $(2,4)$ and $(p,p)$. YUH $\blacksquare$

Assume $p$ is odd; we will deal with $p=2$ later. Then $p^n+1$ is even, so $n^p+1$ is even, so $n$ is odd. Suppose $q\mid p+1$ for a prime $q$. Then \[ q\mid p+1 \implies q\mid p^n+1 \implies q\mid n^p+1\implies n^p\equiv -1 \pmod{q}, \ n^{2p} \equiv 1 \pmod{q}. \]Let the order of $n \pmod{q}$ be $x$. Then $x\nmid p, x\mid 2p$, so $x=2,2p$. We also have $x\mid q-1$; hence if $x=2p$ then $2p \mid q-1$, so $q \ge 2p$, contradicting $q \mid p+1$ by size. Hence $x=2$. So $n^2 \equiv 1\pmod{q}$, which means $q\mid (n-1)(n+1)$. We claim we actually have $q\mid n+1$. If $q\mid n+1$, we have proved the claim. If $q\mid n-1$, then $q\mid n^p-1$. But $q\mid p+1 \mid p^n+1 \mid n^p+1$, so we also have $q\mid 2$. So $q=2$. But since $n$ is odd, $2\mid n+1$, so this proves our claim. Therefore, $q\mid p+1 \implies q\mid n+1$. Now, we use LTE. Note that $q\mid p+1, n+1$, so $q\nmid p,n$. We have \begin{align*} \nu_q(n^p+1) &= \nu_q(n+1) + \nu_q(p) = \nu_q(n+1) \\ \nu_q(p^n+1) &= \nu_q(p+1) + \nu_q(n) = \nu_q(p+1). \end{align*}But $p^n+1\mid n^p+1$, so therefore $\nu_q(n+1) \ge \nu_q(p+1)$. Since $q$ was defined to be any prime divisor of $p+1$, we conclude that $p+1\mid n+1$. In particular, $p\le n$. Now, we use size. Since $p^n+1\mid n^p+1$, we know $p^n \le n^p$. So $n \ln p \le p \ln n$, i.e. $\tfrac{n}{\ln n} \le \tfrac{p}{\ln p}$. Let $f(x) = \tfrac{x}{\ln x}$. It is not hard to show that $f(x)$ is increasing for $x\ge 3$. But $x$ increased from $p$ to $n$, while $f(x)$ decreased from $p$ to $n$. Therefore, either $p<3$ or $n=p$. If $p<3$, then $p=2$, and only $(p,n)=(2,2),(2,4)$ works here. Finally, the solutions are $(p,n)=(p,p),(2,4)$.

The answer is $(2,4)$ and $(p,p)$, where $p$ is prime, only. These can be easily checked. For $p=2$, we can find that the only solutions are $n=2,4$, since anything larger results in $p^n+1>n^p+1$. Henceforth assume $p \geq 3$ Note that it is well-known that if $a>e>2$ and $b>a$, then $a^b>b^a$. Since we need $n^p+1 \geq p^n+1$ and $p \geq 3$, it follows that $b \leq a$. Now, since $p \geq 3$, $p^n+1$ is even and hence $n^p+1$ is even too, so $n$ is odd. As such, any prime $q \mid p+1$ must divide $p^n+1$. Let $Q=q^e \mid p+1$, where $q$ is a prime, $Q \neq 2$ and $e=v_q(p+1)$. Then we need $n^p \equiv -1 \pmod{Q}$. This is enough to imply that $\operatorname{ord}_Q(n) \mid 2p$. However, we also cannot have $\operatorname{ord}_Q(n) \mid p$, else $n^p \equiv 1 \pmod{Q}$. This narrows down the options to $\operatorname{ord}_Q(n)\in \{2,2p\}$. However, the latter is impossible for size reasons as $Q \leq p+1$, so $\operatorname{ord}_Q(n) \leq Q-1\leq p \leq 2p$. Hence we conclude that $\operatorname{ord}_Q(n)=2$ for all prime powers $Q \neq 2$ dividing $p+1$, implying $n \equiv -1 \pmod{Q}$. This also works if $Q=2$, in which case $n \equiv 1 \equiv -1 \pmod{Q}$. Hence by CRT, we have $n \equiv -1 \pmod{p+1}$. But we also have $b \leq a$, so $n=p$. Thus no other solutions exist. $\blacksquare$

syk0526 wrote: Determine all the pairs $ (p , n )$ of a prime number $ p$ and a positive integer $ n$ for which $ \frac{ n^p + 1 }{p^n + 1} $ is an integer. Assume that $n \neq p$ since when $n=p$ we obtain $(n,p)=(p,p)$ which works. Henceforth assume that $p \ge n$ and $p \ge 2$ i.e when $p=2$ we obtain $(n,p)=(2,4)$ which works. Clearly $n$ is odd let $\tilde{p}$ be a prime dividing $p+1$ Notice that $$\nu_{\tilde{p}}(p^n+1)=\nu_{\tilde{p}} (p+1)+\nu_{\tilde{p}} (n)$$i.e $$\tilde{p}|n^p+1 \implies ord_{\tilde{p}}(n)=\{1,2,2p\}$$The first and last cases are impossible hence $n^2+1 \equiv 0 \pmod {\tilde{p}}$ implying $p+1 \equiv 1 \pmod 4 \implies 4|p$,contradiction so $(n,p)=(4,2),(p,p)$

Lemma:if $a$ and $b$ positive integer numbers and $a \leq b \implies b^a \leq a^b$

Funny problem! Suppose that $p \neq 2$ because if we have $p=2$ then $n^2+1 \ge 2^n +1 \implies n \leq 4$ so we have the solutions: $(p,n): (2,2); (2,4)$ Claim: $p+1 \mid n+1$ Proof: First we have that $p^n+1$ is even so $n$ is odd then $p+1 \mid p^n+1\mid n^p+1$ so $p+1 \mid n^{2p} -1 \implies p+1 \mid n^{(2p,\phi(p+1))}-1$ but $\phi(p+1) \leq p-1$ so $(\phi(p+1),p)=1 \implies (2p,\phi(p+1)) \mid 2 \implies p+1 \mid n^2 -1 \implies p+1 \mid n+1$. (Because $p$ is odd) $\square$ Let $n=pu$ .Then we have that $p^n +1 \leq n^p +1 \implies p^pu \leq (pu)^p \implies p^{u-1} \leq u$ but if $u \ge 2$ we have that: $$\lfloor u \rfloor +1 > u \ge p^{u-1} \ge 3^{u-1} \ge 3^{\lfloor u \rfloor-1} \implies \lfloor u \rfloor +1 \ > 3^{\lfloor u \rfloor-1} $$This is false if $u \ge 2$ so we have $n <2p$ and $p+1 \mid n+1$ so $p=n$. This concludes the problem. $\blacksquare$

I really enjoyed from this problem. If $p=2$, we easily get $n=2$ or $n=4$. If $n=1$, we get there is no solution. If $n=2$ we get $p=2$. Now assume $p,n>2$. Since $p^n\leq n^p$ and $p,n>e$, we get $p\geq n$. $n=p$ is obviously solution. Now assume $p>n$. Since $p$ is odd, we get $n$ is odd also. So $p+1\mid n^p+1$. Consider odd prime divisor $q$ of $p+1$. Since $p>q-1$, we get $\gcd(2p,q-1)=2$. Since $n^{q-1}\equiv n^{2p}\equiv 1 \pmod{q}$, and $\gcd(2p,q-1)=2$, we get $n^2\equiv 1 \pmod{q}$. So $n^p+1\equiv (n^2)^{\frac{p-1}{2}} \cdot n+1\equiv n+1\equiv 0 \pmod{q}$. So $q\mid n+1$. Also we have $v_q({p^n+1})=v_q({p+1})+v_q({n})=v_q({p+1})\leq v_q({n^p+1})=v_q({n+1})+v_q({p})=v_q({n+1})$. So if $q$ is odd prime divisor of $p+1$ , then $v_q({p+1})\leq v_q({n+1})$. Now let's deal with $v_2$. Since $v_2({p+1})\leq v_2({n^p+1})=v_2({n+1})$, we get $v_2({p+1})\leq v_2({n+1})$. So $v_r({p+1})\leq v_r({n+1})$ for all prime number $r$. So we get $p\leq n$, which is contradiciton. So all solutions are $\boxed{n=p}$, $\boxed{p=2,n=4}$.

If $p=2$, we get $n=2,4$. Now suppose $p>2$, then $n$ is odd, and we can't have $n=1$, thus: $n \le p$. $p+1 \mid p^n+1 \mid n^p+1 \mid n^{2p}-1$ which implies $O_{p+1}(n) \mid 2p$. If $O_{p+1}(n)$ is odd we get $O_{p+1}(n) \mid p$ clearly impossible. Thus: $O_{p+1}(n) \in \{2,2p\}$. Can we have: $O_{p+1}(n)=2p$? No, the reason being: $\phi(p+1)\le (p+1)<2p$. Thus: $O_{p+1}(n)=2$ which gives us that: $p+1 \mid (n-1)(n+1)$ or $\frac{p+1}{2^{v_2(p+1)}} \mid (n-1) × \frac{n+1}{2^{v_2(p+1)}}$, but $\frac{p+1}{2^{v_2(p+1)}}$ is odd, and therefore coprime with $n-1$, and by LTE $\frac{n+1}{2^{v_2(p+1)}}$ is an integer, thus $p+1 \mid n+1$, which gives us $p=n$.

Interesting. Suppose that $n$ and $p$ are not equal and $p>2$: We know that $n^p$>$p^n$, since $n,p>e$ ($n=2$ case is impossible because $n$ must be odd according to mod 2 and $n=1$ is easy) we have $p>n$ (It is well known that for $a,b>e$, if $a^b>b^a$, then $b>a$). We have $2 \mid p^n+1\mid n^p+1$, then $n$ is odd, then $p+1 \mid p^n+1 \mid n^p+1$ . Let $\operatorname{ord}_{p+1}(n)=k$, since $n^{2p} \equiv 1 \pmod{p+1}$, we know that $k \mid 2p$, we know that $k<2p$, and $k$ is not equal to $p$ (because $n^p \equiv -1 \pmod{p+1}$), which means that $k \mid 2$, then $n^p+1 \equiv n+1 \pmod{p+1}$, since $p+1 \mid n^p+1$, we have $n \equiv p \pmod{p+1}$, which is contradicting $p>n$, then $p$ must be equal to $n$ for $p,n>3$. For $p=2$ we have $2^n+1>n^2+1$ for $n>4$, you can check the cases $n=1,2,3,4$, which gives the solutions $(2,4)$ and $(2,2)$. Then answers are $(p,p)$ and $(2,4)$ where $p$ is an any prime number.

I claim the answers are $n = p$ for all $p$ and $n = 4, p = 2$. First, it is well known that $a^b > b^a$ when $a < b$ and both $a, b \geq 3$ (the result follows form taking a log of both sides and a derivative to show strict monotonicity). In the case when $p = 2$, by bounding we have $n \leq 4$ and here only $n = 4$ works. In the case $n = 1$, the value is less than $1$, and in the case $n = 2$, there is death by parity for $p \geq 3$. Otherwise, we have $n \geq 3$ and thus $n \leq p$. Obviously $n = p$ works. Now notice that since $p^n + 1$ is even, we must have $n$ odd, so it follows $n^p \equiv -1 \pmod{p + 1}$. In particular, since $p+1$ is composite and thus $p \nmid \phi(p+1)$, it follows that there is a unique solution to $n^p \equiv -1 \pmod{p+1}$ up to $p + 1$. Since $n = p$ suffices, this must be the only solution, so we are done.

The answer is $n=p$ and $p=2,n=4$ only. For $p=2$, we have $2^n+1\mid n^2+1$, which only has $n=2$ and $n=4$ as a solution since $2^n>n^2$ for all $n\geq 5$. $n=1$ gives $p+1\mid 2$ which clearly does not work, and $n=2$ gives $p^2+1\mid 2^p+1$ which can only work for $p=2$ since $2^p+1$ is odd. Thus, assume $n,p\geq 3$ from now on. This means that for $n^p$ and $p^n$, the one with the higher exponent is larger, which means that we must have $n\leq p$. If $n$ is even, we must have $p=2$ since the numerator is odd, but we have already shown that the only solution for $p=2$ is $n=2$ and $n=4$. From now on, assume $n$ odd, so $p+1\mid p^n+1$. Thus, $$p+1\mid n^p+1$$$$n^p\equiv -1\pmod{p+1}$$$$n^{2p}\equiv 1\pmod{p+1}.$$Thus the order of $n$ mod $p+1$ must divide $2p$ but not $p$, which means it is either $2$ or $2p$. However, it cannot be $2p$ since that is larger than the modulus of $p+1$, hence the order is $2$ so $n\equiv -1\pmod{p+1}$. Since $n\leq p$, the only solution is $n=p$ in this case.

Only $n = p, (2,4)$ satisfy the condition. For $p=2, p=3$ we can just check until the denominator gets bigger than the numerator. So we can assume $p$ is odd and if $n > p \iff p^n > n^p $ so $n \le p$ It is clear that if we let $\frac{n^p + 1}{p^n + 1} = k$ for some positive integer we have for $p > 2$ $k=1$ if and only if $n = p$ so we can assume $n < p $ $$n^p + 1 - k = p^nk \Rightarrow n \equiv k-1 \pmod p \Rightarrow n = k-1 $$$$(k-1)^p + 1 - k = p^nk \Rightarrow p = k-1 $$so $n = p $ and there are no solutions for $k > 1$.

Solution pairs $(n,p)$, are $(p,p)$ for all primes, and $(4,2)$. Check $p=2$ manually, and by size, assume that $n<p$, as $n=p$ obviously works. Now assume for sake of contradiction some other $n$ works for an odd prime $p$. By orders, if a prime $q \mid n^p + 1$, either $q \equiv 1 \pmod p$ or $q\mid n+1$. By parity, $n=p-1$ dies so consider $n<p-1$: this means $n+1 < p$. By LTE, any prime dividing $n+1$ cannot divide $\frac{n^p+1}{n+1}$, but $n^p+1 \equiv n+1 \pmod p$, which means the primes dividing $n^p+1$ that aren't $1 \pmod p$, are exclusively those dividing $n+1$: their product is thus less than $p$. However, as $2 \mid p^n+1$, then there exists some primes that aren't $1 \pmod p$ that have product greater than $1$ which is a contradiction. I read the other solutions and noticed that I could have just considered $p+1$ instead.

For $p = 2$: We have $2^n > n^2$ for $n \geq 5$, which means we have to check $n = 1, 2, 3, 4$ which gives $(4, 2)$ as a solution, and $(2, 2)$. From now on, assume $p$ odd. Clearly, $p^n + 1$ is even, which means $n$ has to be odd. Consider a prime $q$ such that $q \mid p + 1$. Since $p + 1 \mid p^n + 1$, $q \mid n^p + 1 \implies n^p \equiv -1 \mod{q} \implies n^{2p} \equiv 1\mod{q}$. So, $\text{ord}_q(n) \mid 2p$, and it can't be $1$ or $p$ since $\text{ord}_q(n) \nmid p$, and it can't be $2p$, since $2p > p + 1 > q - 1$. So, $\text{ord}_q(n) = 2$, and $n \equiv -1 \mod{q}$. By LTE, we have $v_q(p^n + 1) = v_q(p + 1) + v_q(n)$, and since $q \mid n + 1$, $q \nmid n$, and $v_q(p^n + 1) = v_q(p + 1)$. We have $v_q(n^p + 1) = v_q(n + 1)$, so $v_q(n + 1) \geq v_q(p + 1) \implies p + 1 \mid n + 1$, so $p \leq n$. For $n > p$, however, $p^n > n^p$, a contradiction, which means $n = p$ is the only solution here, and we're done.