Luke Robitaille tells me this already appeared in an AMM. Oh well. The answer is any $b$ such that $b+1$ is not a power of $2$. In the forwards direction, we first prove more carefully the following claim. Claim: If $b+1$ is a power of $2$, then the only $n$ which is valid is $n = 1$. Proof. Assume $n > 1$ and let $p$ be the smallest prime dividing $n$. We cannot have $p=2$, since then $4 \mid b^n+1 \equiv 2 \pmod 4$. Thus, \[ b^{2n} \equiv 1 \pmod p \]so the order of $b \pmod p$ divides $\gcd(2n,p-1) = 2$. Hence $p \mid b^2-1 = (b-1)(b+1)$. But since $b+1$ was a power of $2$, this forces $p \mid b-1$. Then $0 \equiv b^n + 1 \equiv 2 \pmod p$, contradiction. $\blacksquare$ On the other hand, suppose that $b+1$ is not a power of $2$ (and that $b > 2$). We will inductively construct an infinite sequence of distinct primes $p_0$, $p_1$, \dots, such that the following two properties hold for each $k \ge 0$: $p_0^2 \dots p_{k-1}^2 p_k \mid b^{p_0 \dots p_{k-1}} + 1$, and hence $p_0^2 \dots p_{k-1}^2 p_k^2 \mid b^{p_0 \dots p_{k-1} p_k} + 1$ by exponent lifting lemma. This will solve the problem. Initially, let $p_0$ be any odd prime dividing $b+1$. For the inductive step, we contend there exists an odd prime $q \notin \{p_0, \dots, p_k\}$ such that $q \mid b^{p_0 \dots p_k} + 1$. Indeed, this follows immediately by Zsigmondy theorem since $p_0 \dots p_k$ divides $b^{p_0 \dots p_{k-1}} + 1$. Since $(b^{p_0 \dots p_k})^q \equiv b^{p_0 \dots p_k} \pmod q$, it follows we can then take $p_{k+1} = q$. This finishes the induction. To avoid the use of Zsigmondy, one can instead argue as follows: let $p = p_k$ for brevity, and let $c = b^{p_0 \dots p_{k-1}}$. Then $\frac{c^p+1}{c+1} = c^{p-1} - c^{p-2} + \dots + 1$ has GCD exactly $p$ with $c+1$. Moreover, this quotient is always odd. Thus as long as $c^p + 1 > p \cdot (c+1)$, there will be some new prime dividing $c^p+1$ but not $c+1$. This is true unless $p = 3$ and $c = 2$, but we assumed $b > 2$ so this case does not appear. Remark: In going from $n^2 \mid b^{n}+1$ to $(nq)^2 \mid b^{nq} + 1$, one does not necessarily need to pick a $q$ such that $q \nmid n$, as long as $\nu_q(n^2) < \nu_q(b^n+1)$. In other words it suffices to just check that $\frac{b^n+1}{n^2}$ is not a power of $2$ in this process. However, this calculation is a little more involved with this approach. One proceeds by noting that $n$ is odd, hence $\nu_2(b^n+1) = \nu_2(b+1)$, and thus $\frac{b^n+1}{n^2} = 2^{\nu_2(b+1)} \le b+1$, which is a little harder to bound than the analogous $c^p+1 > p \cdot (c+1)$ from the previous solution. Remark: IMO 1990/3 shows that if $b=2$, then the only $n$ which work are $n=1$ and $n=3$. Thus $b = 2$ is a special case.

