Assume for the sake of contradiction that $n^b+1|a^n+1$ for all $n> N $ Claim: Any prime dividing $b $ divides $a $.

$b|a^k $ which is what we want to prove. If $b $ is even then $a $ is even so take $n $ sufficiently large odd integer it yields that $a $ is odd which contradicts to our claim. So $b $ is odd.Take $n $ sufficiently large such that $n\equiv -1 modp $ where $p|b $.Again similarly we get a contradiction.So done.

TwoTimes3TimesSeven wrote: $a$ and $b$ are given positive integers. Prove that there are infinitely many positive integers $n$ such that $n^b+1$ doesn't divide $a^n+1$. Suppose $n^b+1 \mid a^n+1$ for all sufficiently large $n$. Claim. Set of primes $p$ that divide some number of the form $n^b+1$ is infinite. (Proof) Assume not; let $p_1, \dots, p_s$ be all such primes. Plug $n=\prod^{s}_{i=1} p_i$ to get a contradiction! $\blacksquare$ Pick a large prime $p$ with $p \mid r^b+1$ for some $r>0$. Put $n=r+kp$ and $n=r+(k+1)p$ successively, for $k$ large enough, then $p \mid n^b+1 \mid a^{n}+1$ hence $a^{r+kp} \equiv a^{r+(k+1)p} \pmod{p}$ so $a \equiv 1 \pmod{p}$ (since $p \nmid a$ of course). This is bound to fail for $p$ big since $(a-1)>0$. $\blacksquare$

We may assume that $a$ is odd. Let $b=2^kt,$ where $t$ is odd. Set $n:=a^{2^n}$ for some positive integer $n.$ If we assume that $a^{2^{(k+n)}t}+1|a^{a^{2^n}}+1\Rightarrow a^{2^{k+n}}+1|a^{a^{2^n}}+1\Rightarrow 2^{k+n}|2a^{2^n}$ and therefore $2|a, $ which is a contradiction.

The fact that there are infinitely many $n$ such that bla bla bla, doesn't imply that all large $n$ satisfies that properties.

@Gluncho That's true, but what I think they're saying is: Suppose there are not infinitely many that satisfy this property. This means there are finitely many integers $n$ with this property. That means, there is some biggest one. So, everything bigger than that does not satisfy the property. Then, they prove that this is impossible.

TwoTimes3TimesSeven wrote: $a$ and $b$ are given positive integers. Prove that there are infinitely many positive integers $n$ such that $n^b+1$ doesn't divide $a^n+1$. We construct a prime $p>2$ such that there exists infinitely many $n$ such that $p|n^b+1$ but $p \nmid a^n+1$. For this, we set up the system $$\left\{\begin{array}{l}n \equiv z \pmod{p}\\n \equiv 0 \pmod{p-1}\end{array}\right.$$where $z$ is such that $z^b \equiv -1 \pmod{p}$. By the Chinese Remainder Theorem, there exist infinitely many such $n$, and we are then done as then $a^n \equiv 1 \pmod{p}$ and so $p \nmid a^n+1$ while $p|n^b+1$. We just need to show the existence of such a $z$. But this is easy, choose $p$ such that $b|p-1$ and set $z=g^{(p-1)/2b}$, where $g$ is a primitive root modulo $p.$ $\square$ Comment: The last part, that is showing the existence of such a $z$ is not easy. But primitive roots do the job. This is because the existence of a primitive root is in itself a pretty strong result. Hence, this existence-type proof (and not a contradiction method as the proof given by others above) seemed real smooth, otherwise could have been a real mess!

Assume there are finite such $n$ so $n^b+1 \nmid a^n+1$. So we have $n^b+1 \mid a^n+1$ for all $n > M$ for some M. Take some $n = x >M$ so x is even. Take some prime $p \mid x^b+1$ (which is odd since $x^b+1$ is odd). Then $p \mid a^x+1$. Also, $p \mid (x+p)^b+1 \mid a^{x+p}+1$. Then $a^x \equiv -1 \equiv a^{x+p} \pmod p$. so $a^p \equiv 1 \equiv a^{p-1}$ (RHS equivalence is by FLT). Then $a \equiv 1 \pmod p$. So, $0 \equiv a^x+1 \equiv 2 \pmod p$. But $p$ is not even which is a contradiction.

