Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Lemma 1: If $(a,b)=1$ and $a,b$ are odd, then $(2^a+1,2^b+1)=3$. Proof: Let $d=(2^a+1,2^b+1)$. $3|d$ and $d|(2^{2a}-1,2^{2b}-1)=2^{(2a,2b)}-1=2^2-1=3$, so $d=3$. $\blacksquare$ Lemma 2: If $3\not |a$ ($a$ is odd), then $9\not |2^a+1$. Proof: If $a=3k+1$ we have $2^a+1=2(2^{3k}+1)-1=9t-1$, and if $a=3k+2$ we have $2^a+1=4(2^{3k}+1)-3$. $\blacksquare$ Let $N=p_1\ldots p_n,\ N'=\frac N{p_n}$. For $n=1$, the result is easy to prove: $2^p+1$ has the divisors $1, 3, \frac{2^p+1}3, 2^p+1$. We have $3\ne \frac{2^p+1}3$ because $p>3$. We can now use induction. Assume we have shown it for $n-1$. This means that $2^{N'}+1$ has at least $4^{n-1}$ divisors. We have $2^{N'}+1|2^N+1,\ \frac{2^{p_n}+1}3|2^N+1$, and we can apply the lemmata for $a=p_n, b=N'$ to get $\frac{2^{p_n}+1}3\big|\frac{2^N+1}{2^{N'}+1}$. On the other hand, we clearly have $\left(\frac{2^{p_n}+1}3\right)^2<\frac{2^N+1}{2^{N'}+1}$, which means that $\frac{2^N+1}{2^{N'}+1}$ has at least four divisors $1=d_1,d_2,d_3,d_4$. For each $d|2^{N'}+1$, each of $d_id$ is a divisor of $2^N+1$, and all $d_id$ are different because $(d_i,d)=1$, hence the result: $2^N+1$ has at least $4\cdot 4^{n-1}=4^n$ divisors.

Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $2^{p_1...p_n} + 1$ has at least $2^{2^{n-1}}$ divisors, which is larger than $4^n$. Can someone please try to solve it in that way? Tnx

Consider $2^{mn} + 1 = (2^n + 1)(2^{n(m - 1)} - 2^{n(m - 2)} + ... + 1) = PQ,Q = m\mod P = 2^n + 1$. In these way we can prove, that for any odd m>3 exist prime p, suth that $p|2^m + 1$ and $p|2^n + 1\to m|n.$ Therefore for your case (any primes greater 3 we had $N\ge 2^n$ disdinct primes $p_k|2^m + 1, m = p_1p_2...p_n$ (one for any divisor m). Therefore number of divisors $2^m + 1 = p_1^{k_1}....p_N^{k_N}$ equal $(k_1 + 1)...(k_N + 1)\ge 2^{2^n}$. If one of odd primes in $m=p_1...p_n$ is equal 3, then number of divisors $2^m+1$ greater or equal $3*2^{2^n-2}$.

SpongeBob wrote: Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $2^{p_1...p_n} + 1$ has at least $2^{2^{n - 1}}$ divisors, which is larger than $4^n$. Can someone please try to solve it in that way? Tnx Let $\prod_{i = 1}^{n} p_i = P$. Then $2^P + 1 = \prod_{d | P} \Phi_{2d} (2)$. $P$ has $2^n$ divisors $d$, hence there are $2^n$ factors on the RHS. Consider two divisors $a, b$ of $P$. We have $\gcd(2^{2a} - 1, 2^{2b} - 1) = 2^{2\gcd(a, b)} - 1$. Now, the RHS can be written as a product of cyclotomic polynomials $\Phi_{2d} (2)$ where $d | \gcd(a, b)$. In particular, unless $a | b$ we know that $d < a, d < b$. Therefore $\gcd(\Phi_{2a}(2), \Phi_{2b}(2)) = 1$. We should be able to conclude from here that $P$ has at least $2^{n - 1}$ distinct prime factors, but I'm afraid I don't see the argument Edit: But of course! If $a | b$ then $\Phi_{2a}(2), \Phi_{2b}(2)$ are both factors of $2^{2b} - 1 = (2^b - 1)(2^b + 1)$ where $\gcd(2^b - 1, 2^b + 1) = 1$ and $\Phi_{2a}(2) | 2^b - 1, \Phi_{2b}(2) | 2^b + 1$, hence it is still true that $\gcd(\Phi_{2a}(2), \Phi_{2b}(2)) = 1$. Hence $P$ has at least $2^n$ distinct prime factors as Rust has stated.

Thanks a lot!

I think this works. We'll show that the desired number has at least $2n$ distinct prime factors, and thus at least $2^{2n} = 4^{n}$ factors. We induct on $n$, the base case is easy, since $2^{p_{1}} + 1$ has two prime factors, 3 and something else. Assume it's proven for $n - 1$, and let $A = p_{1}p_{2}\cdots p_{n - 1}$, $p = p_{n}$. $2^{Ap} + 1 = (2^{A} + 1)(2^{A(p - 1)} - 2^{A(p - 2)} + \cdots + 1)$. $2^{A} + 1$ contributes $2(n - 2)$ distinct prime factors by induction hypothesis. We need to show the second factor contributes 2 others. We can repeatedly apply the Euclidean Algorithm to get that the GCD of the two factors is $(2^{A} + 1,p)$, which is either 1 or $p$. First, consider what happens when it's 1. It suffices to show that the second factor is composite. Using grobber's lemma, $(2^{A} + 1,2^{p} + 1) = 3$, so $(2^{p} + 1)/3$ divides the second factor (as it divides the whole thing). Now, once we divide out $(2^{p} + 1)/3$ from the second factor, we'll be left with an integer something bigger than 1* relatively prime to the first factor, which will give us another prime factor. Thus, we have two new prime factors, the new one from $(2^{p} + 1)/3$ and the new one from the second factor divided by $(2^{p} + 1)/3$. *To see this, the second factor is equal to $(2^{p} - 1)(2^{A(p - 2)} + 2^{A(p - 4)} + \cdots + 2^{A}) + 1 = 2^{A}(2^{p} - 1)(mess) + 1 > 2^{p} + 1$. So the other case is if the gcd is $p$. Stuff basically works the same, we now instead of to take out $p(2^{p} + 1)/3$. Note that $2^{p} + 1\equiv 3\pmod{p}$ and $p > 3$ so $(p,2^{p} + 1) = 1$. By similar logic from before, $(2^{p} + 1)/3$ divides the whole second factor, giving us a new prime factor, and when we divide out $p(2^{p} + 1)/3$, we get something bigger than 1 relatively prime to the first factor, giving us another new prime factor, because $(2^{p} - 1)(2^{A(p - 2)} + 2^{A(p - 4)} + \cdots + 2^{A}) + 1 = 2^{A}(2^{p} - 1)(mess) + 1 > 2^{A + p} > 2^{p + 2} > p(2^{p + 1}) > p(2^{p} + 1)$. Sorry if that was hard to follow. If someone finds a hole let me know.

CatalystOfNostalgia wrote: INow, once we divide out $(2^{p} + 1)/3$ from the second factor, we'll be left with an integer something bigger than 1* relatively prime to the first factor, which will give us another prime factor. Thus, we have two new prime factors, the new one from $(2^{p} + 1)/3$ and the new one from the second factor divided by $(2^{p} + 1)/3$. How do you know that the second prime factor isn't the same as the first? For example, we could have something like $((2^{p} + 1)/3)^2$, then dividing $(2^{p} + 1)/3$ won't give you a new prime factor. You can fix this by saying if $q|(2^{p} + 1)/3$ then $2^{A(p-1)}-2^{A(p-2)}+\cdots+1$ is not divisible by $q^3$, and $2^{A(p-1)}-2^{A(p-2)}+\cdots+1>((2^{p} + 1)/3)^2$. Then you can have a new prime factor. Also you can eliminate the second case by assuming $p$ is the smallest among all primes in the exponents. If $2^{Ap}\equiv -1(p)$, then $2^{(2Ap, p-1)}\equiv 1(P)$. But $(2Ap, p-1)=2$ and $p>3$. So $(2^A+1, 2^{A(p-1)}-2^{A(p-2)}+\cdots+1)=1$

nealth wrote: if $q|(2^{p} + 1)/3$ then $2^{A(p - 1)} - 2^{A(p - 2)} + \cdots + 1$ is not divisible by $q^3$ Thanks for pointing this out -- but how come this is true? (I know you're at MOP, but if anyone can answer this...)

t0rajir0u wrote: SpongeBob wrote: Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $2^{p_1...p_n} + 1$ has at least $2^{2^{n - 1}}$ divisors, which is larger than $4^n$. Can someone please try to solve it in that way? Tnx Let $\prod_{i = 1}^{n} p_i = P$. Then $2^P + 1 = \prod_{d | P} \Phi_{2d} (2)$. $P$ has $2^n$ divisors $d$, hence there are $2^n$ factors on the RHS. Consider two divisors $a, b$ of $P$. We have $\gcd(2^{2a} - 1, 2^{2b} - 1) = 2^{2\gcd(a, b)} - 1$. Now, the RHS can be written as a product of cyclotomic polynomials $\Phi_{2d} (2)$ where $d | \gcd(a, b)$. In particular, unless $a | b$ we know that $d < a, d < b$. I think the previous two sentences should be "Now, the RHS can be written as a product of cyclotomic polynomials $\Phi_{d} (2)$ where $d | 2\gcd(a, b)$. In particular, unless $a | b$ we know that $d < 2a, d < 2b$." t0rajir0u wrote: Therefore $\gcd(\Phi_{2a}(2), \Phi_{2b}(2)) = 1$. We should be able to conclude from here that $P$ has at least $2^{n - 1}$ distinct prime factors, but I'm afraid I don't see the argument Edit: But of course! If $a | b$ and $a\neq b$ t0rajir0u wrote: then $\Phi_{2a}(2), \Phi_{2b}(2)$ are both factors of $2^{2b} - 1 = (2^b - 1)(2^b + 1)$ where $\gcd(2^b - 1, 2^b + 1) = 1$ and $\Phi_{2a}(2) | 2^b - 1, \Phi_{2b}(2) | 2^b + 1$, I don't understand why $\Phi_{2a}(2) | 2^b - 1, \Phi_{2b}(2) | 2^b + 1$. t0rajir0u wrote: hence it is still true that $\gcd(\Phi_{2a}(2), \Phi_{2b}(2)) = 1$. Hence $P$ has at least $2^n$ distinct prime factors as Rust has stated. Also, you must prove that $\Phi_{2d}\left(2\right)>1$ for every positive integer $d$. Fortunately this is a known fact (geometrically more or less evident by drawing the regular $2d$-gon in the unit circle).

Solution : $N=2^{p_1p_2*...*p_k}+1=\prod_{d | p_1p_2*...*p_k}\Phi_{2d}(2)$ Use next Lemma : If for integer number x $\gcd(\Phi_{m}(x),\Phi_{m}(x))>1$ , then $\frac{n}{m}=p^{\lambda}$ , for integer $\lambda$ So if $k$ is odd then easy to see that if $a|p_1p_2*...*p_k$ , then if $b=\frac{p_1p_2*...*p_k}{a}$ , then $a$ , or $b$ has odd prime divisors from (p_1,p_2,...,p_k) , and number of such numbers is $2^{k-1}$ , if $k$ is even , then number of numbers $a|p_2p_3*...*p_k$ , were $a*p_1$ has odd number of prime divisors from (p_1,p_2,...,p_k) is $2^{k-2}$ and number of numbers $b|p_2p_3*...*p_k$ , were $b$ has odd number of prime divisors from (p_2,...,p_k) is $2^{k-2}$ , so number of numbers $c|p_1p_2p_3*...*p_k$ , were $c$ has odd number of prime divisors from (p_1,p_2,...,p_k) is $2^{k-2}+2^{k-2}=2^{k-1}$ , so take this $2^{k-1}$ numbers $x_1,x_2,...,x_{2^{k-1}}$ , and $\frac{x_i}{x_j}\neq p^{\lambda}$ , so $\gcd(\Phi_{x_i}(2),\Phi_{x_j}(2))=1$ , so $2^{p_1p_2*...*p_k}+1$ has at least $2^{2^{k-1}}$ divisors . done

We will prove that by induction, showing that the expression has at least $2n$ distinct prime divisors, which would show the problem. Base Case: $2^{p_1}+1$ is divisible by $3$ and an other prime. Inductive Case: Let $a=p_1p_2\cdots p_n$, and $b=p_{n+1}$. Lemma 1: The $gcd(2^x+1,2^y+1)=3$ for relatively prime positive odd integers $x,y$, where $3$ does not divide either. Proof: Let $p$ be a prime dividing both expressions. Then $ord_p(2)|gcd(2x,2y)$ or since $x,y$ are odd, $2^x+1\equiv 2+1\equiv 3\pmod{p}$. Thus $p=3$, using LTE to show that $9$ does not divide either. Lemma 2: The expression $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ has a prime divisor relatively prime to both $2^a+1$ and $2^b+1$ where $a,b$ are relatively prime positive odd integers. Proof: Note that since $2^a+1,2^b+1$ are relatively prime except for one factor of $3$ by lemma 1 and LTE, thus we know that $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ is an integer. Now, we have cases based on the whether the expressions for $2^a+1$ and $2^b+1$ are relatively prime to $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$. The proof for the case where both are is immediate, and the other three are proved in the same way as the case where both are not. Let $p|2^a+1$. Note that $\frac{2^{ab}+1}{2^a+1}\equiv -b\pmod{p}$, and since $b$ is prime, $p=b$ for divisibility and the only prime factor $\frac{2^{ab}+1}{2^a+1}$ and $2^a+1$ can share is $b$. By LTE, $v_b(2^{ab}+1)=v_b(2^a+1)+1$, thus $v_b(\frac{2^{ab}+1}{2^a+1})=1$. Let $p|2^b+1$. Then $\frac{2^{ab}+1}{2^b+1}\equiv -a\pmod{p}$. Then all the primes both can share divide $a$ and we can use LTE to show that $v_{p_i}(\frac{2^{ab}+1}{2^b+1})=1$. Let $gcd(\frac{2^{ab}+1}{2^b+1}, 2^b+1)=k$. We have that $$\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot k}\ge\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot a}> 1$$ Then $\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot k}$ is relatively prime to $2^a+1,2^b+1$ and has a prime divisor distinct from those in $2^a+1,2^b+1$. Now, to the problem, when we "add" $b$ to the exponent we have that $2^{ab}+1$ has a prime divisor added from $2^b+1$ by lemma 1 not in $2^a+1$. However, $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ "adds" another prime divisor to $2^{ab}+1$ and we obtain at least two new prime divisors. Thus our inductive step is complete.

Applying Zsigmondy's Theorem $2^{p_1p_2\ldots p_n}+1$ has atleast $2^n$ distinct prime factors. Because we can induct on $n$ and as $2k+1\mid 2m+1\implies 2^{2k+1}+1\mid 2^{2m+1}+1$ we get more $2^n$ factors, hence its true. For the base case $2^p+1$ has a factor distinct from $2^1+1=3$. Note that the exceptional case of $2^3+1$ never happens as all primes are greater than $3$. Thus it has $\ge 2^{2^n}$ distinct factors.

Without loss of generality let $p_1<p_2<...<p_n$.Then by Zsigmondy,there exists a prime divisor $q_i$ of $2^{p_i}+1$ which does not divide $2^{p_j}+1$ for all $j<i$(paricularly $3$).Thus there are at least $n+1$ prime factors(i.e.$3,p_1,p_2,....,p_n$) of $2^{p_1p_2.....p_n}+1$.Again by Zsigmondy,there exists a disinct prime divisor $r_1$ of $2^{p_1p_2}+1$ which does not divide $2^{p_1}+1$ and $2^{p_2}+1$.More generally there exists a distinct prime divisor $r_i$ of $2^{p_1p_2....p_{i+1}}+1$ which does not divide $2^{p_1p_2....p_j}+1$ for all $j<i+1$.Thus we found $n-1$ more prime divisors of $2^{p_1p_2...p_n}+1$(i.e.,$r_1,r_2,....,r_{n-1}$).So there are atleast $2n$ distinct prime divisors of $2^{p_1p_2...p_n}+1$ and hence atleast $2^{2n}=4^n$ divisors.

We use induction. First the base case. Let $p$ be a prime greater than 3. If $2^p+1$ has less than $4$ divisors, then it must be of the form $r$ or $r^2$ for some prime $r$. But $2^p+1$ is divisible by $3$, so either it is equal to $3$ ($q=1$, impossible) or $9$ ($q=3$, impossible). Thus $2^p+1$ has at least $4$ divisors. Assume the hypothesis holds true for $n$. Consider a set of $n+1$ distinct prime numbers $q<p_1<p_2<...<p_n$, all greater than $3$. Define $P=p_1p_2...p_n$. Note that $q$ does not divide $P$. By induction the hypothesis, $2^P+1$ has at least $4^n$ divisors. Consider the quotient $x=(2^{Pq}+1)/(2^P+1)$. It suffices to show that (1) $x$ has at least $4$ divisors and (2) $x$ is relatively prime to $2^P+1$. We prove (1) by contradiction. Assume $x$ has less than $4$ divisors, so it must be of the form $r$ or $r^2$ for some prime $r$. Since, $2^q+1$ divides $2^{Pq}+1$, $2^q+1$ divides $x(2^P+1)$. If $r$ does not divide $2^q+1$ then $2^q+1$ is relatively prime with $x$, thus $2^q+1$ divides $2^P+1$ so $q|P$ a contradiction. Thus $r$ divides $2^q+1$. Since $x \le r^2$ and $r \le 2^q+1$, we have the bound $x=(2^{Pq}+1)/(2^P+1) \le (2^q+1)^2$. The LHS is greater than $2^{Pq}/2^{P+1}=2^{Pq-(P+1)}$, and the $RHS$ is less than $2^{3q}$. Thus $Pq-(P+1)<3q$, which rearranges to $q<1+4/(P-3)$. The LHS is at least $5$ and the RHS is at most $3$, a contradiction. We now prove (2). Let $t$ be a prime dividing $2^P+1$. By LTE, $v_t(2^{Pq}+1)=v_t(2^P+1)+v_t(q)$. But $v_t(2^{Pq}+1)=v_t(x(2^P+1))=v_t(x)+v_t(2^P+1)$, so $v_t(x)=v_t(q)$. Thus either $t$ does not divide $x$ or $t=q$. If for every prime $t$ dividing $2^P+1$, $t$ does not divide $x$, then we have proved (2). So assume $q$ divides $2^P+1$. Note that $2^{2P}$ is congruent to $1\mod q$. By FLT, we also have that $2^{q-1}$ is congruent to $1 \mod q$. Thus $2^{\gcd(2P,q-1)}$ is $1 \mod q$. But $q$ is smaller than any of the primes dividing $P$, thus $q-1$ is relativeily prime to $P$. So $\gcd(2P,q-1)=2$ and we get $4$ is $1 \mod q$ or $q=3$, a contradiction. Thus $q$ does not divide $2^P+1$ and (2) is proved. A very nice problem in my opinion.

I have a highly overkill-based solution.... We proceed by induction on $n$ checking the base case as in other solutions. Note that $2^{p_1...p_{n+1}}+1$ is divisible by $2^{p_1...p_n}+1$ and by Zsigmondy it must have a prime divisor not dividing the second ugly expression. Moreover,it is evident by Mihailescu's theorem that $(2^{p_1...p_n})^{p_{n+1}}+1 \not= q^m$ where $q$ is a prime. So, we that the induction step is complete and this expression has at least $2n$ distinct prime divisors for every $n$ meaning $4^n$ divisors at least. This was highly overpowered with not much insight. Will post an elementary solution later.

We induct on $n$. $\blacksquare$ $n=1$ It suffices to show that $\left(2^p_1 +1 \right)$ has atleast 4 divisors where $p_1 \geq 5$ . It is trivial because ( By LTE ) , $\left(2^p_1 +1 \right)$ cannot be a power of 3 , and hence is divisible by atleast $2$ distinct primes. $\blacksquare$ (Induction hypothesis) Assume that $\left(2^{ p_1p_2 \cdots p_k}+1\right)$ has atleast $4^k$ divisors. $\blacksquare$ $n=k+1$ Pick a primitive prime factor of $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)$ and call it $q_1$.Pick a primitive prime factor of $\left( 2^{p_{k+1}} +1 \right)$ and call it $q_2$.Note that $q_1$ and $q_2$ are greater than $3$ and are mutually distinct. By our choice of these primes, $gcd( q_1q_2 ,\left(2^{ p_1p_2 \cdots p_k}+1\right) )=1$.So we may write $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)=\left(2^{ p_1p_2 \cdots p_k}+1\right)\cdot q_1\cdot q_2 \cdot q$ for some integer$q$.This allows us to show that there are atleast $4^k \cdot 4=4^{k+1}$ divisors of $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)$. This completes our proof.