We claim that all $b$ not of the form $2^k-1$ for $k\in \mathbb{N}$ satisfies the problem condition. First, assume that $b=2^k-1$ and $n^2 \mid b^n+1.$ Note that $n$ is odd, as if it is even, $b^n+1\equiv 2\mod 4$ while $4\mid n^2\mid b^n+1.$ Thus its minimal prime divisor $p$ is odd. Now \[p\mid b^n+1\implies b^n\equiv -1\mod p\implies b^{2n}\equiv 1 \mod p \implies 2n\equiv 0 \mod \text{ord}_p(b).\]We now claim that $\text{ord}_p(b)\in \{1,2\}.$ Else, it is either a power of $2$ greater than $2$ (contradicting $n$ odd) or has an odd prime divisor $q.$ But $q\leq \text{ord}_p(b)<p$ and $q\mid n,$ contradicting the minimality of $p.$ Thus $\text{ord}_p(b)\in \{1,2\}\implies p \mid b\pm 1.$ If $p\mid b-1,$ $0\equiv b^n+1\equiv 2 \mod p,$ contradiction. Thus $p\mid b+1=2^k,$ implying $p=2$ which is again a contradiction. Now assume $b$ is not of the form $2^k-1.$ Then $b+1$ has an odd prime divisor, say $p.$ We recursively define a sequence $a_1,a_2,\cdots, a_n$ satisfying $a_1=p$, $a_k=\tfrac{b^{a_{k-1}}+1}{a_{k-1}2^{\nu_2(b^{a_{k-1}}+1)}},k\geq 2.$ (this is just $\tfrac{b^{a_{k-1}}+1}{a_{k-1}}$ with all of its powers of 2 chopped off. We will show by induction that $a_k^2\mid b^{a_k}+1$ for all $k,$ the base case following easily from LTE. Now letting $m=\nu_2(b^{a_{k-1}}+1),$ we wish to show $\tfrac{b^{a_{k-1}}+1}{a_{k-1}2^m}\mid b^{\frac{b^{a_{k-1}}+1}{a_{k-1}2^m}}+1.$ It suffices to consider odd prime divisors $p$ of $b^{a_{k-1}}+1$ and show that it divides $b^{a_k}+1$ at least as many times as $a_{k}.$ Before we proceed, note that as $a_{k-1}$ is odd and $\tfrac{b^{a_{k-1}}+1}{a_{k-1}^2}$ is an integer by the induction hypothesis, so is $x=\tfrac{b^{a_{k-1}}+1}{a_{k-1}^22^m}.$ We are now ready to apply LTE: \[\nu_p\left(b^{a_k}+1\right)=\nu_p\left(\left(b^{a_{k-1}}\right)^x+1\right)=\nu_p(b^{a_{k-1}}+1)+\nu_p\left(\tfrac{b^{a_{k-1}}+1}{a_{k-1}^22^m}\right)=2\nu_p\left(\tfrac{b^{a_{k-1}}+1}{a_{k-1}2^m}\right)=2\nu_p(a_k),\]completing the induction. It now suffices to show that this sequence is strictly increasing, which will show that there are indeed infinitely many distinct integers $n$ with $n^2\mid b^n+1.$ Assume $a_{n-1}\geq a_n=\tfrac{b^{a_{n-1}}+1}{a_{n-1}2^m}.$ This rearranges to $\tfrac{b^{a_{n-1}}+1}{a_{n-1}^22^m}\leq 1,$ which implies that that this fraction is equal to $1$ since it is an integer. Now we must show that equality can never hold. If $b$ is even, $m=0$ and so $b^{a_{n-1}}+1=a_{n-1}^2,$ which is a contradiction for $b>3$ due to size reasons. If $b$ is odd, $m=\nu_2(b+1)+\nu_2(a_{n-1})=\nu_2(b+1),$ so $2^m\leq b+1$ and $1=\tfrac{b^{a_{n-1}}+1}{a_{n-1}^22^m}\geq \tfrac{b^{a_{n-1}}+1}{(b+1)a_{n-1}^2},$ again a contradiction for $b>4$ ($b=3=2^2-1$ is irrelevant) due to size reasons. We may now conclude.

WRONG...

Your reasoning here: tenplusten wrote: Take $p|n $ then order of $b $ mod $p $ divides $2n $ but not $n $ which means either order is $2$ or $2n $ It is clear that it cant be $2n $ since $p|2n|p-1$ So it is $2$ which means $p=5$ relies on the fact that $p$ is $n$'s smallest prime divisor. edit: oops i cannot read see below

No I take any prime divisor $p $.

tenplusten wrote: Take $p|n $ then order of $b $ mod $p $ divides $2n $ but not $n $ which means either order is $2$ or $2n $ $n$ is not necessarily prime so the order may be something else (eg if $n=9$ then the order can be $6$)

Finally here it is. Many months too late We claim that the answer is all $b$ that are not one less than a power of $2$. We first show that if $b=2^k-1$, there are only finitely many $n$ (actually we'll show that there are no $n$ except $n=1$). Suppose $n^2\mid b^n+1$ where $b=2^k-1$. Let $p$ be the smallest prime factor of $n$. Let $m$ be the order of $b$ mod $p$. We have that $p\mid b^n+1$, so $b^{2n}\equiv 1\pmod{p}$, so $m\mid\gcd(2n,p-1)\mid 2$, so $m=2$ (we can't have $m=1$ as $b\not\equiv 1\pmod{p}$). Therefore, $p\mid b^2-1=(b-1)(b+1)$, but $p\nmid b-1$, so $p\mid b+1=2^k$, so $p=2$. But $b^n+1\equiv 2\pmod{4}$ if $n\ge 2$, so we can't have $4\mid b^n+1$, a contradiction. Now, suppose $b$ is not one less than a power of $2$. Call $n$ good if $n^2\mid b^n+1$. We prove a lemma. Lemma: If $n$ is good and $p\mid b^n+1$ where $p$ is an odd prime that does not divide $n$, then $np$ is also good. Proof of Lemma: Note that $b^n+1\mid b^{np}+1$ since $p$ is odd, so $n^2\mid b^n+1\mid b^{np}+1$. Now, since $p\mid b^n+1\mid b^{np}+1$, we have that $\nu_p(b^{np}+1)=\nu_p(b^n+1)+1\ge 2$ by LTE, so $p^2\mid b^{np}+1$. Since $\gcd(n,p)=1$, we must then have $n^2p^2\mid b^{np}+1$, implying that $np$ is good. $\blacksquare$ Let $p_0=p$ be an odd prime dividing $b+1$ (this exists because $b$ is not one less than a power of two). Then, we have that $\nu_p(b^p+1)=\nu_p(b+1)+1\ge 2$, so $p$ is good. We now show that there is a sequence of primes $p_0,p_1,p_2,\ldots$ all distinct such that $p_k\mid b^{p_0\cdots p_{k-1}}+1$. We proceed by strong induction on $k$. We see that it is true for $k=1$ (note that an empty product is $1$). Now suppose it is true for all $r<k$. Then, let $p_k$ be a divisor of $b^{p_0\cdots p_{k-1}}+1$ that does not divide $b^{p_0\cdots p_{r-1}}+1$ (it exists by Zsigmondy's theorem), so $p_k$ cannot be $p_0,\ldots,p_{k-1}$. Note that $p_0$ is good, and by repeated applications of the lemma, we see that $p_0\cdots p_k$ is good for all $k$, so there are infinitely many solutions, as desired.

This was already posted in the forums.

ririri wrote: This was already posted in the forums. Wow. That's embarrassing (in more than one way).

Accidentally, I have seen a problem in the same flavor (extending the P5 of IMO 2000) in the following link http://www.math.ust.hk/excalibur/v9_n3.pdf which was written at the year of 2004. My opinion is that such "exponent-type" ,"$a^n \pm b^n$"-type elementary number theoretic problems have been thought over by too many people, even before IMO 1990 and 2000 (I think probably before 1850's, the era of Kummer and Lucas). We deal with such problems mainly by orders in $(\mathbb{Z}/m\mathbb{Z})^{\times}$, the lifting exponent lemma, and some elementary properties of cyclotomic polynomials. An interesting thing is that, people used the lifting exponent lemma in the 19th century but did not give it a name until 21st century!

