Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2002 IMO Shortlist Problems/N3"

m (→‎Solution 2)
 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3.  Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math> \displaystyle 4^n </math> divisors.
+
Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3.  Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math>4^n </math> divisors.
  
 
== Solutions ==
 
== Solutions ==
Line 7: Line 7:
 
=== Solution 1 ===
 
=== Solution 1 ===
  
−
'''Lemma 1'''.  If <math> \displaystyle k > m </math>, then <math> \displaystyle km </math> has at least twice as many divisors as <math> \displaystyle m </math>.
+
'''Lemma 1'''.  If <math>k > m </math>, then <math>km </math> has at least twice as many divisors as <math>m </math>.
  
−
''Proof''.  For every divisor <math> \displaystyle a </math> of <math> \displaystyle m </math>, <math> \displaystyle ka </math> is clearly a divisor of <math> \displaystyle km </math>, but not <math> \displaystyle m </math>.
+
''Proof''.  For every divisor <math>a </math> of <math>m </math>, <math>ka </math> is clearly a divisor of <math>km </math>, but not <math>m </math>.
  
−
'''Lemma 2'''.  If <math> \displaystyle u </math> and <math> \displaystyle v </math> are [[relatively prime]] odd numbers, then the [[greatest common factor]] of <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math> is 3.
+
'''Lemma 2'''.  If <math>u </math> and <math>v </math> are [[relatively prime]] odd numbers, then the [[greatest common factor]] of <math>2^u + 1 </math> and <math>2^v + 1 </math> is 3.
  
−
''Proof''.  Clearly, 3 divides both <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math>.  Now, suppose that there is some <math> \displaystyle t > 3 </math> which divides both <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math>.  Then <math> 2^u \equiv 2^v \equiv -1 \pmod{t} </math>.  But this means that both <math> \displaystyle u </math> and <math> \displaystyle v </math> are divisible by half the order of 2 in mod <math> \displaystyle t </math>, contradicting our assumption that <math> \displaystyle u </math> and <math> \displaystyle v </math> are relatively prime.
+
''Proof''.  Clearly, 3 divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>.  Now, suppose that there is some <math>t > 3 </math> which divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>.  Then <math> 2^u \equiv 2^v \equiv -1 \pmod{t} </math>.  But this means that both <math>u </math> and <math>v </math> are divisible by half the order of 2 in mod <math>t </math>, contradicting our assumption that <math>u </math> and <math>v </math> are relatively prime.
  
 
We now note that since
 
We now note that since
Line 23: Line 23:
 
</center>
 
</center>
  
−
we know that <math> \displaystyle 2^{uv} + 1 </math> is divisible by <math> \displaystyle 2^u + 1</math>, and, by symmetry, <math> \displaystyle 2^v </math> also, and therefore also by <math> \displaystyle (2^u + 1)(2^v +1)/3 </math>.
+
we know that <math>2^{uv} + 1 </math> is divisible by <math>2^u + 1</math>, and, by symmetry, <math>2^v </math> also, and therefore also by <math>(2^u + 1)(2^v +1)/3 </math>.
  
−
We now prove the result by induction on <math> \displaystyle n </math>.  Our base case, <math> \displaystyle n=1 </math>, is easy, since we know that <math> \displaystyle 2^{p_1} + 1 </math> is divisible by 3, and is greater than 27.  Now, set <math> u = p_{1}\cdots p_{n-1} </math> and <math> \displaystyle v = p_n </math>.  By Lemma 2, we know that <math> \displaystyle 2^{u} + 1 </math> and <math> \displaystyle 2^{v} + 1 </math> are relatively prime; hence <math> \displaystyle (2^u +1)(2^v + 1)/3 </math> has at least <math> \displaystyle 2 \cdot 4^{n-1} </math> factors, by the inductive hypothesis.
+
We now prove the result by induction on <math>n </math>.  Our base case, <math>n=1 </math>, is easy, since we know that <math>2^{p_1} + 1 </math> is divisible by 3, and is greater than 27.  Now, set <math> u = p_{1}\cdots p_{n-1} </math> and <math>v = p_n </math>.  By Lemma 2, we know that <math>2^{u} + 1 </math> and <math>2^{v} + 1 </math> are relatively prime; hence <math>(2^u +1)(2^v + 1)/3 </math> has at least <math>2 \cdot 4^{n-1} </math> factors, by the inductive hypothesis.
  
