IMO 90/3 and IMO 00/5 cross-up

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#1 h Jun 26, 2018, 4:30 PM • 21 Y

Y by Amir Hossein, G81928128, Euler_88, TwilightZone, ProblemSolver2048, v4913, HamstPan38825, russellk, sotpidot, csong, FaThEr-SqUiRrEl, centslordm, megarnie, jhu08, microsoft_office_word, Mogmog8, Adventure10, Mango247, sabkx, NO_SQUARES, Yiyj1

For which positive integers $b > 2$ do there exist infinitely many positive integers $n$ such that $n^2$ divides $b^n+1$ ?

Evan Chen and Ankan Bhattacharya

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#2 h Jun 26, 2018, 4:37 PM • 21 Y

Y by Amir Hossein, Benq, me9hanics, hyx, mijail, EulersTurban, OlympusHero, TwilightZone, v4913, HamstPan38825, russellk, csong, centslordm, jhu08, math31415926535, megarnie, microsoft_office_word, Adventure10, Mango247, sabkx, Yiyj1

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#3 h Jun 26, 2018, 6:21 PM • 6 Y

Y by Amir Hossein, csong, centslordm, jhu08, Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by Generic_Username, Jun 26, 2018, 6:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenplusten

1000 posts

tenplusten

#4 h Jun 26, 2018, 6:49 PM • 2 Y

Y by centslordm, Adventure10

WRONG...

This post has been edited 1 time. Last edited by tenplusten, Jun 26, 2018, 7:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Th3Numb3rThr33

1247 posts

Th3Numb3rThr33

#5 h Jun 26, 2018, 6:54 PM • 3 Y

Y by centslordm, Adventure10, Mango247

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

This post has been edited 1 time. Last edited by Th3Numb3rThr33, Jun 26, 2018, 6:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenplusten

1000 posts

tenplusten

#6 h Jun 26, 2018, 6:57 PM • 3 Y

Y by centslordm, Adventure10, Mango247

No I take any prime divisor $p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwerty137

3575 posts

qwerty137

#7 h Jun 26, 2018, 6:58 PM • 3 Y

Y by centslordm, Adventure10, Mango247

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$ )

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#8 h Sep 6, 2018, 5:29 AM • 5 Y

Y by csong, centslordm, rightways, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ririri

24 posts

ririri

#9 h Feb 27, 2019, 4:00 PM • 17 Y

Y by AlastorMoody, v_Enhance, rmtf1111, 62861, tenplusten, tapir1729, RMO-prep, Aryan-23, aops29, mira74, Imayormaynotknowcalculus, centslordm, megarnie, rayfish, Adventure10, sabkx, Funcshun840

This was already posted in the forums.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#10 h Feb 27, 2019, 6:45 PM • 10 Y

Y by v4913, csong, centslordm, 554183, megarnie, HamstPan38825, Adventure10, Mango247, sabkx, Funcshun840

ririri wrote:

This was already posted in the forums.

Wow. That's embarrassing (in more than one way).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sholly

24 posts

sholly

#11 h Mar 7, 2019, 4:41 PM • 5 Y

Y by danepale, csong, centslordm, Adventure10, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_pi_rate

1218 posts

math_pi_rate

#12 h Mar 8, 2019, 4:41 PM • 17 Y

Y by pavel kozlov, yayups, Idio-logy, AlastorMoody, Pluto1708, Doxuantrong, Feng_230, alinazarboland, IAmTheHazard, centslordm, AforApple, megarnie, CyclicISLscelesTrapezoid, Haaaa, JG666, Adventure10, sabkx

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.

This post has been edited 2 times. Last edited by math_pi_rate, Mar 29, 2019, 12:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

khina

994 posts

khina

#13 h Dec 27, 2019, 6:17 PM • 2 Y

Y by centslordm, Adventure10

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheUltimate123

1740 posts

TheUltimate123

#14 h Jan 22, 2020, 1:53 AM • 2 Y

Y by centslordm, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aops29

452 posts

aops29

#15 h Feb 13, 2020, 5:54 PM • 3 Y

Y by centslordm, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1745 posts

OronSH

#49 h Dec 12, 2023, 2:28 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1327 posts

dolphinday

#50 h Dec 25, 2023, 5:17 AM

Y by

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.

This post has been edited 1 time. Last edited by dolphinday, Dec 25, 2023, 5:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