GENERALIZATION: Find all pairs of positive integers $(a,b)$ such that there are infinitely many solutions in $n$ to the equation $a^n+b^n=kn^2$. Solution: We claim that there are finitely many solutions to $n$ iff $a+b$ is a power of $2$ for coprime integers $a,b$, or if $a+b=3$. We divide the proof into $4$ parts- CASE-1 $($When $a+b=3)$ $\rightarrow$ See my solution to this part here. CASE-2 $($When $\gcd(a,b)>1)$ $\rightarrow$ Let $\gcd(a,b)=d>1$. Then taking $n=d^k$ for some positive integer $k$ works. CASE-3 $($When $a,b$ are coprime and $a+b$ is a power of $2)$ $\rightarrow$ First of all consider the situation when $n>1$ is odd. Let $p$ be the smallest prime divisor of $n$. As $\gcd(a,b)=1$, so $p \nmid a,b$. Then we get $$a^n \equiv -b^n \pmod{p} \Rightarrow (ab^{-1})^{2n} \equiv 1 \pmod{p} \Rightarrow z=\text{ord}_p(ab^{-1}) \mid 2n$$However $z \mid p-1$ also, which gives that $z \mid \gcd(p-1,2n)=2$. If $z=2$, then $p \mid a^2-b^2$ but $p \nmid a-b$, which gives that $p \mid a+b$. But, $a+b$ is a power of $2$, which contradicts the fact that $p$ is odd. So we must have $z=1$. But then $$a \equiv b \pmod{p} \Rightarrow 0 \equiv a^n+b^n \equiv 2a^n \pmod{p} \Rightarrow p \mid a^n \Rightarrow p \mid a \rightarrow \text{CONTRADICTION}$$Now, suppose $n$ is even. Then take $n=2m$. This gives $$4 \mid a^n+b^n=a^{2m}+b^{2m} \equiv 2 \pmod{4} \rightarrow \text{CONTRADICTION}$$Thus, if $\gcd(a,b)=1$ and $a+b$ is a power of $2$, then the only solution is $n=1$. CASE-4 $($When there exists an odd prime divisor of $a+b$, with $a+b \neq 3)$ $\rightarrow$ Let $p$ be an odd prime divisor of $a+b$. Note that, by LTE, $\nu_p(a^p+b^p)=\nu_p(a+b)+\nu_p(p) \geq 2$, and so $p^2 \mid a^p+b^p$. We contruct the required infinite sequence inductively. Let $p_0=p$. Suppose we find a sequence of distinct primes $p_0,p_1, \dots p_k$ such that $$(p_0p_1 \dots p_r)^2 \mid a^{p_0p_1 \dots p_r}+b^{p_0p_1 \dots p_r} =X_r \text{ } \forall r \in \{0,1, \dots ,k\}$$By Zsigmondy Theorem, we know that there exists a primitive prime divisor $p_{k+1}$ of $X_k$. More particularly, $p_{k+1}$ does not divide $X_r$ for any $r \in \{0,1, \dots ,k-1\}$. This gives that $p_{k+1}$ does not belong to the set of primes $\{p_0,p_1, \dots ,p_k\}$. Now, note that, by FLT, $X_{k+1} \equiv X_k \pmod{p_{k+1}}$, and so $p_{k+1}$ divides $X_{k+1}$ also. Applying LTE once again, one easily gets that $\nu_{p_{k+1}}(X_{k+1}) \geq 2$, i.e. $p_{k+1}^2 \mid X_{k+1}$. And, as $p_{k+1}$ is odd, so $X_k \mid X_{k+1}$. Thus, we get that $$(p_0p_1 \dots p_kp_{k+1})^2 \mid X_{k+1}=a^{p_0p_1 \dots p_kp_{k+1}}+b^{p_0p_1 \dots p_kp_{k+1}}$$Continuing in this manner, we can find infinitely many solutions in $n$. $\blacksquare$ REMARK: This problem is a generalization of $5$ problems (to my knowledge), namely IMO 1990 P3, IMO 2000 P5, IZhO 2007 P3, India TST 2018 D2 P1 and USA TSTST 2018 P8.

We claim the only such $b$ satisfy the property that $b + 1$ is not a power of two. First of all, consider any such $n$, and let $p$ be the smallest prime divisor of $n$. We claim that $p \neq 2$. Indeed, if $n$ is even, then we have that $4$ divides $n^2$, but since $b^n + 1$ is even, $b + 1$ is odd. This gives us that $b^n + 1 \equiv 2 \pmod 4$, so by $v_2$ we reach a contradiction. Now say $b+1$ is a power of two, and let $x$ be the order of $b$ mod $p$. We have that: \begin{align*} x | 2n \\ x | p-1 \end{align*} This gives us that $x$ divides $\gcd{(2n, p-1)}$. Since $p$ is the smallest prime divisor of $n$, all prime divisors of $p-1$ do not divide $n$, and thus this gcd is equal to $2$. This gives us that $b \equiv \pm 1 \pmod p$. If $b \equiv 1 \pmod p$, then we have that $b^n + 1 \equiv 2 \pmod p$, and so $p = 2$: a contradiction. Otherwise, $p$ divides $b+1$, but since this is a power of two $p = 2$ again in this case. Thus we reach a contradiction, and so there are no possibilities for $n$ in this case. Now say $b+1$ is not a power of two. Denote a positive integer $n$ as kawaii if $n^2$ divides $b^n + 1$. First of all, consider any odd prime $p$ dividing $b+1$. We have that: \begin{align*} v_p(b^p + 1) &= v_p(b + 1) + 1 \\ &\geq 2 \end{align*}Thus $p^2 | b^p + 1$, and so $p$ is kawaii. Now, denote a sequence of numbers $n_1, n_2, \ldots$, where $n_1 = p$. Define $n_{i+1} = qn_i$, such that $q$ divides $b^n+1$, but $q$ does not divide $b^x + 1$ for any $x < n$ (since $b>2$, such a prime exists by Zsigmondy). We claim that all numbers in this sequence are kawaii. We prove this result by induction. Note that by our construction we always have that $\gcd{(n_i,q)} = 1$. We also have that since $q$ does not divide $b+1$, either $b$ is odd and $q \neq 2$ or $b$ is even and $q \neq 2$ anyways. Thus $q$ is always odd. Now, we have that $b^n \equiv -1 \pmod n^2$, so $n^2 | b^{nq} + 1$. We also have that: \begin{align*} v_q(b^{nq} + 1) &= v_q(b^n + 1) + 1 \\ &\geq 2 \end{align*} Thus $(nq)^2 | b^{nq} + 1$, and the induction is complete. Thus when $b$ is not a power of $2$ there are infinitely many kawaii integers, and we are done!

The answer is all $b$ such that $b+1$ is not a power of $2$. Claim 1. All such $n$ are odd. Proof. Assume for contradiction $n=2k$ for some $k$. Since $b^2\equiv0,1\pmod4$, \[4\mid b^{2k}+1=\left(b^2\right)^k+1\equiv1,2\pmod4,\]which is absurd. $\blacksquare$ Claim 2. If $b+1$ is a power of $2$ and $n^2\mid b^n+1$, then $n=1$. Proof. Assume that $b+1$ is a power of $2$, and let $p$ be the least odd prime dividing some $n>1$. Then $b^{2n}\equiv1\pmod p$ and $b^{p-1}\equiv1\pmod p$. Since $\gcd(2n,p-1)=2$, we must have $b^2\equiv1\pmod p$, or $p\mid b^2-1$. Since $b+1$ is a power of $2$, $p$ divides $b-1$. It follows that \[p\mid b^n+1\equiv2\pmod p,\]contradiction, thus no $b$ with $b+1$ a power of $2$ work. $\blacksquare$ Claim 3. If $p$ is an odd prime dividing $b+1$, then $p^2\mid b^p+1$. Proof. Indeed, we take an odd prime $p$ dividing $b+1$, and note that \[\nu_p\left(b^p+1\right)=\nu_p(b+1)+1\ge2\]by lifting the exponent, so $p^2\mid b^p+1$, as claimed. $\blacksquare$ Claim 4. If $n>1$ and $n^2\mid b^n+1$, then there is an odd prime $p\nmid n$ with $(np)^2\mid b^{np}+1$. Proof. The pith of this claim is that by Zsigmondy theorem, we can choose a prime $p$ dividing $b^n+1$ but not $n$. Then $n^2\mid b^n+1\mid b^{np}+1$ and \[\nu_p\left(b^{np}+1\right)=\nu_p\left(b^n+1\right)+1\ge2,\]so $p^2\mid b^{np}+1$, which proves the claim. $\blacksquare$ Claim 2 ensures that no $b$ with $b+1$ a power of $2$ satisfy the problem condition. On the other hand, if $b+1$ is not a power of $2$, Claim 3 shows there are $n>1$ with $n^2\mid b^n+1$, and Claim 4 proves there are infinitely many such $n$. This completes the proof.