−
We know that <math> \displaystyle (2^u +1)(2^v + 1)/3 </math> divides <math> \displaystyle 2^{uv} + 1 </math>.  We also know that <math> \displaystyle uv > 2(u+v) </math>, whence <math> \displaystyle 2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2 </math>.  Then by Lemma 1,
+
We know that <math>(2^u +1)(2^v + 1)/3 </math> divides <math>2^{uv} + 1 </math>.  We also know that <math>uv > 2(u+v) </math>, whence <math>2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2 </math>.  Then by Lemma 1,
  
 
<center>
 
<center>
Line 68: Line 68:
 
Thus <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> has at least four factors and is relatively prime to <math>2^{q} + 1 </math>, completing the induction.
 
Thus <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> has at least four factors and is relatively prime to <math>2^{q} + 1 </math>, completing the induction.
  
 +
=== Solution 3 ===
 +
We proceed by induction. Base case <math>n=1</math>. Observe that <math>3|2^{p_1}+1</math>, and since <math>p_1>3</math>, <math>2^{p_1}+1>9 \implies \frac{2^{p_{1}}+1}{3}>3</math> so <math>2^{p_1}+1</math> has at least 4 divisors.
 +
 +
Now suppose the proposition holds for <math>n=h</math>.
 +
 +
 +
lemma 1:
 +
if <math>gcd(a,b)=1</math> with <math>a</math> and <math>b</math> both being odd, then <math>gcd(2^a+1,2^b+1)=3</math>.
 +
 +
Proof:
 +
let p be a prime that divides both <math>2^a+1</math> and <math>2^b+1</math>. Then p divides both <math>2^{2a}-1</math> and <math>2^{2b}-1</math>. Since <math>2^{2a}\equiv 1</math> (mod <math>p</math>) and <math>2^{2b}\equiv 1</math> (mod <math>p</math>), <math>ord_{p}\left(2\right)</math> divides <math>2a</math> and <math>2b</math>. But, <math>gcd(a,b)=1</math>, so <math>ord_{p}\left(2\right)=2 \implies p=3</math>. Hence proven.
 +
 +
 +
 +
 +
 +
 +
lemma 2:
 +
<math>3||2^p+1</math>, with <math>p</math> being a prime greater than <math>3</math>.
 +
 +
Proof;
 +
It suffices to show that <math>9\nmid 2^p+1</math>. for <math>0\le i\le8</math>, the only solution to <math>2^i+1\equiv 0</math> (mod <math>9</math>) is <math>i=3</math>. <math>6</math> is the smallest natural <math>k</math> such that <math>2^k-1\equiv 0</math> (mod <math>9</math>). This means that if <math>2^m+1\equiv 0</math> (mod <math>9</math>), <math>m\equiv 3</math> (mod <math>6</math>), but <math>p</math> is a prime greater than <math>3</math>, so this is not possible.
 +
 +
Note that <math>\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3</math>. Let <math>m=\frac{2^{p_{n+1}}+1}{3}</math>. Note that <math>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)<3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right) \implies \left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)m<\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)</math>. So <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)mx</math>. Note that <math>gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>.
 +
 +
I will now prove <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. Note that <math>x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}</math>. We wish to prove <math>x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. Rearrange the inequality to get <math>\left(2+1\right)\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)^{2}\left(2^{p_{n+1}}+1\right)</math>. Note that <math>p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}+1>2p_{1}p_{2}\cdot\cdot\cdot p_{n}+p_{n+1}</math>, which implies the inequality. Since <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>,  <math>x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>.
 +
 +
Also, note that <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1>m \implies x>m</math>. This means <math>mx</math> has at least four factors. Note that if <math>gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>, <math>mx</math> would be relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>, which would mean <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1</math> has at least <math>4\cdot4^{h}=4^{h+1}</math> factors.
 +
 +
