2^n-1 has n divisors

The post below has been deleted. Click to close.

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

megarnie

5603 posts

megarnie

#1 h Oct 30, 2021, 11:00 PM • 9 Y

Y by HWenslawski, OlympusHero, centslordm, Justpassingby, Epsilon-, TheHawk, Ciel_vert, GoodMorning, OronSH

Find all integers $n\ge1$ such that $2^n-1$ has exactly $n$ positive integer divisors.

Proposed by Ankan Bhattacharya

This post has been edited 2 times. Last edited by megarnie, Nov 6, 2021, 7:37 PM
Reason: Added the proposer

Z K Y

The post below has been deleted. Click to close.

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

nukelauncher

354 posts

nukelauncher

#6 h Oct 30, 2021, 11:17 PM • 10 Y

Y by centslordm, megarnie, CT17, math31415926535, RedFlame2112, ILOVEMYFAMILY, StarLex1, rayfish, mijail, Asynchrone

Solution

This post has been edited 2 times. Last edited by nukelauncher, Oct 30, 2021, 11:40 PM

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7346 posts

DottedCaculator

#7 h Oct 30, 2021, 11:22 PM • 2 Y

Y by centslordm, megarnie

solution attached

Attachments:

2021 USEMO Problem 2.pdf (299kb)

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

#8 h Oct 30, 2021, 11:22 PM • 3 Y

Y by centslordm, megarnie, ilikemath40

The answers are 1, 2, 4, 6, 8, 16, 32. It is easy to check by hand that these work via Fermat primes. Moreover, we may check that $d(2^{12}-1)=24$ and $d(2^{64}-1)=128$ .

Now we claim for all other $n$ that $\nu_2(d(2^n-1))>\nu_2(n).$
To this end, we induct on $\nu_2(n)$ , with base cases $n=12$ , $n=64$ , and $n\ne1$ odd. The first two have been checked above. For $n\ne1$ odd, $d(2^n-1)$ is even since $2^n-1\equiv3\pmod4$ is not a square.

For the inductive step $n\to2n$ , observe that $2^{2n}-1=(2^n-1)(2^n+1)$ , and since the two terms are coprime, we have $d(2^{2n}-1)=d(2^n-1)\cdot d(2^n+1).$ But $\nu_2(d(2^n-1))>\nu_2(n)$ by inductive hypothesis, and $d(2^n+1)$ is even since $2^n+1$ is not a square for $n\ne3$ by Mih\u ailescu theorem. Hence $\nu_2(d(2^{2n}-1))>\nu_2(n)+1=\nu_2(2n).$

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5603 posts

megarnie

#9 h Oct 30, 2021, 11:31 PM

Y by

oh no I wrote a super long proof of why $\gcd(2^m-1,2^{2^i\cdot m}+1)=1$ .

Z K Y

The post below has been deleted. Click to close.

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

MarkBcc168

1595 posts

MarkBcc168

#10 h Oct 31, 2021, 12:09 AM • 4 Y

Y by centslordm, megarnie, MatBoy-123, RaceCar21

Nice problem! Here is a very different solution.

The answers are $n=1,2,4,6,8,16,32$ . These can be easily checked to be all work. To show that there are no other solutions, we first recall the functions $\omega$ and $\Omega$ defined by
$\begin{align*} \omega(p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}) &= k \\ \Omega(p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}) &= e_1+e_2+\dots +e_k, \end{align*}$ where $p_1,\dots,p_k$ are primes. The main idea of the solution is the following lemma.

Lemma: For any positive integer $n$ , $\Omega(\tau(n)) \geq \omega(n)$ .

Proof: Obvious after writing $n$ as the factorization form. $\blacksquare$

In light of this lemma, we bound $\omega(2^n-1)$ . By Zsigmondy's theorem, for each divisor $d\ne 1,6$ , there exists a prime $p_d$ such that $\mathrm{ord}_{p_d}(2) = d$ . All the $p_d$ 's are distinct, so
$\tau(n) - 2 \leq \omega(2^n-1) \leq \Omega(\tau(2^n-1)) = \Omega(n).$ This inequality alone is enough to deduce that:

Claim: $n$ must be a prime power or the product of two primes.

Proof: Suppose that $n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ where $k\geq 2$ . Then,
$\begin{align*} \tau(n) &= (e_1+1)(e_2+1)\dots (e_k+1) \\ &\geq e_1e_2\dots e_k + (e_1+e_2+\dots + e_k) + 1 \\ &\geq \Omega(n)+2. \end{align*}$ The equality occurs iff $e_1e_2\dots e_k=1$ and $k=2$ , implying the result. $\blacksquare$

The rest is just grinding. First, note that, except $n=1$ , $n$ must be even because otherwise, $2^n-1$ must be a perfect square, which is impossible because $2^n-1\equiv 3\pmod 4$ . Thus, we have two cases.

If $n=2^k$ for some $k$ , then note the factorization
$2^{2^k}-1 = (2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)\dots (2^{2^{k-1}}+1),$ which implies that it has at least $k$ divisors. Furthermore, $2^{2^5}+1$ is composite, forcing $k\leq 5$ or $n\in\{1,2,4,8,16,32\}$ .
Otherwise, $n$ must be $2p$ for some prime $p$ . If $p\ne 3$ , then we can go back and stregthen the bound above to $\omega(2^n-1)\geq 3$ , which implies that $\Omega(n)\geq 3$ , contradiction.

Thus, all answers are indeed $1,2,4,6,8,16,32$ .

This post has been edited 1 time. Last edited by MarkBcc168, Sep 4, 2023, 1:44 PM

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5603 posts

megarnie

#11 h Oct 31, 2021, 12:46 AM • 3 Y

Y by centslordm, bjump, peace09

I literally learned about Fermat Primes yesterday.

We claim the answer is $\boxed{n=1,2,4,6,8,16,32}$ . Proof that these work

Let $d(m)$ denote the number of positive integer divisors of $m$ .

Claim: If $n$ is odd, then $n=1$ .
Note that $d(2^1-1)=1$ , so $n=1$ works. If $n>1$ , then $2^n-1\equiv3\pmod 4$ Since $3$ is not a quadratic residue $\pmod4$ , $2^n-1$ is not a perfect square, and thus doesn't have an odd number of divisors.

Henceforth assume that $n$ is even.

We can write $2^n-1$ as $(2^m-1)(2^m+1)(2^{2m}+1)(2^{4m}+1)\cdots(2^\frac{n}{2}+1),$ where $m$ is an odd positive integer and $m=\frac{n}{2^k}$ .