We claim there are finitely many such $n$ iff $b+1$ is a power of 2. Suppose $b+1$ is a power of 2. Then consider the smallest prime factor $p \mid n$, so $b^n\equiv -1\pmod{p}$. Then $b^{2n}\equiv 1 \pmod{p}$, so the order of $b\mod p$ divides $\gcd(2n,p-1)$, which divides 2. So $b^2\equiv 1\pmod{p}$, which means $p\mid (b-1)(b+1)$. If $p=2$, then $n^2\equiv 0 \pmod4$ but $b$ is odd, so $b^n+1\equiv 2 \pmod4$, contradiction. Therefore, $n$ is odd. Since $b+1$ has no odd prime factors, we must have $p\mid b-1$, i.e. $b\equiv 1\pmod{p}$. But then $b^n\equiv 1 \pmod{p}$, contradiction, unless $n=1$. Therefore, there are only finitely many solutions for $n$ (only one), which means $b+1$ is a power of 2 cannot work. Now, suppose $b+1$ is not a power of 2. We will inductively construct $n$ which work. Suppose we already have $n=p_1p_2\cdots p_{k-1}$ (where $p_1<\cdots < p_k$) so we know $b^{p_1p_2\cdots p_{k-1}}\equiv -1\pmod{p_1^2\cdots p_{k-1}^2}$. We will find a $p_k$ such that $b^{p_1\cdots p_k} \equiv -1 \pmod{p_1^2\cdots p_k^2}$. We want $b^{p_1\cdots p_k}\equiv -1 \pmod{p_k^2}$, i.e. $b^{2p_1\cdots p_k} \equiv 1 \pmod{p_k^2}$. Let $r$ be the order of $b\pmod{p_k}$. Then $r\mid \gcd(2p_1\cdots p_k, p_k-1) \mid 2p_1\cdots p_{k-1}$. Therefore, $b^{2p_1\cdots p_{k-1}} \equiv 1 \pmod{p_k}$. So if we can find a new prime $p_k \mid b^{p_1\cdots p_{k-1}}+1$, then we also have to check that $v_{p_k}(b^{2p_1\cdots p_k}-1) \ge 2$, and then we will be done. By Zsigmondy, we can find a new prime dividing the sequence $b^x+1$ for any $x$, so we can definitely find a $p_k$. Now, by LTE, \begin{align*} \nu_{p_k}(b^{2p_1\cdots p_k}-1) &= v_{p_k}(b^{p_1\cdots p_k}-1) + v_{p_k}(b^{p_1\cdots p_k}+1) \\ &= 0 + v_{p_k}((b^{p_1\cdots p_{k-1}})^{p_k} + 1) \\ &= v_{p_k} (b^{p_1\cdots p_{k-1}} + 1) + 1 \ge 2, \end{align*}so we are done.

The answer is any integer $b>2$ such that $b+1$ isn't a power of $2$. Firstly, we'll prove that if $b+1=2^{k}$, $k\geq 1$, then $n=1$: Suppose that $b+1=2^{k}$, $k\geq 1$ and $n>1$, then take the smallest prime factor $p$ of $n$. Notice that $p>2$, otherwise $4|b^{n}+1 \implies 2\equiv b^{n}+1 \equiv 0 \pmod4$, a contradiction. Hence, $p\geq 3 \implies b^{2n}-1 \equiv 1 \pmod p \implies ord_{p}b| 2n, p-1$ (by FLT) $\implies ord_{p}b|gcd(2n,p-1)=2$, since $p$ is the smallest prime factor of $n$. Then, we have that $p|b^{2}-1$, and since $b+1=2^{k}$, $p|b-1 \implies 0 \equiv b^{n}+1 \equiv 2 \pmod p$, contradiction. Now, assume that $b+1$ is not a power of $2$, and call a positive integer "Paulo Kogos" if $n^2|b^{n}+1$. Take an odd Paulo Kogos number $n$. By Zsigmondy Theorem, there exists an odd prime $p$ such that $p|b^{2n}-1$ and $p\not|b^{k}-1$ for all $k=1,2,...,2n-1$. Then, we have that $p\not|b^{\phi(n)}-1 \implies p\not|n$ (otherwise $p|b^{\phi(n)}-1$), and since $p\not|b^{n}-1 \implies p|b^{n}+1$. Now, notice that by LTE, we have that $\nu_{p}(b^{np}+1)= \nu_{p}(b^{n}+1)+1 \geq 2 \implies p^{2}|b^{np}+1$ and observe that $n^2|b^{n}+1|b^{np}+1$. Therefore, $(np)^{2}|b{np}+1$, since $gcd(n,p)=1$ and we also have that $np$ is a Paulo Kogos number. $(*)$ Then, since $b+1$ is not a power of $2$, we can take an odd prime factor $q$ of $b+1$ and observe that $\nu_{q}(b^{q}+1)=\nu_{q}(b+1) + 1\geq 2 \implies q^{2}|b^{q}+1$, and from $(*)$ we are done by induction, since there will be infinitely Paulo Kogos' numbers. $\blacksquare$

Note that if $n$ is even, then by Fermat's Christmas Theorem, all prime factors $p\ne 2$ of $n^2$ are congruent to $1$ mod $4.$ But this implies that $n^2\equiv 2\pmod{4},$ which is impossible. Therefore, we only need to consider odd $n.$ We claim that the answer is all $b$ that cannot be expressed as $2^m-1$ for some positive integer $m.$ First, we show that all such $b$ satisfy the statement of the problem. Define a sequence $\{p_i}\}$ recursively as follows: let $p_1=1,$ and let $p_i\ne p_1,p_2,\dots,p_{i-1}$ be an odd prime dividing $b^{p_{1}p_{2}\dots p_{i-1}}+1$ (which is guaranteed to exist by Zsigmondy's Theorem). Then, every number of the form $n=p_{1}p_{2}\dots p_{k}$ divides $b^n+1,$ because we have $$p_{i}\mid b^{p_{1}b_{2}\dots b_{i-1}}+1\mid b^{n}+1$$for all $i.$ Hence, we have constructed infinitely many $n$ that satisfy $n^2\mid b^n+1.$ Note that this argument does not work for any $n$ that is one less than a power of $2,$ because of the exceptional case of Zsigmondy's Theorem. Now, we show that all $b$ of the form $2^m-1$ for some $m$ do not satisfy the statement of the problem. Assume, for the sake of contradiction, that there is at least one prime dividing $n.$ Let $p$ be the smallest prime dividing $n.$ Since $p\mid b^n+1,$ we cannot have $p\mid b.$ Therefore, we have $$b^n+1\equiv 0\pmod p\implies b^{2n}\equiv 1\pmod p,$$$$b^{p-1}\equiv 1\pmod{p}.$$This implies that $$\text{ord}_{p}b\mid\gcd(2n,p-1).$$By the minimality of $p,$ we know $\gcd(n,p-1)=1.$ Additionally, since $p\ne 2,$ we know $2\mid p-1.$ Therefore, $$\text{ord}_{p}b\mid 2.$$If $\text{ord}_{p}b=1,$ then $b\equiv 1\pmod{p},$ so $b^n+1\equiv 2\pmod{p},$ which is a contradiction. Hence, $\text{ord}_{p}b=2,$ so $$(2^m-1)^2\equiv 1\pmod p.$$This simplifies to $$2^{m+1}(2^{m-1}-1)\equiv 0\pmod{p}.$$Since $p\ne 2,$ $p\nmid 2^{m+1},$ so we must have $2^{m-1}\equiv 1\pmod{p}.$ Therefore, $$b=2^m-1\equiv 1\pmod{p}.$$This implies that $b^n+1\equiv 2\pmod{p},$ which is impossible. Our proof is complete.