Let $d_1,d_2,\ldots,d_{2^n}$ be the divisors of $p_1p_2\ldots p_n$. By Zsigmondy's theorem $2^{d_i}+1$ has a primitive prime factor for all $i$ except for if $d_i=3$ which is not possible since $p_k>3$. Hence, we have at least $2^n$ distinct prime divisors of $2^{p_1p_2\ldots p_n}+1$, so at least $2^{2^n}$ divisors.

my solution: let $q=\Pi_{i=1}^{n}p_{i}$ obviously, $2^{r}+1|2^{q}+1$,$r|q$ here we have $2^n$ divisors,and we also have $\frac{2^{q}+1}{2^{r}+1}$ so,we have $4^{n}$ divisors now we only say why do not exist same divisors it equals to say that exists x,y such that $(2^{x}+1)(2^{y}+1)=2^{q}+1$ it is same as $2^{x+y}+2^{x}+2^{y}=2^{q}$ compare the power of 2 then we have $x=y=1,q=3$ ( $\rightarrow\leftarrow$ ) done!

For $n=1$ we have that some divisors are $1, 3, \frac{2^{p_1}+1}{3}, 2^{p_1}+1$ hence this case is done. For $n=2$ we will use the cyclotomic representation of $2^{p_1p_2}+1$ $$2^{p_1p_2}+1=3 \cdot \Phi_{2p_1}(2) \cdot \Phi_{2p_2}(2) \cdot \Phi_{2p_1p_2}(2)$$ Now we verify that $v_3(2^{p_1p_2}+1)=v_3(2+1)+v_3(p_1p_2)=1$ and $\frac{2p_1}{2p_2}=\frac{p_1}{p_2}$ which is not a power of a prime number, hence we have guaranted $2^3=8$ prime factors but since none of the products u can create is $2^{p_1p_2}+1$ or $1$ we have $16$ divisors in total and hence on this case we are done. For $n \ge 3$ we will use again the cyclotomic representation of $2^{p_1p_2 \cdots p_n}+1$ $$2^{p_1p_2 \cdots p_n}+1=\prod_{k \mid p_1p_2 \cdots p_n} \Phi_{2k}(2)$$ Now from all of these $2^n$ factors we can notice that if we look for all $k$ such that $\gcd(\Phi_{2k}(2), \Phi_{2p_n}(2))=1$ then we are just looking for $\frac{k}{p_n}$ not being a power of a prime number which happens always except on $n-1$ cases, hence we have guaranted $2^n-n+1$ prime fractors hence we have guaranted at least $2^{2^n-n+1}$ divisors. Now we skip all we did so far and we will show by induction that $2^n \ge 3n-1$ for all $n \ge 3$ For $n=3$ we get equality so now we do inductive step, if it holds for $n=k$ we will prove it for $n=k+1$ $$2^{k+1}=2 \cdot 2^k \ge 6k-2 \ge 3k+2$$ Hence it holds for all $n$ which means that we have $2^{2^n-n+1} \ge 4^n$ divisors guaranted hence we are done