682 posts

Shreyasharma

#51 h Dec 28, 2023, 5:12 PM

Y by

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.

This post has been edited 1 time. Last edited by Shreyasharma, Dec 28, 2023, 5:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlanLG

241 posts

AlanLG

#52 h Feb 6, 2024, 12:46 AM

Y by

$\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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#53 h Feb 12, 2024, 8:32 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

796 posts

shendrew7

#54 h Mar 1, 2024, 8:54 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

280 posts

peppapig_

#55 h Mar 14, 2024, 3:42 PM

Y by

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.

This post has been edited 1 time. Last edited by peppapig_, Mar 14, 2024, 6:09 PM
Reason: Typo fix, b^n+1, not \nu_2(b^n+1)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#56 h Mar 15, 2024, 12:29 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

straight

415 posts

straight

#57 h Jul 3, 2024, 10:59 PM

Y by

Truly one of the NT problems of all time

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BestAOPS

707 posts

BestAOPS

#58 h Jul 9, 2024, 2:54 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#59 h Feb 18, 2025, 3:03 AM

Y by

Fix the value of $b$ . We say that $n$ is good if $n^2\mid b^n+1$ and there exists some odd prime $q$ such that $q\nmid n^2$ and $q\mid b^n+1$ .

We claim that if $n$ is good, then so is $np$ for some odd prime $p$ with $p\nmid n$ . Indeed, for such $n$ , take $p$ satisfying $p\nmid n^2$ and $p\mid b^n+1$ . Then $\nu_p(b^{np}+1)=\nu_p((b^n)^p-(-1)^p)=\nu_p(b^n+1)+\nu_p(p)\ge2$ from exponent lifting. Additionally, we have $n^2\mid b^{np}+1$ as $p$ is odd. This implies that $n^2p^2\mid b^{np}+1$ .

Additionally, since $b>2$ , by Zsigmondy there exists some odd prime $q$ for which $q\nmid b^n+1$ and $q\mid b^{np}+1$ . In particular, $q\nmid n^2p^2$ but $q\mid b^{np}+1$ . This proves our claim. In particular, it follows that if there exists some integer that is good, then there exists infinitely many integers that are good.

Let $k=\frac{b+1}{2^{\nu_2(b+1)}}$ . We claim the if $k>1$ , so that $b+1$ is not a power of two, then $k$ is good. If $p\mid k$ , by exponent lifting we have $\nu_p(b^k+1)=\nu_p(b^k-(-1)^k)=\nu_p(b+1)+\nu_p(k)=2\nu_p(k)$ , so $k^2\mid b^k+1$ . Additionally, by Zsigmondy there exists some prime $q$ for which $q\nmid b+1$ and $q\mid b^k+1$ . Since $k\mid b+1$ , we have $q\nmid k^2$ . Thus $k$ is good.

As a result, if $b+1$ is not a power of $2$ , our above results imply that there exist infinitely many good integers and thus infinitely many positive integers $n$ such that $n^2\mid b^n+1$ .

Finally, if $b+1=2^m$ for some $m$ , we claim that $n^2\nmid b^n+1$ for all $n$ . Indeed, if otherwise, let $p$ be the minimal odd divisor of $n$ . Then $b^n\equiv-1\pmod p$ and $b^{p-1}\equiv1\pmod p$ , so that $b^2\equiv b^{\gcd(2n,p-1)}\equiv1\pmod p$ by minimality. Thus $p\mid b^2-1=(b-1)(b+1)$ , and since $p$ is odd we have $p\mid b-1$ . But then $b^n\equiv1\pmod p$ , a contradiction.