The answer is all $b$ such that $b$ is not of the form $2^{\ell}-1$ for some positive integer $\ell \geq 2$. First we show that if $b=2^{\ell}-1$ then there are no $n>1$ such that $n^2 \mid b^n+1$; assume for contradiction that there were. Take the smallest prime $p$ dividing $n$, and let $e$ be the smallest positive integer such that $b^e \equiv -1 \pmod{p}$. Then if $d$ is the order of $b \pmod{p}$ we must have $e<d \mid 2e$ which implies $d=2e$ and $e \mid n$. But since $e<p$, by minimality of $p$ we must have $e=1$, i.e. $p \mid b+1 \Rightarrow p=2$. But then since $n$ is even and $b \equiv 3 \pmod{4}$ we get $b^n+1 \equiv 2 \pmod{4}$, impossible. Now we provide a construction for all other $b$. Take some odd prime $p_0 \mid b+1$; then by Zsigmondy we can generate an infinite sequence $p_0, p_1,p_2, p_3, \dots$ of distinct primes such that $p_i \mid b^{p_{i-1}}+1$. Now pick any positive integer $k$, and we show that $n=p_0p_1 \cdots p_k$ is a solution. Indeed, by LTE we can compute $$\nu_{p_0} \left( b^n+1 \right) \geq 2$$and $$\nu_{p_i} \left( b^n+1 \right) = \nu_{p_i} \left( \left( b^{p_{i-1}} \right)^{n/p_{i-1}}+1 \right) \geq 2$$and we're done.

solved with pi271828 one year ago, but i doubt either of us remember the solution so i solved it again recently The answer is all positive integers $b \neq 2^k - 1$ for $k \ge 2$. Proof of necessity. Assume FTSOC that $b = 2^k - 1$ for some $k$. Then for any $n > 1$ that works, take the smallest prime $p \mid n$; $p = 2$ is impossible else $4 \mid b^{2k} + 1 \equiv 2 \pmod{4}$ for $n = 2k$, hence $p$ is odd. Then $b^{2n}\equiv 1\pmod{p} \implies \operatorname{ord}_p(b)\mid\gcd(2n,p-1)=2 \implies b\equiv\pm1\pmod{p}$. However, $b \equiv -1 \pmod{p}$ is impossible as then $p \mid 2^k$, and $b \equiv 1 \pmod{p}$ is impossible as then $b^n+1\equiv 2\pmod{p}$, contradiction. $\blacksquare$ Proof of sufficiency. We will construct an infinite sequence $a_0, a_1, \dots$ that works. Let $a_0 = p$, with $p$ being an odd prime that divides $b +1$; then by LTE, $p^2 \mid b^p + 1$. Now assume that we have found a sequence $a_0, a_1, \dots, a_n$ that work and note that by Zsigmondy, we can find a prime $q$ so that $q \mid b^{a_n}+1$ but $q \nmid b^{a_k}+1$ for $k = 0, 1, \dots, n-1$. Take $a_{n+1} = qa_n$; then by LTE, we have \[\nu_q(b^{a_{n+1}}+1)=\nu_q(b^{a_n}+1)+\nu_q(q)\ge 2,\]which finishes. $\blacksquare$

solved with pikapika007 one year ago, and had to write up for otis Let $b+1$ be a power of two. If $n$ is even, then $b^n \equiv 3 \pmod 4$, but $3$ is not a quadratic residue. Letting $p$ be the smallest prime dividing $n$, we get $b^{2n} = 1 \pmod{p}$. Now notice the order must divide $\gcd(2n, p-1) = 2$ due to the minimality of $p$. This directly implies $b-1 \equiv 0 \pmod p$. However this gives us an obvious contradiction. Now if $b+1$ is not a power of two, we can first find an odd prime $p$ dividing $b+1$, and by LTE it satisfies the given condition. Now, notice by Zsigmondy's there must exist a prime $q \neq p$ that divides $b^p+1$. Now notice this implies $p^2q \mid b^{pq}+1$. Now by LTE, $v_q((b^p)^q + 1) = v_p(b^p+1) + 1 \le 2$. Therefore $p^2q^2 \mid b^{pq}+1$. Repeating this process gives the desired result.

my soln.