Assume <math>x</math> and <math>m</math> are not relatively prime. Then there exists some prime <math>q</math> such that <math>v_{q}\left(x\right)>v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)</math>. Let <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{e_{1}}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}</math>, <math>m=pD</math> and <math>x=kq_{1}^{e_{1}+f}</math>, with <math>q_1</math> being the prime in question. Note that <math>f\ge1</math>. (<math>p</math> is relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>). Then <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k</math>. Let <math>d(n)</math> be the number of divisors of <math>n</math>. Then <math>d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k\right)\ge d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\right)=\left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2</math>. Note that <math>f+1\ge 2</math>, so
 +
<math>2e_{1}+f+1\ge2\left(e_{1}+1\right) \implies \left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2\ge4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)</math>. From the inductive step <math>d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^h</math>, so <math>4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}</math>. This implies <math>d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}</math>, which completes the induction.
 +
QED
  
−
{{alternate solutions}}
 
  
 
== Resources ==
 
== Resources ==

Latest revision as of 06:38, 12 November 2019

Problem

Let $p_{1}, p_{2}, \ldots , p_{n}$ be distinct primes greater than 3. Show that $2^{p_{1}p_{2} \cdots p_{n}} + 1$ has at least $4^n$ divisors.

Solutions

Solution 1

Lemma 1. If $k > m$, then $km$ has at least twice as many divisors as $m$.

Proof. For every divisor $a$ of $m$, $ka$ is clearly a divisor of $km$, but not $m$.

Lemma 2. If $u$ and $v$ are relatively prime odd numbers, then the greatest common factor of $2^u + 1$ and $2^v + 1$ is 3.

Proof. Clearly, 3 divides both $2^u + 1$ and $2^v + 1$. Now, suppose that there is some $t > 3$ which divides both $2^u + 1$ and $2^v + 1$. Then $2^u \equiv 2^v \equiv -1 \pmod{t}$. But this means that both $u$ and $v$ are divisible by half the order of 2 in mod $t$, contradicting our assumption that $u$ and $v$ are relatively prime.

We now note that since

$2^{uv} = (2^{u} + 1) \left[ \sum_{i=0}^{v-1} (-2)^{ui} \right] \qquad \qquad$,

we know that $2^{uv} + 1$ is divisible by $2^u + 1$, and, by symmetry, $2^v$ also, and therefore also by $(2^u + 1)(2^v +1)/3$.

We now prove the result by induction on $n$. Our base case, $n=1$, is easy, since we know that $2^{p_1} + 1$ is divisible by 3, and is greater than 27. Now, set $u = p_{1}\cdots p_{n-1}$ and $v = p_n$. By Lemma 2, we know that $2^{u} + 1$ and $2^{v} + 1$ are relatively prime; hence $(2^u +1)(2^v + 1)/3$ has at least $2 \cdot 4^{n-1}$ factors, by the inductive hypothesis.

We know that $(2^u +1)(2^v + 1)/3$ divides $2^{uv} + 1$. We also know that $uv > 2(u+v)$, whence $2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2$. Then by Lemma 1,

$d(2^{uv} + 1) \ge d \left[ (2^{u}+1)(2^{v}+1)/3 \right] \ge 4^{n}$.

Q.E.D.

Solution 2

We proceed by induction. For our base case, $n = 1$, we note that $2^{p_1} +1$ is divisible by 3. Since $p_1 \ge 5$, $2^{p_1} +1$ is clearly greater than 3 and cannot be a larger power of three, since this would require $p_1 \equiv 3 \pmod{6}$. Therefore $2^{p_1} + 1$ has some other prime factor and therefore at least 4 factors overall.

Now, suppose the proposition holds for $n = k-1$. Without loss of generality, let $p_{k}$ be the minimum of $p_{1}, \ldots , p_{k}$. We shall abbreviate $q = \prod_{i=1}^{k-1}p_i$. We note the relation

$2^{qp_k} + 1 = \left( 2^q + 1 \right) \left[ \sum_{i=0}^{p_{k}-1} (-2)^{qi} \right]$.

Since $2^q + 1$ has at least $4^{k-1}$ factors, it will suffice to show that $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ is relatively prime to $2^q + 1$, and has at least four factors.

We note that in general, $\sum_{i=0}^{p_{k}-1}(-x)^{i}$ has remainder $p_k$ when divided by $x+1$. But $p_k$ cannot divide $2^q + 1$, as this would require $2^q \equiv -1 \pmod{p_k-1}$ when $q$ is relatively prime to $p_k - 1$. Hence $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ and $2^q + 1$ are relatively prime.