My solution is undoubtedly long and not pretty, but I would like someone to check it for correctness.

By Schur Theorem, there exists infinitely many prime $p$ which divides $k^b+1$ for some $k$. Take one such $p > a+1$ and just let $n\equiv k\pmod p$ and $n\equiv 1\pmod{p-1}$.

My solution : All P in form 4k+1 and such that all primes of a+1 divide p-1 works Proof: use ord , ...

Assume that there are infinitely many integers n that doesn't satisfy the condition, then consider p| n^b+1. Thus p|a^n+1. Then consider (n+p). Apparently p|(n+p)^b+1. By Schur Theorem, choose p significantly large compared to a, then a-1 is not divisible by p and thus a^p -1 is not divisible by p. Hence, a^(n+p)-1 is not divisible by p

I do not understand the necessity of Schur's Theorem in the above proofs - simply an odd prime divisor of $n^b+1$ works. Assume for the sake of contradiction that there are $a,b \in \mathbb{N}$ satisfying the condition. Let $p$ be a prime ($p \neq 2$ which one can ensure by the Catalan Conjecture) such that $p \mid n^b+1$ for some $n \in \mathbb{N}$. Then notice that $$p \mid (kp+n)^b+1$$for all $k \in \mathbb{N}$, we have that $$p \mid (kp+n)^b+1 \mid a^{kp+n}+1$$for all but finitely many $k \in \mathbb{N}$, yet notice that $ord_p(a)$ is relatively prime to $p$ meaning that $kp+n$ is surjective $\pmod{ord_p(a)}$ which is a contradiction as we can simply take infinitely many $k \in \mathbb{N}$ such that $ord_p(a) \mid kp+n$. $\blacksquare$

Can someone please check my solution

, we have that $\exists N \in \mathbb{Z}_p$ such that $ord_p(N)=2^{x+1} \implies p|N^{2^x}+1$. Then, choose a natural number $k$ such that $k \equiv -N \pmod{p-1}$.Also $ord_p(kp+n) =2^{x+1} \implies p|(kp+N)^{2^x}+1$ Now , $$p|a^{kp+N}-1 \implies \gcd(p,a^{kp+N}+1)=1$$Thus we are done.

lte ftw

First we start by ruling out the case when $b$ is odd. Let $q$ be an odd prime. By CRT, we can find a $n$ such that \[n \equiv q-1 \pmod {q(q-1)}.\] Note that this gives that \begin{align*} n^b &\equiv (-1)^b = -1 \pmod q,\\ n &\equiv 0 \pmod {q-1}. \end{align*} Thus, we have \[0 \equiv n^b + 1 \equiv a^n + 1 \equiv 2 \pmod q\] which is a contradiction. Such choice of $n$ is infinite. Hence, we are done in this case. Let $\nu_2(b) = m,$ and $b = 2^mk.$ We let $q$ be a prime such that \[q \equiv 1 \pmod {2^{m+1}}\] for which there are infinitely many of them by Dirichlet. Then we wish to find a $n$ such that \begin{align*} n^{2^m} &\equiv -1 \pmod q\\ n &\equiv 0 \pmod {q-1}. \end{align*} Let $n = (q-1)l$, then we want \[l^{2^m} \equiv -1 \pmod q.\] We show such $l$ exists. Let $g$ be a primitive root modulo $q$. Then setting $l = g^{(q-1)/2^{m+1}}$ works. So, \[0 \equiv (n^{2^m})^k + 1 \equiv n^b + 1 \equiv a^n+1 \equiv 2 \pmod q\] which is again a contradiction. Such choice of $n$ is again infinite and hence we are done.