We claim that all $b$ such that $\boxed{b \neq 2^x-1}$ work. We produce values of $n$ inductively. We first produce our base case. Look at a prime such that $p|b+1$ and $p \neq 2$. From LTE we get that $v_p(b^p+1) = v_p(b+1) +v_p(p)$. Thus $p^2|b^p+1$. Now for the inductive step. We now look at a prime $q$ such that $q|b^n+1$ (with $n^2|b^{n} +1$. We can see that there exists such a $q \not |n$ from Zsigmondy's. Since $n$ and $q$ are odd we can see that $n^2q^2|b^{nq} +1$. We prove that $b = 2^x-1$ don't work. We claim that $2 \not |n$. This is obvious because if this were true then $b^n + 1 \equiv 2 \pmod{4}$ contradiction. Let $p$ be the minimal prime such that $p|n$. We can see that $b^2n \equiv 1 \pmod{p}$ or $ord_p(b) | \gcd(2n, p-1) = 2$. Thus we have $b \equiv 1 \pmod{p}$ or $(b^2-1) \equiv (b+1)(b-1) \pmod{p}$ if $b \equiv 1 \pmod{p}$ then $b^n +1 \equiv 2 \pmod{p}$ but $p \neq 2$. If $b \equiv -1 \pmod{p}$ then since $2 \not | n$, $b^n +1 \equiv 2^x \pmod{p}$ and $p \neq 2$. $\blacksquare$

Claim $b = 2^k-1$ fails Proof. Firstly we have $2^2\nmid b$ since otherwise $b^{n} + 1\equiv 2 \pmod 4$ a contradiction. Now, as in 90IMO3 consider the smallest prime $p | b^n+1$. We have $b^{2n} \equiv 1\pmod n$, and $$2|ord_p(b) | \gcd(2n, p-1) = 2$$due to the minimality of $p$. Thus $p|b^2 - 1$. Clearly $p\nmid b+1 = 2^k$ so $p|b-1$ and $b^n + 1 \equiv 2 \pmod p$, a contradiction. $\blacksquare$ Next we show all remaining $b$ suffice. Consider any odd $n^2|b^n + 1$ Then we try to show there exists a $p^2n^2 | b^{np} +1$, for $\gcd(p, n) = 1$. This means $p | (b^n)^p + 1$ which means $(b^n)^{2p} \equiv 1 \pmod p$ so $$2 | ord_p(b^n) | \gcd(2p, p-1) = 2\implies p | b^{2n}-1 \implies p | b^n+1.$$By Zsigmondy we can chose a primitive $p| b^n + 1$ and thus $\gcd(p, n)$ is 1. We can repeat this process now for $n = np$ to generate infinitely many $n$. $\blacksquare$

The answer is all $b$ such that $b+1$ is not a power of $2.$ First, we may assume $n$ odd since otherwise it fails $\pmod 4.$ Additionally, let $o$ be the order of $b \pmod p.$ If we have $p \mid b^n+1,$ then we must have $o \mid 2n$ and $o \mid p-1.$ Now, if $b+1$ is a power of $2,$ we let $p$ be the smallest prime factor of $n$ and we see that $o<p$ but $o \mid 2n$ so we must have $o=2,$ which gives $b+1 \equiv 0 \pmod p,$ impossible. Thus there are no solutions (except for trivial $1$) in this case. Now if $b+1$ is not a power of $2$ there is some prime $p$ dividing it. Furthermore, from Lifting the Exponent, we see that $p^2 \mid b^p+1,$ since $\nu_p(b^p+1)=\nu_p(b+1)+1.$ Next, since $b \ne 2,$ by Zsigmondy's there is some prime $q$ dividing $b^p+1$ but not $b^i+1$ for $1 \le i <p.$ Notice that $\nu_q(b^{pq}+1)=\nu_q(b^p+1)+1,$ so $p^2q^2 \mid b^{pq}+1.$ Then there is again some prime $r$ dividing $b^{pq}+1$ but not $b^i+1$ for $1 \le i < pq,$ and we get that $pqr=n$ works, and we may repeat this, so there are infinitely many solutions in this case and we are done.

All work except for $b = 2^x - 1$. We will use induction to prove that all numbers $\neq 2^x - 1$ work. $\newline$ Base Case: We take a prime $p \neq 2$ that divides $b + 1$. Then by LTE, we have $v_p(b^p + 1^p) = v_p(p) + v_p(b + 1) \geq 2$, so $p^2$ divides $b^p + 1^p$. $\newline$ Inductive Step: Then by Zsigmondy, there is a prime $q$ dividing $b^{pq} + 1^{pq}$ that does not divide $b^p + 1$. Using LTE again, we find that $p^2q^2$ also divides $b^{pq}$. We can repeat this, so there are infinitely many $n$ that work, so our induction is done Note that this does not work for $b = 2^x - 1$ as $b + 1$ is a power of two(so we can't apply LTE the same way we did.) $\newline$ Now to prove the other direction. Suppose $q$ is the smallest prime dividing $n$. Then we have $b^{2n} \equiv 1\pmod{p}$, so the order of $b\pmod{p}$ divides $\gcd(2n, p-1) = 2$, therefore $p$ divides $b^2 - 1$, so $b \equiv 1\pmod{p}$(not $-1$). This then means that $b^n + 1 \equiv 2\pmod{p}$, which is a contradiction because $p \neq 2$ due to $p$ dividing $2^x - 1$, so we are done.

We claim that $\boxed{\text{all } b \text{ not of the form } 2^k -1 \text{ are good.}}$ We first try to determine $b$ for which there may exist infinitely such good $n$. Say we have a satisfactory base case of $n$ for some $b$. Then we wish to find some prime $p \nmid n$ such that $p^2 \mid b^{np} + 1$. Claim: We can find a satisfactory infinite sequence of $n$ for $b \neq 2$ and $b \neq 2^k - 1$ for some $k$, using Zsigmondy. Proof. Consider taking $p \neq 2$ as a primitive divisor of $b^{2n} - 1$. Then note that $p \nmid n$ follows as $n \mid b^{\phi(n)} - 1$ and $p \nmid b^{\phi(n)}-1$. Also clearly $p \mid b^n + 1$ as $p \nmid b^n - 1$. Then we find, \begin{align*} b^{np} \equiv b^n \equiv - 1\pmod{p} \end{align*}Note that LTE gives $\nu_p(b^{np} + 1) = \nu_p(b^n+1) + \nu_p(p) \geq 2$. Hence $p^2 \mid b^{np}+1$. Now note this argument fails for $n$ in which we are unable to find a base case, or where our base case violates Zsigmondy's. Namely when we have, The only solution for some $b$ such that $b + 1$ is a power of $2$ is $n = 2$. The only solution when $b = 2$ is $n = 3$ Thus the claim holds. $\blacksquare$ Now we in fact show that for $b = 2$ or $ b =2^k - 1$ there exists no satisfactory $n$. Claim: For $ b =2^k - 1$ or $b = 2$ there exists no satisfactory $n$ for a base case. Proof. We will handle the first bullet to begin with. Assume that $b = 2^k - 1$ for some $k$. Then we wish to find $n \neq 2$ such that $n^2 \mid (2^k - 1)^n + 1$. Taking the smallest prime $p$ dividing $n$, which we will assume is greater than $2$. Then we must have, \begin{align*} (2^k - 1)^n &\equiv - 1 \pmod{p}\\ (2^k - 1)^{2n} &\equiv 1 \pmod{p} \end{align*}Then $\text{ord}_p(2^k - 1) \mid \gcd(2n, p - 1) = 2$ from which we conclude either $\text{ord}_p(2^k - 1) = 1$ of $\text{ord}_p(2^k - 1) = 2$. Testing the first case we find we then have, \begin{align*} 2^k - 1 &\equiv 1 \pmod{p}\\ \iff 2^k &\equiv 2 \pmod{p}\\ \iff 2^{k-1} &\equiv 0 \pmod{p} \iff p = 2 \end{align*}Testing the second case we have, \begin{align*} 2^{2k} - 2^{k + 1} &\equiv 0 \pmod{p}\\ 2^{2k} &\equiv 2^{k+1} \pmod{p}\\ 2^{k - 1} &\equiv 0 \pmod{p} \iff p = 2 \end{align*}Thus we must have $2 \mid n$. However then note that then $4 \mid (2^k - 1)^{n} + 1$, but we have $(2^k - 1)^n + 1 \equiv 2 \pmod{4}$, a contradiction. Thus indeed whenever $b + 1$ is a power of $2$ there are no satisfactory values of $n$. To handle the second bullet, note that it is just 90IMO3, and we see that $n = 3$ is indeed the only solution, so $b = 2$ fails. Hence our claim holds. $\blacksquare$ We will now present a base-case construction for all other $b$. For some $b$ consider taking $n$ as the smallest odd prime divisor $p$ of $b + 1$. Then LTE we find, \begin{align*} \nu_p(b^p + 1) = \nu_p(b + 1) + \nu_p(p) \geq 2 \end{align*}Thus we're done. Remark: I felt like this problem was just stress testing Zsigmondy, after using the 00IMO5 argument. Also big thank you to nebula on the OTIS discord server for hinting me along on this problem.

$\boxed{\textcolor{blue}{\text{I claim all}\hspace{0.2cm} b\hspace{0.2cm} \text{satisfies, except when}\hspace{0.2cm} b+1 \hspace{0.2cm}\text{is a power of } \hspace{0.1cm}2}}$ $\textcolor{red}{\text{Case 1.} \hspace{0.2cm} b+1 \hspace{0.2cm} \text{is a power of} \hspace{0.2cm}2}$ If $n$ is even, as $b$ is odd then $b^n+1\equiv 1+1\equiv 2\not\equiv 0\pmod 4$ so n odd; let $p\neq 2$ be the smallest prime dividing then $b^{2n}\equiv 1\pmod p$ and $b^{p-1}\equiv 1\pmod p$ thus $\operatorname{Ord}_p(b)\mid 2\gcd\left(n,\frac{p-1}{2}\right)=2$, so $p\mid b^2-1=(b-1)(b+1)$, but $b+1$ is a power of $2$ thus $p\mid b-1$ thus $b^n+1\equiv 1^n+1\equiv 2\pmod p$ a contradiction. $\textcolor{red}{\text{Case 2.} \hspace{0.2cm} b+1 \hspace{0.2cm} \text{is not a power of} \hspace{0.2cm}2}$ Let $p$ prime such that $p\mid b+1$, then by Lifting the Exponent $$\nu_p(b^p+1)=\nu_p(b+1)+\nu_p(p)\geq 2$$so $p^2\mid b^p+1$, take $q\mid b^p+1$ a primitive prime divisor of $b^p+1$ which by Zsigmondy exists, then $q\mid b^p+1\mid b^{pq}+1$ and again by LTE $$\nu_q\left((b^p)^q+1\right)=\nu_q(b^p+1)+\nu_q\geq 2$$so in fact $p^2q^2\mid b^{pq}+1$, therefore we can continue this sequence adding primes in a way that every new prime is a primitive prime that divides $b^{p_1p_2\cdots p_k}+1$

The answer is $\boxed{n \neq 2^k-1, \ k \in \mathbb{N}_{>1}}$. For numbers not of the form $2^k-1$, we will build up values of $n$ inductively. For the base case, consider a prime $p$ that divides $b+1$. LTE gives \[\nu_p(b^p+1) = \nu_p(b+1)+\nu_p(p) \ge 2.\]\[\implies p^2 \mid b^p+1.\] For the inductive step, consider a prime $q$ that divides $b^p+1$, which exists by Zsigmondy. We have \[\nu_q(2^{pq}+1) = \nu_q(2^p+1)+1 \ge 2,\] so $(pq)^2 \mid 2^{pq}+1$, completing the induction. This only applies when the desired primes are not equal to $2$, or when the prime factorization of $b+1$ does not only consist of $2$'s. Hence, numbers that are one less than powers of $2$ are not covered in this induction. For the sake of contradiction, assume $b+1$ is a perfect power of $2$. Let $r$ be the smallest prime dividing $b+1$; due to a modulo $4$ argument, $r \neq 2$. We have \[b^{2n} \equiv 1 \pmod{p},\] so $\operatorname{ord}_p(b) \mid \gcd(2n, p-1) = 2$. Thus, $p \mid b^2-1 = (b-1)(b+1)$. Since $b+1$ contains only factors of $2$, which cannot be $p$, we have $p \mid b-1$. However, \[b \equiv 1 \pmod{p} \implies b^n \equiv -1 \equiv 1 \pmod{p} \implies p=2,\] a contradiction. Therefore, we are left with our desired solution set.

Our answer is all $\boxed{b \neq 2^k-1}$. Notice that our condition implies \[\operatorname{ord}_p b \mid 2n, \operatorname{ord}_p b \nmid n \implies v_2(\operatorname{ord}_p) > v_2(n).\] First note that $n$ must be odd. Suppose $p_1$ is the least prime divisor of $n$, where we assume there exists a solution other than $n=1$. Then \[\operatorname{ord}_{p_1} b \mid \gcd(2n,p_1-1) = 2 \implies p \mid b^2-1, p \nmid b-1.\] Zsigmondy tells us this primitive root must exist iff $b+1$ is not a power of two. If it is, we're stuck; otherwise, we just procede inductively with Zsigmondy to find infinitely many solutions. $\blacksquare$

I claim that the answer is all $b>2$ such that $b\neq 2^k-1$. C1: First, I claim that $n$ is odd. This is obvious if $b$ is even. However, if $b$ is odd, we have that \[b^n+1\equiv 2\mod 4 \iff \nu_2(b^n+1)=1,\]since both $b$ and $1$ are odd. However, this is a contradiction, since $\nu_2(n^2)\geq2$ if $n$ is even. Therefore, $n$ must be odd. C2: I claim that $b=2$ and $b=2^k-1$ do not have infinite solutions. First, note that $b=2$ does not have infinite solutions. This is seen in IMO's 1990/3, where we proved that the only solutions were $n=1$ and $n=3$. Now, I claim that if $b=2^k-1$, then the only solution is $n=1$. This is because if we let $p$ be the smallest prime to divide $n$, we have that \[p\mid b^n+1 \iff 2\mid ord_p(b), ord_p(b)\mid 2n.\]but by Euler's Totient, we also have that $ord_p(b)\mid p-1$, so this implies that $ord_p(b)\mid \gcd(2n,p-1)$. However, since $p$ is the smallest prime that divides $n$, this means that $\gcd(2n,p-1)=2$. Therefore, since $ord_p(b)$ is even, we have that $ord_p(b)=2$. This gives that \[p\mid b^2-1=(b-1)(b+1).\]However, since $ord_p(b)=2>1$, this implies that $p$ does not divide $b-1$. Therefore, we have that \[p\mid b+1=2^k,\]meaning that $p=2$ if $n>1$, which is impossible, since by (C1) we proved that $n$ must be odd. Therefore, if $b=2^k-1$, $n=1$ is the only solution, which is clearly not infinite. C3: I claim that for all other $b$, we have infinitely many solutions. We do this by using an induction similar to that of IMO's 2000/5! Call a number $n$ "appley" if $n^2\mid b^n+1$. I now claim that if for a prime $p$ such that $p\mid b^n+1$ and $\gcd(p,n)=1$, if $n$ is "appley", then so is $np$. Note that by LTE, we have that \[\nu_p(b^{np}+1)=\nu_p(b^n+1)+1\geq 2,\]meaning that $p^2\mid b^{np}+1$. Additionally, since $p$ is odd, we have that \[b^n+1\mid b^{np}+1,\]meaning that $n^2\mid b^{np}+1$ since $n$ is "appley". Therefore we must have that $n^2p^2\mid b^{np}+1$, meaning that $np$ is also "appley", as desired. Finally, for the last step of the induction, we use the starting $n=1$ as our base case. Note that by Zsigmondy's, we have that there will always exist such a prime $p$ from here on out such that $p\mid b^n+1$ but not $n$. Therefore for all $b$ not equal to $2^k-1$ or $2$, $n^2\mid b^n+1$ has infinitely many solutions, finishing the problem.

bashing practice... For any prime $p\mid n$ notice that \[p\mid b^{2n}-1\implies \text{ord}_p(b)\mid 2n\implies \text{ord}_p(b)\mid \gcd(2n,p-1).\]The smallest prime $p$ dividing $n$ would then satisfy $\gcd(n,p-1)=1$. In particular, we should have $\text{ord}_p(b)\in \{1,2\}$. So $p\mid b-1$ or $p\mid b^2-1$ and $p\nmid b-1$. Note that $p\mid b^n+1$ though, hence we would require $p=2$ in the former case. In particular we need $4\mid b^n+1$ where $n$ is even, which is impossible. Hence $p\mid b^2-1$ and $p\nmid b-1$. Also note that $n$ is odd, and $p\neq 2$. This additionally implies $b-1$ and $b+1$ are relatively prime. In particular $p\mid b+1$. Hence if $b+1$ is a power of two we fail. Admittedly I've been spoiled to the answer, but the point is that if $b+1$ is not a power of two we are fine. Start with said value of odd $p$ as a "base case" and we'll inductively create values $n_1,n_2,\dots$ which all satisfy $n_i^2\mid b^{n_i}+1$. Oops the next step took too long. Write $n_1=pq$. By LTE we have $p^2\mid b^{pq}+1$. So we need $q^2\mid b^{pq}+1$. In particular it will suffice to have $b^p+1\equiv 0\pmod q$. Hence we just need to show there exists a prime $q$ dividing $b^p+1$ which doesn't divide $b+1$ (and is therefore not equal to $p$). This is guaranteed by Zsigmondy (since we can easily find $b\ge 4$ and bypass special cases). Repeat the process. If $n_2=pqr$ we need $r^2\mid b^{pqr}+1$. It suffices to have $r\mid b^{pq}+1$ while $r\nmid b^p+1$, which is fine. We can get infinitely many values this way. Done. $\blacksquare$

Truly one of the NT problems of all time

Lemma: If $a \mid b$ and $a$ and $b$ are odd, then $x^a + 1 \mid x^b + 1$ for all natural numbers $x$. Proof: We know $\frac{b}{a}$ is odd, so \[ \frac{x^b + 1}{x^a + 1} = x^{b-a} - x^{b-2a} + x^{b-3a} - \ldots + 1. \] We claim that all $b$ such that $b+1$ is not a power of $2$ work. We will generate an infinite sequence of $n$'s satisfying the condition, starting with $n_1 = p_1$ where $p_1$ is an odd prime that divides $b+1$. The sequence will also satisfy the additional condition that $n_i$ can be written in the form $p_1p_2\ldots p_i$ where the $p_j$'s are distinct odd primes. To establish the base case, notice that since $p_1$ is odd, we can use lifting the exponent: \[ \nu_{p_1}(b^{p_1} + 1) = \nu_{p_1}(b + 1) + 1 \geq 2. \]Thus, $n_1^2 \mid b^{n_1} + 1$. Next, assume $n_i = p_1p_2\ldots p_i$ satisfies the condition that $n_i^2 \mid b^{n_i} + 1$. Then, let $p_{i+1}$ be a primitive prime divisor of $b^n + 1$. Its existence is guaranteed by Zsigmondy's theorem. We claim that $p_{i+1} \neq 2$. If $b$ is even, then that is obvious. Otherwise, $2 \mid b+1$, so $2$ would not be a primitive divisor. Thus, $p_{i+1}$ is an odd prime distinct from any of $p_1,p_2,\ldots,p_i$. We then claim that if $n_{i+1} = p_1p_2\ldots p_{i+1}$, then $n_{i+1}$ satisfies the condition from the problem statement. By our lemma, we know that $n_i^2 = (p_1p_2\ldots p_i)^2 \mid b^{n_i} + 1 \mid b^{n_{i+1}} + 1$. It remains to check $p_{i+1}^2 \mid b^{n_{i+1}} + 1$. Again, we use lifting the exponent: \[ \nu_{p_{i+1}}(b^{n_{i+1}} + 1) = \nu_{p_{i+1}}(b^{n_i} + 1) + \nu_{p_{i+1}}(p_{i+1}) = \nu_{p_{i+1}}(b^{n_i} + 1) + 1 \geq 2. \] Thus, by induction, every $n$ in this infinite sequence works. Finally, we prove that if $b+1$ is a power of $2$, there are finitely many solutions to $n^2 \mid b^n + 1$. Suppose $n > 1$ satisfies $n^2 \mid b^n + 1$. If $n$ were even, then $b^n + 1$ would be either $1$ or $2$ mod $4$, but it also must be $0$ mod $4$ in order to be divisible by $n^2$. Hence, $n$ must be odd. Next, let $p$ be the least prime factor of $n$. We have \[ b^n \equiv -1 \implies b^{2n} \equiv 1 \pmod{p}, \]so the order of $b^2$ must divide $\gcd(p-1,n)$. Since $p$ is the least prime factor of $n$, this GCD must equal $1$; otherwise, $\gcd(p-1,n)$ would have a prime factor less than $p$ which is also a factor of $n$, contradicting $p$'s minimality. Thus, $b^2 \equiv 1 \pmod{p}$, or in other words, $p \mid (b-1)(b+1)$. We know $p$ cannot divide $b+1$ since $b+1$ is a power of $2$. Thus, $p$ must divide $b-1$, and $b \equiv 1 \pmod{p}$. However, this means $b^n \equiv 1 \pmod{p}$, so $p$ must be $2$, which is impossible since $n$ is odd! This concludes the proof.