grobber wrote: . On the other hand, we clearly have $\left(\frac{2^{p_n}+1}3\right)^2<\frac{2^N+1}{2^{N'}+1}$, which means that $\frac{2^N+1}{2^{N'}+1}$ has at least four divisors $1=d_1,d_2,d_3,d_4$. For each $d|2^{N'}+1$, each of $d_id$ is a divisor of $2^N+1$, and all $d_id$ are different because $(d_i,d)=1$, hence the result: $2^N+1$ has at least $4\cdot 4^{n-1}=4^n$ divisors. Can you please give more clarity on this part of the proof. I did not get it.

anantmudgal09 wrote: I have a highly overkill-based solution.... We proceed by induction on $n$ checking the base case as in other solutions. Note that $2^{p_1...p_{n+1}}+1$ is divisible by $2^{p_1...p_n}+1$ and by Zsigmondy it must have a prime divisor not dividing the second ugly expression. Moreover,it is evident by Mihailescu's theorem that $(2^{p_1...p_n})^{p_{n+1}}+1 \not= q^m$ where $q$ is a prime. So, we that the induction step is complete and this expression has at least $2n$ distinct prime divisors for every $n$ meaning $4^n$ divisors at least. This was highly overpowered with not much insight. Will post an elementary solution later. I understand the Zsigmondy and Mihailescu theorem part. But I do not understand how the induction is complete. Can someone help me understand. Thanks, MathWhiz214

Let the divisors of $p_1p_2 \dots p_n$ be $d_1, d_2, d_3, \dots, d_{2^n}$. Note that $2^{d_i}+1$ has a primitive prime factor not dividing $2^{d_j}+1$ for any $j<i$ by Zsigmondy's Theorem. Note that each of these primes divides $2^{p_1p_2\dots p_{2^n}}$, so we have there is at least $2^{2^n} \ge 2^{2n}=4^n$ prime factors.

We proceed by induction. WLOG, let $p_1<p_2<\dots < p_n$. Clearly, any prime must be odd, so $a_1=2^{p_1}+1$ has divisors $1$, $3$, $\tfrac{a_1}{3}$, and $a_1$. $~$ Now, suppose that $a_n=2^{p_1p_2\dots p_n}+1$ has at least $4^n$ divisors. Consider $a_{n+1}=2^{p_1p_2\dots p_{n+1}}+1$. Note that $2^{p_1p_3\dots p_n p_{n+1}}+1\mid a_{n+1}$. This contains a prime factor not already divisible by $a_n$, and $2^{p_2p_3\dots p_n}+1$ contains an additional prime factor not already divisible by $a_n$, so $\tau(a_{n+1})\ge 4\tau(a_n)$ as desired.

Clearly, this is true when $n=1$, since $2^{p_1}+1$ is larger than 9 and divisible by 3. Now, we will induct. Suppose that $$N=2^{p_1\cdots p_n}+1$$ has $d$ divisors. We will then show that $$M=2^{p_1\cdots p_np_{n+1}}+1$$ has at least $4d$ divisors. Note that we have $N|M$ and $2^{p_{n+1}}+1|M.$ Claim 1: $$\gcd(N,2^{p_{n+1}}+1)=3.$$ Clearly, they are both odd but divisible by 3. Now, suppose for the sake of contradiction that they are divisible by some other prime $p\geq5.$ Then, $$2^{p_1\cdots p_n}\equiv -1\pmod p$$ and $$2^{p_{n+1}}\equiv -1\pmod p.$$ This would mean that $$ord_p(2)|2p_1\cdots p_n$$ and $$ord_p(2)|2p_{n+1}.$$ However, since the $p_i$ are distinct odd primes, we must then have $$ord_p(2)|2,$$ clearly a contradiction if $p\geq5.$ Thus, $$N\cdot\frac{2^{p_{n+1}}+1}{3}|M,$$ and furthermore $N$ is relatively prime to $\frac{2^{p_{n+1}}+1}{3}$, since $2^{p_{n+1}}+1$ is not a multiple of 9 as $p_{n+1}$ is not a multiple of 3. Claim 2: $$N\cdot\frac{2^{p_{n+1}}+1}{3}<\sqrt{M}.$$ Note that $N\geq33$ and $p_{n+1}\geq5$. We can use the relation $$M=(N-1)^{p_{n+1}}+1.$$ Plugging this into the inequality gives $$N^2(2^{p_{n+1}}+1)^2<9((N-1)^{p_{n+1}}+1).$$ This also becomes $$2\log_2(N)+2\log_2(2^{p_{n+1}}+1)<\log_2(9)+\log_2((N-1)^{p_{n+1}}+1).$$ Clearly, it suffices to show that $$2\log_2(N)+2\log_2(2^{p_{n+1}}+1)<p_{n+1}\log_2(N-1).$$ Now, since $p_{n+1}\geq5$, we have $$\log_2(2^{p_{n+1}}+1)<p_{n+1}+0.5,$$ so it suffices to show that $$2\log_2(N)+2p_{n+1}+1<p_{n+1}\log_2(N-1).$$ This is equivalent to $$p_{n+1}(\log_2(N-1)-2)>2\log_2(N)+1.$$ Note that $N\geq33$, so $\log_2(N-1)-2$ is positive. Thus, it suffices to show that this is true for the smallest value of $p_{n+1}$, which is 5. In this case, it becomes $$5\log_2(N-1)>2\log_2(N)+11,$$ which exponentiated becomes $$(N-1)^5>2048N^2.$$ This is clearly true for $N\geq33$, so we have shown Claim 2. To recap, we now know that: 1. $N(\frac{2^{p_{n+1}}+1}{3})$ is a factor of $M$. 2. $N$ is relatively prime to $\frac{2^{p_{n+1}}+1}{3}.$ 3. $N(\frac{2^{p_{n+1}}+1}{3})<\sqrt{M}.$ From (2), we have that $N(\frac{2^{p_{n+1}}+1}{3})$ has at least $2d$ factors, since the divisor function is multiplicative when they are relatively prime. Thus, $M$ has at least $2d$ factors that are less than $\sqrt{M}$. Therefore, $M$ has at least $4d$ factors, so we are finally done.

Take an arbitrary $d\mid p_1p_2...p_n$; this implies $2^d+1\mid 2^{p_1 p_2... p_n}+1$. By Zsigmondy's, $2^d+1$ has a prime p s.t. $p\nmid2^{d_0}+1\forall d_0<d$, which implies for each d (2^n of them) there's at least a prime factor in $2^{p_1p_2...p_n}+1$ (built by taking smallest d to largest, each one is distinct), implying the expressions has at least $2^{2^n}\ge2^{2n}=4^n$ factors. $\blacksquare$ @below indeed, zsigmondy has a harder proof than this problem itself, but zsigmondy does not immediately kill, nor does it generalize;

huashiliao2020 wrote: Take an arbitrary $d\mid p_1p_2...p_n$; this implies $2^d+1\mid 2^{p_1 p_2... p_n}+1$. By Zsigmondy's, $2^d+1$ has a prime p s.t. $p\nmid2^{d_0}+1\forall d_0<d$, which implies for each d (2^n of them) there's at least a prime factor in $2^{p_1p_2...p_n}+1$ (built by taking smallest d to largest, each one is distinct), implying the expressions has at least $2^{2^n}\ge2^{2n}=4^n$ factors. $\blacksquare$ But Zsigmondy's Thm isn't an easy one. So I think the solution is rather meaningless.

We induct on $n$. Notice that $$\nu_3(2^{p_1}+1)=1$$ and yet $2^{p_1}+1>3$ hence $2^{p_1}+1$ has at least $4$ divisors. Now suppose $m=2^{p_1\dots p_n}+1$ has at least $4^n$ divisors for $n\ge 1$. We prove that $M=2^{p_1\dots p_{n+1}}+1$ has at least $4^{n+1}$ divisors. By Zsigmondy, $M$ has a primitive prime divisor $P$---by definition, $P$ is relatively prime to $m$. Now consider the quantity $q=\frac{2^{p_{n+1}}+1}{3}$. Evidently three things hold: $q$ is relatively prime to $P$ by definition of $P$. $q$ divides $M$. $q$ and $m$ are relatively prime. This is slightly harder to prove: notice that $$m\mid 2^{2\cdot p_1\dots p_n}-1=A$$ and $$q\mid 2^{2\cdot p_{n+1}}-1=B$$ and therefore $$\gcd\{m,q\}\mid \gcd\{A,B\}=2^2-1=3$$ and because $3\nmid q$ it follows that $q$ and $m$ are relatively prime. As a result $M$ is a multiple of $m\cdot P\cdot q$. Thus $$\tau(M)\ge \tau(m)\cdot \tau(P)\cdot \tau(q)\ge 4^n\cdot 2\cdot 2=4^{n+1}$$ where $\tau(q)\ge 2$ is trivial. $\blacksquare$

Let $k=p_1p_2 \cdots p_n$. Consider the $2^n$ factors of $k$, denoted as $1=x_1 < \cdots < x_{2^n}=k$. By Zsigmondy's theorem, we may choose primes $q_1, \cdots, q_{2^n}$ such that $q_i \mid 2^{x_i}+1$, $q_i \neq q_j$ for all $1 \leq i<j \leq 2^n$. So $2^k+1$ has at least $2^n$ prime factors, so $d(2^k+1) \geq 2^{2^n} \geq 4^n$.

We proceed with induction. Without loss of generality, assume $p_i<p_{i+1}$ for all $i\in[n-1]$. Base Case: If $n=1$, by LTE: $$v_3(2^{p_1}+1)=v_3(3)+v_3(p_1)=1.$$ Clearly, $2^{p_1}+1>9$, so $\exists$ a $p>3$ such that $p\mid 2^{p_1}+1$, which implies that $2^{p_1}+1$ has at least $4$ divisors $\square$ Inductive Step: Assume for all $1\leq k\leq n-1$, $2^{p_1\cdot p_2\dots p_k}+1$ has at least $4^k$ divisors. Let: $$A_i=\frac{1}{p_{n+1-a}}\cdot\prod_{j=1}^{n}p_j,$$ $$X=2^{p_1\cdot p_2\dots p_n}+1.$$ Note that $A_i<A_{i+1}$ for all $i\in [n-1]$. Claim: For any two $A_i,A_j$, $i<j$, $\exists$ a $p$ such that: $$p\nmid 2^{A_i}+1\land p\mid 2^{A_j}+1$$ Proof: Since $A_i$ and $A_j$ share exactly $n-1$ elements, by LTE, it suffices to show that for any distinct primes $p_i<p_j$, $\exists$ a $p$ such that: $$p\nmid 2^{p_i}+1\land p\mid 2^{p_j}+1.$$ As $p_j$ is prime, $\text{ord}_p(2)=2p_j>2p_i$. This implies that: $$2^p_{i}\not\equiv -1\pmod{p},$$ as desired $\square$ Now consider a $p_i\mid 2^{A_i}+1$. By LTE: $$v_{p_i}(X)=v_{p_i}(2^{A_i}+1)+v_{p_i}(p_{n+1-a})\geq v_{p_i}(2^{A_i}+1).$$ By our claim: $$\exists\text{ a prime }p\nmid 2^{A_1}+1,\land p\mid X$$ $$\exists\text{ a prime }p\nmid 2^{A_1}+1,2^{A_2}+1\land p\mid X,$$ for which these two are distinct primes. This implies that the number of divisors of $X$ is greater than or equal to, by our inductive hypothesis: $$4^{n-1}*2*2=4^n,$$ as desired $\blacksquare$

We claim a better bound of $2^{2^n} \ge 2^{2a} = 4^n$. Consider the set of $2^n$ divisors of our desired number $$\{2^d+1 \mid p_1p_2 \ldots p_n \equiv 0 \pmod d\} = \{2^1+1, \ldots, 2^{p_1p_2 \ldots p_n}+1\}.$$ If we sort our set in increasing order, Zsigmondy tells us that each subsequent element contributes at least one more distinct prime factor not seen previously in the list (with the exception not possible as $p_i \neq 3$). Thus our desired number has at least $2^n$ prime factors, which finishes. $\blacksquare$

Prove that by Zsigmondy's theorem $2^{p_1p_2\cdots p_n}+1$ has $2^n$ prime factors.

WLOG $p_1 < p_2 <p_3 .........<p_n$ Note that $2^{p_1}+1$ is divisible by $3$ and another prime due to zsigmondy. $2^{p_1p_2}+1$ is divisible by $2^{p_1}+1$ and $2^{p_2}+1$. Now $2^{p_2}+1$ has another primitive prime factor and so does $2^{p_1p_2}+1$ so we add atleast $2$ more primes in the divisors list. Note that every time we multiply a new prime in the exponent, we do the same thing so we are adding atleast two prime factors at every turn without removing the previous ones. Hence we are increasing the number of divisors by atleast a factor of $4$ and since we started at atleast $4$ prime factors the assertion holds good.