Claim: All terms in the above product are relatively prime.
Proof (on the test I took 4.5 pages to prove this claim

) (I also write big): I will first show that the first term is relatively prime to all other terms. We must show that $\gcd(2^m-1,2^{m\cdot 2^i}+1)=1$ for all integers $0<i<k$ . Note that $(2^m-1)(2^m+1)(2^{2m}+1)\cdots (2^{m\cdot 2^{i-1}}+1)=2^{m\cdot 2^i}-1$ , so by the Euclidean Algorithm, $\gcd(2^m-1,2^{m\cdot 2^i}+1)=\gcd(2^m-1, 2)=1$
Now, to prove our original claim, it suffices to show that all other terms are pairwise relatively prime. We must show that $\gcd(2^{m\cdot2^i}+1,2^{m\cdot 2^j}+1)=1$ ,

for all integers $0<i<j<k$ .

Note that $(2^{m\cdot2^i}+1)(2^{m\cdot2^i}-1)(2^{m\cdot 2^{i+1}}+1)(2^{m\cdot 2^{i+2}}+1)\cdots (2^{m\cdot2^{j-1}}+1)=2^{m\cdot 2^j}-1$ , so by the Euclidean Algorithm, $\gcd(2^{m\cdot2^i}+1,2^{m\cdot 2^j}+1)=\gcd(2^{m\cdot2^i}+1,2)=1,$ as desired.

Since $d(m)d(n)=d(mn)$ whenever $m$ and $n$ are relatively prime, we have $d(2^n-1)=d(2^m-1)d(2^{m}+1)d(2^{2m}+1)\cdots d(2^{\frac{n}{4}}+1)d(2^{\frac{n}{2}}+1)=n$ .

Since there are $m+1$ terms in the above product, and $\nu_2(n)=m$ , one of the terms has an odd number of divisors, and must be a perfect square.

Case 1: $2^m-1$ is a perfect square.
So $m=1$ . Thus, $n=2^k$ .
Claim: The rest of the terms are not perfect squares.
Proof: Suppose $2^i+1=a^2$ . Then $(a-1)(a+1)=2^i$ , so $a-1$ and $a+1$ are both powers of $2$ , which implies $a=3$ and so, $i=3$ . $3$ is not a power of $2$ , so we are done.

Now, if one of the terms has the number of divisors equal to a multiple of $4$ , then $d(2^n-1)$ has at least one more power of $2$ than $n$ .

We have $2^{32}+1=641\cdot6700417$ , both of which are primes, so $d(2^{32}+1)=4$ . Thus, $k<6$ and all integers $0<k<6$ work.

Case 2: $2^m-1$ is not a perfect square.
One of the other terms must be a perfect square, so $m=3$ . Thus, $n=3\cdot 2^k$ .

Now, if one of the terms has the number of divisors equal to a multiple of $4$ , then $d(2^n-1)$ has at least one more power of $2$ than $n$ .

Note that $d(2^{3\cdot 2^1}+1)=4$ , so $k<2$ . $k=1$ obviously works and $k=0$ doesn't.

Having exhausted all cases, we are done.

This post has been edited 4 times. Last edited by megarnie, Dec 30, 2021, 3:14 AM

Z K Y

The post below has been deleted. Click to close.

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

mathleticguyyy

3217 posts

mathleticguyyy

#12 h Oct 31, 2021, 1:22 AM • 2 Y

Y by centslordm, megarnie

probably closer to (albeit still difficult for) a JMO 2 than USAMO/IMO 2, but still a cool problem nonetheless.

The answers are $1,2,4,6,8,16,32$ . It's fairly easy to check that they do work.

Let $\nu_2(n)=m$ and $n=k\cdot 2^m$ for some odd $k$ . We can factor $2^{n}-1=(2^{2^{m-1}k}+1)(2^{2^{m-2}k}+1)\ldots (2^{k}+1)(2^{k}-1)$ , where there are notably $m+1$ terms on the RHS.

By Catalan conjecture, $2^k+1$ is a perfect square only when $k=3$ , and $2^{k}-1$ is a perfect square only when $k=1$ . Also, it's easy by Euclidean Algorithm to see that any two terms on the RHS are relatively prime; this means that when $k\ge 5$ , the # of factors of RHS is a product of $m+1$ even integers by multiplicativity, but $n$ is not divisible by $2^{m+1}$ . We can therefore concentrate on $k=1$ and $k=3$ , where the answer can be derived by simply recognizing that $2^{2^5}+1$ and $2^{3\cdot 2}+1$ are not primes.

This post has been edited 7 times. Last edited by mathleticguyyy, Oct 31, 2021, 3:51 PM

Z K Y

The post below has been deleted. Click to close.

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

pad

1671 posts

pad

#13 h Oct 31, 2021, 3:41 AM • 3 Y

Y by megarnie, centslordm, math31415926535