We now claim that $\sum_{i=0}^{p_{k}-1}(-2)^{qi}$ has at least four factors. We start by noting that in general, $\sum_{i=0}^{p_{k}-1} x^i$ divides $\sum_{i=0}^{p_{k}-1} x^{qi}$, since the roots of the former are the nonreal $p_{k}$th roots of unity and $q \perp p_{k}$.

Since clearly $\sum_{i=0}^{p_{k}-1} (-2)^{qi} > \sum_{i=0}^{p_{k}-1} (-2)^i$, it is sufficient to show that the former is not the square of the latter (i.e., that the former is either a higher power of the latter, or some other prime divides the latter, either of which implies that the former has at least four factors). But this follows from

$\begin{matrix} \sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\ & > & \left( 2^{p_{k}} \right)^2 \qquad \quad \\ & > &\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2 \end{matrix}$

Thus $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ has at least four factors and is relatively prime to $2^{q} + 1$, completing the induction.

Solution 3

We proceed by induction. Base case $n=1$. Observe that $3|2^{p_1}+1$, and since $p_1>3$, $2^{p_1}+1>9 \implies \frac{2^{p_{1}}+1}{3}>3$ so $2^{p_1}+1$ has at least 4 divisors.

Now suppose the proposition holds for $n=h$.


lemma 1: if $gcd(a,b)=1$ with $a$ and $b$ both being odd, then $gcd(2^a+1,2^b+1)=3$.

Proof: let p be a prime that divides both $2^a+1$ and $2^b+1$. Then p divides both $2^{2a}-1$ and $2^{2b}-1$. Since $2^{2a}\equiv 1$ (mod $p$) and $2^{2b}\equiv 1$ (mod $p$), $ord_{p}\left(2\right)$ divides $2a$ and $2b$. But, $gcd(a,b)=1$, so $ord_{p}\left(2\right)=2 \implies p=3$. Hence proven.




lemma 2: $3||2^p+1$, with $p$ being a prime greater than $3$.

Proof; It suffices to show that $9\nmid 2^p+1$. for $0\le i\le8$, the only solution to $2^i+1\equiv 0$ (mod $9$) is $i=3$. $6$ is the smallest natural $k$ such that $2^k-1\equiv 0$ (mod $9$). This means that if $2^m+1\equiv 0$ (mod $9$), $m\equiv 3$ (mod $6$), but $p$ is a prime greater than $3$, so this is not possible.

Note that $\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3$. Let $m=\frac{2^{p_{n+1}}+1}{3}$. Note that $\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)<3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right) \implies \left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)m<\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)$. So $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)mx$. Note that $gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1$.

I will now prove $x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$. Note that $x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}$. We wish to prove $x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$. Rearrange the inequality to get $\left(2+1\right)\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)^{2}\left(2^{p_{n+1}}+1\right)$. Note that $p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}+1>2p_{1}p_{2}\cdot\cdot\cdot p_{n}+p_{n+1}$, which implies the inequality. Since $x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$, $x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$.

Also, note that $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1>m \implies x>m$. This means $mx$ has at least four factors. Note that if $gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1$, $mx$ would be relatively prime to $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$, which would mean $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1$ has at least $4\cdot4^{h}=4^{h+1}$ factors.

Assume $x$ and $m$ are not relatively prime. Then there exists some prime $q$ such that $v_{q}\left(x\right)>v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)$. Let $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{e_{1}}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}$, $m=pD$ and $x=kq_{1}^{e_{1}+f}$, with $q_1$ being the prime in question. Note that $f\ge1$. ($p$ is relatively prime to $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$). Then $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k$. Let $d(n)$ be the number of divisors of $n$. Then $d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k\right)\ge d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\right)=\left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2$. Note that $f+1\ge 2$, so $2e_{1}+f+1\ge2\left(e_{1}+1\right) \implies \left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2\ge4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)$. From the inductive step $d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^h$, so $4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}$. This implies $d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}$, which completes the induction. QED


Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_IMO_Shortlist_Problems/N3&oldid=111275"