Our solution set for $b$ is therefore $\boxed{\{b\mid b\in\mathbb{N},b>2,\log_2(b+1)\notin\mathbb{Z}\}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

634 posts

cursed_tangent1434

#60 h Apr 9, 2025, 4:02 PM

Y by

We claim that the answer is all positive integers $b>2$ excluding those of the form $2^r-1$ for some positive integer $r>1$ . We shall first show that such $b$ indeed do not work.

First note that if $n$ is even $2 \mid b^n+1$ which requires $b$ to be odd. However then,
$b^n+1 \equiv 1+1 \equiv 2 \pmod{4}$ since $n$ is even which contradicts the fact that $4 \mid n^2 \mid b^n+1$ . Thus, for all $b$ there exists no even $n$ such that $n^2 \mid b^n+1$ .

With this observation in hand, it is clear that $b^n+1$ must have some odd prime factors. We look at the smallest prime factor $q \mid n$ . Note that $b^{2n}\equiv1 \pmod{q}$ but $b^n \equiv -1 \pmod{q}$ . This means that $\text{ord}_q(2) \mid 2n$ . Thus, if $\text{ord}_q(2)$ has some odd prime factor, it is a violation of the minimality of $q$ implying that $\text{ord}_q(2)$ is a perfect power of two. However, $\nu_2(2n)=1$ since $n$ must be odd so $\text{ord}_q(2) \mid 2$ . However, this cannot be $1$ as $b^n\equiv -1 \not \equiv 1 \pmod{q}$ . This means that $\text{ord}_q(2)=2$ and thus, $b+1 \equiv 0 \pmod{q}$ .

However, if $b=2^r-1$ for some positive integer $r$ this implies that there exists some odd prime $q$ such that $q \mid 2^r$ which is a clear contradiction. Thus, all $b$ of the prescribed form in deed do not satisfy the desired conditions.

To see why all other $b$ work, we employ induction. Consider an odd prime $p_1 \mid b+1$ . Note that,
$\nu_{p_1}(b^{p_1}+1) = \nu_{p_1}(b+1)+\nu_{p_1}(p_1) \ge 2$ and thus, $p_1^2 \mid b^{p_1}+1$ . Now, assume that for some $r \ge 1$ there exists a product of distinct odd primes $x_{r-1}=p_1p_2\dots p_{r-1}$ and $x_r=p_1p_2\dots p_r$ such that $x_{r-1}^2 \mid b^{x_{r-1}}+1$ and $p_{r} \mid b^{x_{r-1}}+1$ ( $p_r\not \in \{p_1,p_2,\dots , p_{r-1}\}$ ). Note that,
$(p_1p_2\dots p_{r-1})^2 \mid 2^{x_{r-1}}+1 \mid 2^{x_r}+1$ Also, by Lifting the Exponent Lemma,
$\nu_{p_r}(2^{x_r}+1)= \nu_{p_r}(2^{x_{r-1}}+1)+\nu_{p_r}(p_r) \ge 2$ Thus, $p_r^2 \mid 2^{x_r}+1$ and we conclude that $x_r^2 \mid 2^{x_r}+1$ . Further, by Zsigmondy's Theorem there exists some odd prime factor $p_{r+1}$ such that $p_{r+1} \mid 2^{x_r}+1$ but $p_{r+1} \nmid 2^{x_{r-1}}+1$ (and hence $p_{r+1} \not \in \{p_1,p_2,\dots , p_r\}$ ). We then let $x_{r+1}=p_1p_2\dots p_rp_{r+1}$ which completes the induction and solves the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Adywastaken

46 posts

Adywastaken

#61 h Apr 25, 2025, 3:02 PM

Y by

Claim: $\exists$ infinitely many $n$ iff $b+1\neq 2^k$

Proof: FTSOC assume otherwise.
Let $p_1$ be a prime such that $p_1\mid b+1$
$v_{p_1}(b^{p_1}+1)=1+v_{p_1}(b+1)$
$\implies (p_1)^2\mid b^{p_1}+1$
By Zsig, $\exists p_2\neq p_1$ such that $p_2\mid b^{p-1}+1$
Now, let's say $(p_1p_2\dots p_{n-1})^2p_n\mid b^{p_1p_2\dots p_{n-1}}+1$
By LTE again, $(p_1p_2\dots p_n)^2\mid b^{p_1p_2\dots p_n}+1$
By Zsig, $\exists p_{n+1}$ such that $p_{n+1}\mid b^{p_1p_2\dots p_n}+1$
So, $(p_1p_2\dots p_n)^2p_{n+1}\mid b^{p_1p_2\dots p_n}+1$
Hence, there are infinitely many solutions.

Now, let $b=2^k-1$
Let $p$ be the smallest prime dividing $n$ .
$p\mid b^n+1$ , $p\mid 2^{p-1}+1$ , so $p\mid (b+1)(b-1)$ .
$\implies p\mid b+1$ , $p=2$
For $n\geq 2$ , $4\mid b^n+1\equiv 2\pmod 4$ , since $n$ is even and $b$ is odd. $\Rightarrow\!\Leftarrow$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

650 posts

Ilikeminecraft

#62 h Apr 26, 2025, 12:05 AM

Y by

I claim the answer is all integers that can't be expressed as $2^n - 1.$

I will start by proving that any integer of that form can't work.

I claim that $n$ must be odd. Take modulo 4, and thus $b^n + 1 \equiv 2 \pmod 4 \implies \nu_2(b^n + 1) = 1 < 2,$ which is a contradiction. For $n \neq 1,$ let $p$ be the smallest prime dividing $n.$ I claim that $p \mid b + 1.$

By using the fact that $b^{2n} \equiv 1\pmod {p},$ and $b^{p - 1} \equiv 1 \pmod p,$ we have that $\operatorname{ord}_(b) \mid (2n, p - 1) = 2.$ Thus, $p\mid b^2 - 1.$ However, if $p\mid b - 1,$ we have that $b^n + 1 \equiv 1 + 1 \equiv 2 \pmod p\implies p\mid 2,$ which is clearly a contradiction. Thus, $p\mid b + 1.$

If $b + 1 = 2^k$ for some $k,$ then we clearly have no solution because then $p = 2,$ which is a contradiction.

Now, I prove that any other integer can work. I will do this with induction. Let $p_i, n_i$ be an infinite sequence. Let $n_k = \prod\limits_{i = 0}^k p_i$ . Let $p_i = 1,$ and then for all $i\geq 1,$ let $p_i$ be distinct primes such that $p_{i} \mid b^{n_{i - 1}} + 1.$ We know $p_i$ exists because of Zsigmondy's, and that $p_i$ are all odd. I claim that each term in the sequence $n_k$ is a valid construction. We will prove this with induction.

$k = 0$ is obviously true. $k = 1$ has that $n_1 = p_1 \mid b + 1.$ Thus, $\nu_{p_1} (b^{p_1} + 1) = \nu_{p_1}(b + 1) + 1 \geq 2.$ Thus, this is valid.

Now assume that $k = l$ has that is a valid construction. Hence, $n_l^2 \mid b^{n_l} + 1 \mid b^{n_lp_{l + 1}} + 1 = b^{n_{l + 1}} + 1.$ We also have that $p_{l + 1} \mid b^{n_{l}} + 1,$ and hence $\nu_{p_{l + 1}} (b^{n_{l + 1}} + 1) = \nu_{p_{l + 1}}({b^{n_{l}}}^{p_{l + 1}} + 1)\geq2.$ Thus, we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GingerMan

5 posts

GingerMan

#63 h May 4, 2025, 1:18 AM

Y by

Answer is all integers $b>2$ except for those that are $1$ less than a power of $2$ .
First, we show $b=2^k-1$ fails. Let $p$ be the minimal prime divisor of $n$ ; the order of $b$ mod $p$ divides $\gcd(2n, p-1) = 2$ and thus $p \mid b+1 \implies p=2$ . Now $4 \mid b^n+1$ and since $b \equiv -1 \pmod 4$ , we have $n$ odd which is a contradiction.
We now prove all other $b$ work. Let $p_1$ be an odd prime divisor of $b+1$ . Define $p_{k+1}$ as an odd prime satisfying $p_{k+1} \mid b^{p_k}+1$ and $p_{k+1} \notin \{p_1,\dots,p_k\}$ (this exists by Zsigmondy). Fix any positive integer $m$ and define $n=p_1p_2\dotsb p_m$ .
By LTE,
$\begin{align*} \nu_{p_k}(b^n+1) &= \nu_{p_k}(b^{p_{k-1}}+1) + \nu_{p_k}(n/p_{k-1})\\ &= \underbrace{\nu_{p_k}(b^{p_{k-1}}+1)}_{\ge 1} + \underbrace{\nu_{p_k}(n)}_{=1} \geq 2\nu_{p_k}(n) \end{align*}$ for $k=2,\dots,m$ ; we similarly show
$\nu_{p_1}(b^n+1) = \nu_{p_1}(b+1) + \nu_{p_1}(n) \geq 2\nu_{p_1}(n).$ Hence $n^2 \mid b^n+1$ , and by setting $m=1,2,\dots$ , we get infinitely many integers.
The case $b=2$ fails by IMO 1990/3.

Z K Y