Write $n=2^\ell a$ , where $a$ is odd. Then
$2^n-1 = (2^a-1)(2^a+1)(2^{2a}+1)\cdots (2^{2^{\ell-1}a}+1).$ We claim that all the above $\ell+1$ terms are pairwise coprime. All are odd. If $p\mid 2^a-1$ is a prime, then $p\mid 2^{2^ka}-1$ for all $k\ge 0$ , so in particular $p\nmid 2^{2^ka}+1$ since $p>2$ . Similarly, if $p\mid 2^{2^ka}+1$ , then $p\mid 2^{2^{k+1}a}-1 \mid 2^{2^{k'}a}-1$ for all $k'>k$ , so $p\nmid 2^{2^{k'}a}+1$ for all $k'>k$ .

Now,
$2^\ell a = n = \tau(2^n-1) = \tau(2^a-1)\tau(2^a+1)\tau(2^{2a}+1)\cdots \tau(2^{2^{\ell-1}a}+1).$ It is well-known (and easy to prove) that $2^x-1$ square if and only if $x=1$ , and $2^x+1$ square if and only if $x=3$ . So if $a\ge 5$ , then all the terms above are even, so $\nu_2(RHS) \ge \ell+1 > \ell = \nu_2(LHS)$ , contradiction. So $a=1$ or $a=3$ .

If $a=3$ , then
$\tau(2^a-1) = 2, \tau(2^a+1)=3, \tau(2^{2a}+1) = 4 = 2^2,$ and of course $\tau(2^{2^ka}+1) \ge 2$ for all $k\ge 0$ , so the product is at least $3\cdot 2^{\ell+1}>2^\ell a$ , contradiction, unless $\ell\le 1$ , in which case $n=6$ .

If $a=1$ , it can be confirmed that $\tau(2^{k}+1)=2$ for all $k=1,2,3,4$ , but $\tau(2^{32}+1) > 2$ . A similar argument gives a size contradiction for $k \ge 6$ . So $1,2,4,8,16,32$ are possibilities for $n$ .

It can be checked manually that $1,2,4,8,16,32,6$ work, so 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.

rama1728

800 posts

rama1728

#14 h Oct 31, 2021, 5:59 AM • 3 Y

Y by megarnie, centslordm, cursed_tangent1434

megarnie wrote:

Find all integers $n\ge1$ such that $2^n-1$ has exactly $n$ positive integer divisors.

I'm loving this one. This is one of my favorite problems. The solution I am about to present will contain motivation too.

First of all by Fermat primes, we can check that $n=1,2,4,6,8,16,32$ work.

Now we are starting the problem. We naturally start with plugging some random values of $n$ .
$\begin{tabular}{ c c c } 1 & 1 & 1 \\ 2 & 3 & 2 \\ 3 & 7 & 1 \\ 4 & 15 & 4 \\ 5 & 31 & 2 \\ 6 & 63 & 6 \\ 7 & 127 & 2 \\ 8 & 255 & 8 \\ 9 & 511 & 4 \\ 10 & 1023 & 8 \\ \end{tabular}$ We have plugged the first ten values, where the first column tells the value of $n$ , second for $2^n-1$ and third for $d(2^n-1)$ . Now, we check for patterns in this. Notice that many of the values in the last column (all except one, that is for $6$ ) are giving powers of $2$ ! So this motivates us to consider the power of $2$ dividing $d(2^n-1)$ , and as a consequence, we try to find some relation between $\nu_2\left(d(2^n-1)\right)$ and $\nu_2(n)$ . If we check in this table, we see that the former is at least the latter! And this really relates to our problem because if we show that the former is at least the latter always, then we can try to show that after a point, the former is strictly greater than the latter, and this will imply that after that point, there is no value of $n$ .

Highly motivated by this, we try to show the inequality: $\nu_2\left(d(2^n-1)\right)\geq\nu_2(n)$ This surely pings induction, because there is no possible way we could prove this (since it looks kind of abstract). We will induct over $\nu_2(n)$ . If $\nu_2(n)=0$ (the base case), the proposed inequality is true, because every positive integer has at least one divisor. Now assume that this holds for $\nu_2(n)=k$ , that is $n=2^k\cdot e$ , where $e$ can be any odd number. We have to show that the statement holds true for $n=2^{k+1}\cdot e$ . Notice that $d\left(2^{2^{k+1}\cdot e}-1\right)=d\left(\left(2^{2^k\cdot e}-1\right)\left(2^{2^k\cdot e}+1\right)\right)=d\left(2^{2^k\cdot e}-1\right)\cdot d\left(2^{2^k\cdot e}+1\right)$ since both $2^{2^k\cdot e}+1$ and $2^{2^k\cdot e}-1$ are co-prime. Therefore, $\nu_2\left(d\left(2^{2^{k+1}\cdot e}-1\right)\right)=\nu_2\left(d\left(2^{2^k\cdot e}-1\right)\right)+\nu_2\left(d\left(2^{2^k\cdot e}+1\right)\right)\geq k+1$ by our inductive assumption and the fact that $2^{2^k\cdot e}+1$ is greater than $1$ . This completes the inductive step.

Now, we would like to show that after a point, the inequality becomes strict. We know that $2^{2^5}-1$ has exactly $32$ divisors. Now, let us assume that $\nu_2(n)>5$ . Then, since $2^{2^5}+1$ is composite, we can say that $\nu_2\left(d(2^{2^6\cdot e}-1)\right)>\nu_2(n)$ because the $2^{2^5\cdot e}+1$ adds more than 1 factor (The solutions above worked because $2^{2^k}+1$ is prime for $1\leq k\leq 4$ and $2^1-1$ has $1$ prime factor). So if $\nu_2(n)>=6$ , their highest powers of $2$ can never be equal, because we already got strict inequality for $\nu_2(n)=6$ and if you increase $\nu_2(n)$ by $1$ , the quantity $\nu_2\left(d(2^n-1)\right)$ increases by at least $1$ and so when $\nu_2(n)$ is at least $6$ , the proposed statement fails. So $\nu_2(n)\leq5$ and a simple case check reveals that the solutions presented above are the only ones that work.

This post has been edited 2 times. Last edited by rama1728, Oct 31, 2021, 6:05 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

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

Sprites

478 posts

Sprites

#16 h Oct 31, 2021, 3:07 PM • 2 Y

Y by centslordm, megarnie

To factorise up,denote $n=2^km$ to get $2^{2^km}-1=\left[2^m-1 \right] \cdot \prod_{j=0}^ {k-1} \left[2^{2^jm}-1 \right]$
Claim #1:- The gcd of all the fore-mentioned terms is $1$

Proof:- The first term i.e $2^m-1$ clearly has a gcd of $1$ with $2^m+1$ ;moreover $\gcd(2^m-1,2^{2^jm}+1)=\gcd(2^m-1,2)=1$ by Euclidean Algorithm.
For all other terms we have $\gcd(2^{2^jm}+1,2^{2^im}+1)=1$ again by the Euclidean Algorithm.

Claim #2:- For all $n$ we must have $\nu_2\left(\tau(2^n-1)\right)\geq\nu_2(n)$
Proof:- Induction works;i.e induction over $\nu_2(n)$ .Suppose that(since the base case works) $\nu_2(n)=k \;\;\; n=2^ek$ then $\tau\left(2^{2^{k+1}\cdot e}-1\right)=\tau\left(\left(2^{2^k\cdot e}-1\right)\left(2^{2^k\cdot e}+1\right)\right)=\tau\left(2^{2^k\cdot e}-1\right)\cdot \tau\left(2^{2^k\cdot e}+1\right)$ since both $2^{2^k\cdot e}+1$ and $2^{2^k\cdot e}-1$ are co-prime. Therefore, $\nu_2\left(\tau\left(2^{2^{k+1}\cdot e}-1\right)\right)=\nu_2\left(\tau \left(2^{2^k\cdot e}-1\right)\right)+\nu_2\left(\tau \left(2^{2^k\cdot e}+1\right)\right)\geq k+1$ where the last step follows from the inductive hypothesis and Mihalescu's theorem;(since $k>3$ ; $k=3$ can be verified seperately.)

Now by the multiplicative-ness of the $\tau$ function we get $\tau \left(2^{2^km}-1 \right)=\tau \left[2^m-1 \right] \cdot \tau \left(\prod_{j=0}^ {k-1} \left[2^{2^jm}-1 \right]\right)$ If all of the terms on the RHS,were not perfect squares then their $\nu_2>\nu_2(n)$ ,which is a contradiction so again by Mihalescu's, $\boxed{m\in \{1,3 \}}$
$\;\;\;\;\;\;\;\;\; \bullet$ If $m=1$ then $n=2^{2^k}$ where we get the solutions $\boxed{n=1,2,4,8,16,32}$
$\;\;\;\;\;\;\;\;\; \bullet$ If $m=3$ then we get the solution $\boxed{n=6}$
Therefore, $\boxed{n=1,2,4,6,8,16,32}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

ChrisWren

323 posts

ChrisWren

#17 h Oct 31, 2021, 3:38 PM • 2 Y

Y by centslordm, megarnie

Sillied this problem.. I thought $2^{16}+1$ was composite. :blush:

edit: How many points would I get?

This post has been edited 1 time. Last edited by ChrisWren, Oct 31, 2021, 3:39 PM

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5603 posts

megarnie

#18 h Oct 31, 2021, 3:50 PM

Y by

ChrisWren wrote:

Sillied this problem.. I thought $2^{16}+1$ was composite. :blush:

edit: How many points would I get?

Was your answer $\boxed{1,2,4,6,8,16}$ ?

Z K Y

The post below has been deleted. Click to close.

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

ChrisWren

323 posts

ChrisWren

#19 h Oct 31, 2021, 3:53 PM • 1 Y

Y by megarnie

Yes. Every aspect of my solution was the same as the ones here (except for the $2^k$ case, which I messed up on)

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5603 posts

megarnie

#20 h Oct 31, 2021, 4:21 PM

Y by

ChrisWren wrote:

Yes. Every aspect of my solution was the same as the ones here (except for the $2^k$ case, which I messed up on)

Then maybe 6 points? IDK since I'm not a grader.

This post has been edited 1 time. Last edited by megarnie, Oct 31, 2021, 4:22 PM

Z K Y

The post below has been deleted. Click to close.

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

pi_is_3.14

1437 posts

pi_is_3.14

#40 h Mar 3, 2023, 5:58 AM

Y by

Odd n immediately fail (except 1) by mod 4.

Claim: Only $2^n + 1$ square exists when $n = 3$ .

Proof: $2^n + 1 = (2a + 1)^2 = 4a^2 + 4a + 1 \implies 2^n = 4(a)(a + 1)$ but this will have odd factors unless $a = 1$ and $n = 3$ .

For even n, let $n = 2^k \cdot m$ for odd m. Factor $2^{n}- 1= (2^m - 1)(2^m + 1)(2^{2m} + 1)\dots (2^{\frac{n}{2}} + 1)$ . Then, by Euclidean Algorithm, we have that $\gcd(2^m + 1, 2^{2m}+ 1) = \gcd(2^m + 1, 2^m - 1) = 1$ . Therefore, all of the above terms are relatively prime and since divisor function is multiplicative so to find divisors, just multiply # of divisors of each term. Note that for $m$ not equal to 1 or 3, every term can not be a square and # divisors of that term must have factor of 2. However, there are much such terms than factors of 2 in n so fail.

Case 1: $m = 3$
$n = 3 \dots 2^k$ . 6 works, all higher k fail since $2^6 + 1$ does not have 2 factors.

Case 2: $m = 1$
Will work for all $k$ until $2^{2^{k - 1}} + 1$ isn't prime which first happens at k = 6.

So answer is 1, 2, 4, 6, 8, 16, 32 which all work

This post has been edited 2 times. Last edited by pi_is_3.14, Mar 5, 2023, 11:10 PM

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#45 h Mar 3, 2023, 11:55 PM

Y by

The answer is $n=1, 2, 4, 6, 8, 16, 32$ . Suppose $n$ has $m$ distinct prime divisors $p_1, \ldots, p_m$ . Then, define the sequence $a_i=2^{p_i^{\nu_{p_i}(n)}}-1$ for $i=1, 2, \ldots, m$ . The central claim is the following.

Claim: We have
1. For each $1 \le i \le n$ , $a_i$ has exactly $\nu_{p_i}(n)$ distinct prime divisors.
2. The set of distinct prime divisors of $2^n-1$ is the set of distinct prime divisors of $\prod_{i=1}^m a_i$ .

Proof:
We first show that $a_i$ has at least $\nu_{p_i}(n)$ distinct prime divisors. Write $a_i = \bigg(\frac{2^{p_i^1}-1}{2^{p_i^0}-1}\bigg)\cdots\bigg(\frac{2^{p_i^{\nu_{p_i}(n)}-1}}{2^{p_i^{\nu_{p_i}(n)-1}}-1}\bigg).$ Label these quotients $q_1, \ldots, q_{\nu_{p_i}(n)}$ ; by Zsigmondy's theorem, $q_k$ has a prime divisor that does not divide $q_{k-1}$ for all $2 \le k \le \nu_{p_i}(n)$ . This implies that $a_i$ has at least $\nu_{p_i}(n)$ distinct prime divisors.

Next, we show that $\prod_{i=1}^m a_i$ divides $2^n-1$ . To do so, notice that each of the $a_i$ divide $2^n-1$ and that $a_i$ and $a_j$ are relatively prime for distinct $i$ and $j$ .

Finally we use the above two facts to write $\sum_{\text{prime} \ p} \nu_p(d(2^n-1)) \ge \sum_{\text{prime} \ p} \nu_p(d(\prod_{i=1}^m a_i)) = \sum_{\text{prime} \ p} \sum_{i} \nu_p(d(a_i)) = \sum_{i} \sum_{\text{prime} \ p} \nu_p(d(a_i)) \ge \sum_{i} \nu_{p_i}(n) = \sum_{\text{prime} \ p} \nu_p(n).$
However, since $d(2^n-1)=n$ , $\sum_{\text{prime} \ p} \nu_p(d(2^n-1)) = \sum_{\text{prime} \ p} \nu_p(n)$ , so the inequalities in the above statement are tight. The claim follows. $\square$

By Zsigmondy's theorem and the Claim, $m=1$ or $n=6$ .

Case 1: $m=1$
Then, $n=p^e$ for some prime $p$ . However, $p=2$ by modulo 4 reasons. It can be checked that $0 \le e \le 5$ all work. Denote $F_n$ by the $n$ th Fermat number. Notice that $2^{2^{k+1}}-1=(2^{2^k}-1)F_k$ . Since $(F_k, 2^{2^k}-1)=1$ , $d(2^{2^{k+1}}-1)=d(2^{2^k}-1)d(F_k)$ . As such, $F_5$ is not prime, and from here it can be inductively shown that all $e \ge 6$ do not work. Thus, $n=1, 2, 4, 8, 16, 32$ are the solutions for this case.

Case 2: $n=6$
This can be verified to work, so $n=6$ works.

Hence, $n=1, 2, 4, 6, 8, 16, 32$ are the only solutions, which completes the proof. $\blacksquare$

This post has been edited 2 times. Last edited by Leo.Euler, Aug 20, 2023, 12:12 AM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8858 posts

HamstPan38825

#46 h Apr 9, 2023, 7:00 PM

Y by

By looking at mod $4$ , it's clear that $n$ must be even (or $n=1$ ). Now, let $n = 2^k \cdot a$ , so $2^n - 1 = (2^{2^{k-1} \cdot a} + 1)(2^{2^{k-2} \cdot a} + 1) \cdots (2^a + 1)(2^a - 1).$
Claim. One of the terms on the RHS must be a perfect square.

Proof. Assume otherwise. Note that every pair of terms on the RHS are relatively prime. This implies that for each term there exists a $p$ that appears a net odd amount of times in the factorization of $2^n - 1$ . But this implies $\nu_2(n) = \nu_2(\tau(n)) \geq k+1$ , which is a contradiction. $\blacksquare$

By Mihailescu theorem no terms except for the last two can be perfect squares. On the other hand, $2^a + 1 = r^2 \iff 2^a = (r+1)(r-1),$ which yields $a=3$ only. $2^a -1 = r^2$ fails by mod $4$ for $a \geq 3$ , thus $a=1$ or $a=3$ .

Now the condition can only really be true for finitely many $k$ , as we need each of the terms on the RHS to be precisely prime. For $a = 3$ , only $n=6$ works, and for $a=1$ , $n = 2, 4, 8, 16, 32$ work as $2^{2^5} + 1$ is the first non-Fermat prime, done.

This post has been edited 1 time. Last edited by HamstPan38825, Apr 9, 2023, 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.

pi271828

3368 posts

pi271828

#47 h Jul 7, 2023, 1:31 PM

Y by

Let $n = 2^a \cdot b$ . Now, $2^n-1 = (2^b-1) \cdot \prod_{i=0}^{a-1} (2^{2^i \cdot b}+1)$ Notice that all these terms are relatively prime due to Euclidean Algorithm. We require $\tau(2^b-1) \cdot \prod_{i = 0}^{a} \tau(2^{2^{i} \cdot b}+1) = n$ . Notice that there must be at least $2$ squares out of all the terms $2^b - 1, 2^b +1, 2^{2b}+1, \dots, 2^{(2^a \cdot b)} +1$ . This is due to the fact that the LHS has $a+1$ terms, and the RHS has $v_2$ of $a$ . This means there must be at least $1$ square among those terms. This implies that $b = 1, 3$ . Casework finishes.

Z K Y

The post below has been deleted. Click to close.

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

huashiliao2020

1292 posts

huashiliao2020

#48 h Sep 3, 2023, 11:59 PM

Y by

Very nice problem, writeup takes a while though. To no one in particular: Can you check this one carefully im not sure if fakesolve

It's obvious by mod 4 that n is even (except for the trivial n=1), so write $n=2^ab,2^n-1=(2^b-1)(2^b+1)(2^{2^1b}+1)...(2^{2^{b\frac n2}}+1)\quad(1)$ ; it's easily computed that these terms are pairwise relatively prime. This is important because if n has an odd factor >1, to have an odd factor in number of divisors, at least one from each of the terms in the factorization of (1) must have a perfect square in it's terms (since we have pairwise relativity); remarking that $(2c+1)^2=2^k+1\iff 2^k=4c(c+1)\implies c=1,k=3$ , assuming b>1, we must have b=3.

Case 1: $2^b-1$ is a perfect square. Mod 4 it's immediate that b=1, so $n=\tau(2^1+1)\tau(2^2+1)...\tau(2^{2^{a-1}}+1),$ where tau denotes the number of divisors function. Since the RHS has $a$ terms, all of them must be $2$ , which implies that $2^{2^i}+1$ is prime, and since $2^{2^5}+1$ is composite, $k\le 5$ ; checking, all of them work. We conclude the numbers 1,2,4,16,32 work.

Case 2: $2^m+1$ is a perfect square. From earlier, we know b=3, so $2^a 3=\tau(7)\tau(2^3+1)\tau(2^{2^13}+1)...\tau(2^{2^{a-1}3}+1)\iff2^a=\tau(7)\tau(2^{2^13}+1)...\tau(2^{2^{a-1}3}+1).$ Again, since there are a terms on the right, each of them must be 2 (meaning the terms inside the tau are prime), but $2^6+1$ is not prime, so $a\le 1$ ; checking, only $n=6$ works.

We conclude the final answer is $\boxed{\{1,2,4,6,8,16,32\}}$ . $\blacksquare$

This post has been edited 1 time. Last edited by huashiliao2020, Sep 3, 2023, 11:59 PM

Z K Y

The post below has been deleted. Click to close.

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

Math4Life7

1703 posts

Math4Life7

#49 h Sep 19, 2023, 2:36 AM

Y by

We can see that $n$ must be even. This is because $2^n -1$ is never a perfect square by $\pmod{4}$ unless $n = 1$ which is a solution.

Thus we let $n = 2^ab$ for $a \geq 1$ . We can see that we can factor the given as $(2^b - 1)(2^b+1)(2^{2b}+1) \ldots (2^{2^{a-1}b} +1)$ . We claim that all of these divisors are relatively prime.

First, we compare $(2^b-1)$ and $(2^{2^xb} + 1)$ . We take a prime $p$ such that $p|2^b-1$ this means that $2^b = 1 \pmod{p}$ and consequently $2^{2^xb} \equiv 1 \pmod{p}$

Second, we compare $(2^{2^xb}+1)$ and $(2^{2^yb} +1)$ where $x <y$ . We take a prime $p$ such that $p|2^{2^xb}+1$ this means that $2^{2^xb} \equiv -1 \pmod{p}$ and consequently $2^{2^yb} \equiv 1 \pmod{p}$

Now note $\tau(2^n-1) = \tau(2^b-1) \cdot \tau(2^b+1) \cdot \tau(2^{2b}+1) \ldots \tau(2^{2^{a-1}b}+1)$ Since there are $a+1$ terms on the LHS one of them must be a perfect square. Since even powers never produce a perfect square we only consider $2^b-1$ and $2^b+1$ .

If $2^b -1$ is a perfect square then we can take $\pmod{4}$ to see that $b = 1$ from this we get the solutions $1, 2, 4, 8, 16, 32$ (from fermat primes).

If $2^b+1$ is a perfect square then we can see that if $v_2(b) = x$ then $2^x + 1$ is a divisor of $2^b + 1$ . This means that we need $(2^x + 1)^2 = 2^b+1$ . This gives that $b = 3$ which indeed gives the solution $6$ (note we cannot multiply this by $2$ since $\tau(2^6+1) = 4$ which gives too much $v_2$ ).

Combining our answer is $\boxed{1, 2, 4, 6, 8, 16, 32}$ . $\blacksquare$

This is incredibly similar to this.

This post has been edited 1 time. Last edited by Math4Life7, Sep 19, 2023, 2:39 AM

Z K Y

The post below has been deleted. Click to close.

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

AtharvNaphade

341 posts

AtharvNaphade

#50 h Sep 29, 2023, 5:18 AM

Y by

Let $n = p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . We have $\tau(2^{n} - 1) = p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . By Zsigmondy's, there exists unique prime for each divisor $d | n$ except $d = 1, 6$ . This means there are at least $(e_1 + 1)(e_2 + 1)\dots (e_k + 1)-2$ distinct primes dividing $2^n-1$ , so there at least $2^{(e_1 + 1)(e_2 + 1)\dots (e_k + 1)-2}$ divisors of $\tau(2^n-1)$ . However we know the number of divisors of $n$ is $(e_1 + 1)(e_2 + 1)\dots (e_k + 1)$ , which implies $k \leq 2$ .

For $k = 2$ we need the inequality to be an equality, meaning $6 | n$ and $e_i = 1$ giving only $n = 6$ which works.

For $k=1$ we have $\tau(2^{p^k} - 1) = p^k$ . We can see $p = 2$ since otherwise all the prime factors of $2^{p^k} - 1$ have even powers, implying $2^{p^k} - 1$ is a perfect square, impossible mod 4. Then $2^{p^k} - 1 = (2^{2^{k-1}}+1) (2^{2^{k-2}}+1)\dots (2+1).$ This gives exactly $k$ prime factors unless $n\geq 6$ by fermat primes, but we need $\leq k$ prime factors. Checking, our answers are then $\boxed{1, 2, 4, 6, 8, 16, 32}$

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1730 posts

OronSH

#51 h Dec 6, 2023, 3:05 PM • 3 Y

Y by ihatemath123, megarnie, mathmax12

Answer is $1,2,4,6,8,16,32.$

First if $n$ is odd we get $2^n-1$ is a square so $2^n=m^2+1$ but $m^2+1 \equiv 1,2 \pmod 4$ so $n=1$ which works.

Next if $\nu_2(n)=1$ we let $n=2k$ and we see $2^n-1=(2^k-1)(2^k+1)$ and when $k \ne 1,3$ we see that neither of these terms are squares (e.g. by Mihailescu) and these are relatively prime so $\nu_2(d(2^n-1)) \ge 2$ when $n \ne 2,6$ and checking $n=2,6$ both work.

Next we prove by induction that $\nu_2(n)<\nu_2(d(2^n-1))$ when $n=2^i k$ where $i$ is a positive integer and $k=32,6,$ or any odd positive integer greater than $3.$ The base cases are when $i=1,$ and we can check these easily (using the well-known factorization of $2^32+1$ for $k=32,$ and using our above work for $k$ odd.) Now suppose this is true for $n=2^i k.$ We will show it is also true for $n=2^{i+1}k.$ We have $\nu_2(2^{i+1}k)=1+\nu_2(2^i k),$ and $\nu_2(d(2^{2^{i+1}k}-1))=\nu_2(d(2^{2^i k}-1))+\nu_2(d(2^{2^i k}+1)).$ However, similarly as above we have $2^{2^i k}+1$ is not a square so $\nu_2(d(2^{2^i k}+1)) \ge 1$ and combining this with our inductive hypothesis we finish.

It remains to check the cases $n=4,8,16,32$ which are easy.

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

616 posts

cursed_tangent1434

#52 h Dec 29, 2023, 3:58 AM • 2 Y

Y by Shreyasharma, GeoKing

Solved with Shreyasharma. We claim that the answer is $1,2,4,6,8,16,32$ only. Throught the solution, let $d(n)$ denote the number of factors of $n$ .

First, we have the following key claim.

Claim : $2^n-1$ and $2^n+1$ are not perfect squares for any $n\geq 4$ .
Proof : We let $2^n-1=x^2$ . Now, note that for all $n\geq 2$ , $x^2+1 = 2^n \equiv 0 \pmod{4}$ . Thus, $x^2\equiv 3 \pmod{4}$ which is a clear contradiction. Then, we let $2^n+1=x^2$ . Now, $2^n=x^2-1=(x-1)(x+1)$ . But, clearly almost one of these is divisible by 4. Thus, since we must have $x$ odd, one of $x-1$ or $x+1$ must be 2. Thus, $x=3$ or $x=1$ . This implies that $n=3$ , which is not in our range. Thus, the desired claim is in fact true.

Now, we have a look at the powers of two. Note that, $2^{32}+1$ is not prime (well yeah you are supposed to know this). Thus, $2^{64}-1$ has more than, $32\times 2 = 64$ factors. For all powers of two, $2^{2^m}$ for $m\geq 7$ we then have,
$d(2^{2^m}-1)=d((2^{2^{m-1}}-1)(2^{2^{m-1}}+1)) = d(2^{2^{m-1}}-1)d(2^{2^{m-1}}+1)>2^{m-1} \times 2 = 2^m$ and thus, no solutions of this form exist for $m\geq 6$ .

Now, that we have put that out of the way we look at numbers of the form $n=3\cdot 2^m$ . Clearly, $3$ fails. Note that $2^12-1$ has $24$ factors. Thus, for all $m \geq 3$ ,
$d(2^{3\cdot2^{m}})=d((2^{3\cdot2^{m-1}}-1)(2^{3\cdot 2^{m-1}}+1))=d(2^{3\cdot2^{m-1}})d(2^{3\cdot 2^{m-1}}) > 3\cdot 2^{m-1} \times 2 = 3\cdot 2^m$ Thus, no solutions of this form exist for $m\geq 2$ .

Now, we look at $n=2^mk$ where $k\geq 5$ . We use our original claim in our solution and further note the following claim.

Claim : For all $m_1<m_2$ , $\gcd(2^{2^m_1}+1,\gcd(2^{2^m_2} +1)=1$ .
Proof : We simply look at
$\gcd(2^{2^{m_1}}+1,\prod_{i=1}^{m_1-1}2^{2^{i}}+1)=\gcd(2^{2^{m_1}}-1,2^{2^{m_1}}+1)=1$ Thus, we can see that the claim is true.

Now, note that,
$\begin{align*} \nu_2(d(2^n-1))&=v_2(d(2^m-1)(2^m+1)\dots(2^{2^{k-1}m}+1))\\ &= v_2(d(2^m-1))+v_2(d(2^m+1))+\dots + v_2(d(2^{2^{k-1}m}+1))\\ & \geq k+1 \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ by our first Claim none of these terms are odd}\\ &>k\\ &= v_2(2^km)\\ &= v_2(n) \end{align*}$ Thus, $v_2(d(2^n-1))>v_2(n)$ for all $n=2^km$ ( $k\geq 0$ and $k\geq 5$ ). Thus, it is impossible to have $d(2^n-1)=d(n)$ in these cases. We have explored all other cases separately before and they yielded no solutions besides the one's claim which can be confirmed quite easily using knowledge of Fermat Primes ~~or simply using Wolfram Alpha~~.

This post has been edited 2 times. Last edited by cursed_tangent1434, Dec 29, 2023, 4:00 AM
Reason: latex

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

#54 h Feb 10, 2024, 12:13 AM

Y by

Let $n=2^a b$ , we have
$2^n-1=(2^b-1)(2^b+1)\left(2^{2^1 b}+1\right)\cdots \left(2^{2^{a-1}b}+1\right)$ $\textcolor{blue}{\text{All terms in the product are relative primes}}$
First we prove the first term is relative prime with any other
$\begin{align*} \gcd(2^b-1,2^{2^i\cdot b}+1) &= \gcd( 2^b-1, 2^{2^i\cdot b}+1-(2^{2^i\cdot b}-1)) \\ &= \gcd(2^b-1,2)=1 \end{align*}$ And if $i<j$
$\gcd(2^{2^i\cdot b}+1,2^{2^j\cdot b}+1)=d$ then $d\mid 2^{2^i\cdot b}+1$ so $2^{2^j\cdot b}\equiv 1\pmod d$ then $d=1$

$\textcolor{blue}{\text{Any terms in the product is a square for}\hspace{0.2cm} b>3}$
Note $2^{\text{even}}+1\equiv 3\pmod 3$ so only $2^b-1$ or $2^b+1$ can be a square, and by Catalan $b=1$ or $b=3$

Then, we have
$d(2^n-1)=d(2^b-1)\cdot d(2^b+1)\cdot d\left(2^{2^1 b}+1\right)\cdots d\left(2^{2^{a-1}b}+1\right)$ But every term in the RHS is even then $2^{a+1}\mid \text{RHS}$ but the LHS is $n$

Thus it suffices to check the cases when $b=1$ or $b=3$

If $b=1$ then $n=2^a$ , we want
$2^a=d(2^n-1)=d(1)\cdot d(2^1+1)\cdot d\left(2^{2^1 }+1\right)\cdots d\left(2^{2^{a-1}}+1\right)$ But as any number has at least $2$ divisor then every number in the RHS has to be prime which by Fermat numbers $a\leq5$
here the answer are $\boxed{n=1,2,4,8,16,32}$
If $b=3$ then $n=2^a\cdot 3$ , we want
$2^a\cdot 3=d(2^n-1)=d(7)\cdot d(2^3+1)\cdot d\left(2^{2^1\cdot 3}+1\right)\cdots d\left(2^{2^{a-1}\cdot 3}+1\right)$ As before, every term has more than $2$ divisors but if exist some number in the product with four divisors it can satisfies, which occurs at $a=2$ so only $n=3,6$ can satisfies but only $\boxed{n=6}$ gives a solution.

So the solutions are $\boxed{n=1,2,4,8,16,32,6}$

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

#55 h Feb 12, 2024, 8:36 PM

Y by

The answer is $n = \boxed{1,2,4,6,8,16,32}$ , which can be checked to work with Fermat's primes.

Let $n=2^a \cdot k$ for an odd $k$ . We have

$2^n-1 = (2^a-1)(2^a+1)(2^{2^1 \cdot k}+1)\dots (2^{2^{a-1} \cdot k}+1)$
Suppose that $k \ge 5$ .

It is relatively simple to prove that the terms are pairwise relatively prime, and Mihailescu shows that none of the terms are perfect squares. Hence,

$\nu_2(\tau(2^n-1)) = \nu_2(\tau(2^n-1))+\sum_{i=0}^{a-1} \nu_2(\tau(2^{2^i \cdot k})) \ge a+1.$
This means that $k=1,3$ . The answers follow.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#56 h Mar 2, 2024, 7:01 AM

Y by

Our answers are $\boxed{1,2,4,6,8,16,32}$ . First note, by Catalan Conjecture for instance, the only values of $m$ for which $2^m-1$ and $2^m+1$ are perfect squares are $m=1$ and $m=3$ , respectively, so odd $n>1$ all fail. If we suppose $n=2^ab$ , where $b$ is odd, then
$2^{2^ab}-1 = \left(2^{2^{a-1}b}+1\right) \left(2^{2^{a-2}b}+1\right) \ldots \left(2^b+1\right) \left(2^b-1\right).$
Each of the factors are pairwise relatively prime, so we can invoke the multiplicativity of $\tau$ . Besides the edge cases $b=1,3$ mentioned earlier, which gives us the solutions above, we know for each factor $f$ ,
$v_2(\tau(f)) \ge 1 \implies v_2(\tau(2^n-1)) \ge a+1 > v_2(n) \text{, contradiction. } \blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 2, 2024, 7:02 AM

Z K Y

The post below has been deleted. Click to close.

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

peppapig_

281 posts

peppapig_

#57 h Mar 14, 2024, 5:18 PM

Y by

I claim that the only possible $n$ are $1$ , $2$ , $4$ , $6$ , $8$ , $16$ , and $32$ . These clearly work through factoring.

C1: I now claim that all working $n>1$ must be even. This is because if $n>1$ is odd, then this implies that $2^n-1$ is a perfect square. However, note that since $n\geq3$ , this means that $2^n-1$ is $3$ mod $4$ , meaning that it cannot possibly be a perfect square. Therefore, if we let $n=2^kq$ , we can factor $2^n-1$ as
$2^n-1=(2^q-1)(2^q+1)(2^{2q}+1)\dots(2^{2^{(k-1)}q}+1),$ all of which I claim are relatively prime. I will prove as such in the following two claims.

C2: I claim that $2^q-1$ and $2^{2^mq}+1$ are always relatively prime for all positive integers $m$ . This is because if a prime $p\mid 2^q-1$ , this implies that $p\mid 2^{2^mq}-1$ . However, by Euclidean Algorithm, since both $2^{2^mq}-1$ and $2^{2^mq}+1$ are odd, this means that they are relatively prime. Therefore no prime $p$ dividing $2^q-1$ divides $2^{2^mq}+1$ , meaning that the two are relatively prime.

C3: I claim that for any two positive integers $m<n$ , $2^{2^mq}+1$ and $2^{2^nq}+1$ are relatively prime. This is because if a prime $p\mid 2^{2^mq}+1$ , then we have
$2^{2^nq}-1 \equiv 0\mod p,$ since $m<n$ and we can expand using difference of squares. Therefore, this means that $2^{2^nq}+1$ must be $2$ mod $p$ . However, since $2^{2^mq}+1$ is odd, this implies that $2$ mod $p$ is not $0$ mod $p$ , meaning that no prime $p$ dividing $2^{2^mq}+1$ divides $2^{2^nq}+1$ , meaning that the two are relatively prime.

Therefore, all terms of this expansion are relatively prime. If we let $d(x)$ be the divisor function, this implies that
$n=d(2^n-1)=d(2^q-1)*d(2^q+1)*d(2^{2q}+1)*\dots*d(2^{2^{(k-1)}q}+1).$ However, note that there are $k+1$ terms multiplied together and $\nu_2(n)=k$ , implying that one of $d(2^{2^mq}+1)$ or $d(2^q-1)$ must be odd, implying that one of $2^{2^mq}+1$ or $2^q-1$ must be a perfect square. However, if $2^mq$ is even, then that implies that $2^{2^mq}+1$ cannot be a perfect square. Therefore, we consider $2^q+1$ and $2^q-1$ .

C4: Note that if $2^q-1$ is a perfect square, then $q$ must be $1$ , otherwise if $q\geq2$ , we would get that $2^q-1$ is $3$ mod $4$ , making it impossible to be a perfect square. Setting $q=1$ , we get that
$2^k=d(1)*d(2^1+1)*d(2^2+1)*\dots*d(2^{2^{k-1}}+1),$ which implies that every term must have exactly $2$ factors, otherwise we'd not get $2^k$ as our answer. Therefore every term must be prime, and using Fermat Primes, we get that our only solutions using this are $1$ , $2$ , $4$ , $8$ , $16$ , and $32$ .

C5: Now if $2^q+1$ is a perfect square, by Mihâilescu's Theorem/Catalan's Conjecture, we can get that the only possible $q$ here is $q=3$ . Therefore, if we have $q=3$ , we then have
$3*2^k=d(7)*d(2^3+1)*d(2^{3*2}+1)*\dots*d(2^{3*2^{k-1}}+1),$ and note that again, each number contributes at least $+1$ to the $\nu_2$ of the product. If there is one term with more than $+1$ to the $\nu_2$ (meaning the $d(2^{3*2^m}+1)$ is divisible by $4$ ), then all $k\geq m$ will have too high of a $\nu_2$ in its product, not allowing them to be solutions. Since $\nu_2(d(2^6+1))=4$ , we have that $n=3*2^k$ with $k\geq 2$ do not work. This gives us the only possible solutions are $n=3$ and $n=6$ , the former of which is extraneous by (C1).

Therefore our only solutions are $1$ , $2$ , $4$ , $6$ , $8$ , $16$ , and $32$ , finishing the problem.

This post has been edited 2 times. Last edited by peppapig_, Mar 14, 2024, 6:11 PM
Reason: Typo

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

#58 h Mar 14, 2024, 11:59 PM

Y by

megarnie wrote:

Find all integers $n\ge1$ such that $2^n-1$ has exactly $n$ positive integer divisors.

Proposed by Ankan Bhattacharya

im actually malding on 45 moh. time to do trivial problems.

Write $n=2^e\cdot o$ . We obtain
$2^n-1=(2^{n/2}+1)(2^{n/4}+1)\dots(2^{n/2^e}+1)(2^{n/2^e}-1).$ These are all pairwise relatively prime. If none are a square, then
$e=\nu_2(n)=\nu_2(d(2^n-1))\ge e+1$ which fails. Hence one of these is a square, and it must clearly be one of the last two terms: one of $2^o+1$ and $2^o-1$ is a square.

If $o\ge 3$ then the square must be $9$ and $o=3$ by Mihailescu.

Else $o=1$ . At this point we can just induct upwards.

$n=1$ works.
$n=2$ works.
$n=4$ works.
$n=8$ works.
$n=16$ works.
$n=32$ works.
$n=64$ fails as $2^{32}+1$ is not prime, and everything above must fail too.

Also we have

$n=3$ fails.
$n=6$ works.
$n=12$ fails as $65$ is not prime, and everything above must fail too.

Final solution set is $\{1,2,4,8,16,32,6\}$ .

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

614 posts

Ilikeminecraft

#59 h Apr 26, 2025, 12:03 AM

Y by

I claim the answer is $\boxed{1, 2, 4, 6, 8, 16, 32}.$ This is easily verifiable. I will now prove these are the only ones.

Let $\nu_2(n) = m, n = 2^m \cdot k.$ Thus, $2^n - 1 = 2^{2^mk} - 1 = (2^{k } - 1)(2^k + 1)(2^{2k} + 1)\cdots(2^{2^{m - 1}k} - 1)$ I claim that any 2 terms on the RHS are relatively prime. First, we have that $(2^k - 1, 2^{2^ik} + 1) = (2^k - 1, 2) = 1.$ Now, let $0 < i < j < k.$ $(2^{2^ik} + 1, 2^{2^{j}k} + 1) = (2^{2^{ik}} + 1, 2) = 1.$ Thus, they are relatively prime.

By Catalan's conjecture, we have that $2^n - 1$ is only a perfect square when $n = 1,$ and $2^n + 1$ is a perfect square when $n = 3.$ Thus, if $k\geq5,$ the number of divisors on the RHS is divisible by $m + 1$ even integers. However, we know that $\nu_2(n) = m,$ which is a contradiction. We will now focus on $k = 1, 3.$

If $k = 3,$ we see that $n = 6$ is a solution. I claim that there are no more. At $n = 12,$ we have that $2^6 + 1 = 65 = 5\cdot13.$ Hence, the number of divisors of $2^{12} - 1$ is 24. We prove the rest with induction. Let $n = 3\cdot2^m.$ Assume that the number of divisors of $n$ is $\geq n.$ By Zsigmondy, we have that there exists a prime dividing $2^{3\cdot2^{m + 1}} - 1$ that adoesn't divide $2^{3\cdot2^{m}} - 1.$ Hence, the number of divisors at minimum doubles, while $n$ also doubles. Hence, there is no solution.

If $k = 1,$ by similar reasoning, we only have solutions up to $m = 5.$

Z K Y