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

m (alternate solutions)
m (Solution 2)
Line 38: Line 38:
 
=== Solution 2 ===
 
=== Solution 2 ===
  
We proceed by induction.  For our base case, <math> \displaystyle n = 1 </math>, we note that <math> 2^{p_1} </math> is divisible by 3.  Since <math> p_1 \ge 5 </math>, <math> 2^{p_1} </math> is clearly greater than 3 and cannot be a larger power of three, since this would require <math> p_1 \equiv 3 \pmod{6} </math>.  Therefore <math> 2^{p_1} + 1 </math> has some other prime factor and therefore at least 4 factors overall.
+
We proceed by induction.  For our base case, <math>n = 1 </math>, we note that <math> 2^{p_1} +1 </math> is divisible by 3.  Since <math> p_1 \ge 5 </math>, <math> 2^{p_1} +1 </math> is clearly greater than 3 and cannot be a larger power of three, since this would require <math> p_1 \equiv 3 \pmod{6} </math>.  Therefore <math> 2^{p_1} + 1 </math> has some other prime factor and therefore at least 4 factors overall.
  
Now, suppose the proposition holds for <math> \displaystyle n = k-1 </math>.  Without loss of generality, let <math> \displaystyle p_{k} </math> be the minimum of <math> \displaystyle p_{1}, \ldots , p_{k} </math>.  We shall abbreviate <math> q = \prod_{i=1}^{k-1}p_i </math>.  We note the relation
+
Now, suppose the proposition holds for <math>n = k-1 </math>.  Without loss of generality, let <math>p_{k} </math> be the minimum of <math>p_{1}, \ldots , p_{k} </math>.  We shall abbreviate <math> q = \prod_{i=1}^{k-1}p_i </math>.  We note the relation
  
 
<center>
 
<center>
Line 48: Line 48:
 
</center>
 
</center>
  
Since <math> \displaystyle 2^q + 1 </math> has at least <math> \displaystyle 4^{k-1}</math> factors, it will suffice to show that <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> is relatively prime to <math> \displaystyle 2^q + 1 </math>, and has at least four factors.
+
Since <math>2^q + 1 </math> has at least <math>4^{k-1}</math> factors, it will suffice to show that <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> is relatively prime to <math>2^q + 1 </math>, and has at least four factors.
  
We note that in general, <math> \sum_{i=0}^{p_{k}-1}(-x)^{i} </math> has remainder <math> \displaystyle p_k </math> when divided by <math> \displaystyle x+1 </math>.  But <math> \displaystyle p_k </math> cannot divide <math> \displaystyle 2^q + 1 </math>, as this would require <math> \displaystyle 2^q \equiv -1 \pmod{p_k-1}</math> when <math> \displaystyle q </math> is relatively prime to <math> \displaystyle p_k - 1 </math>.  Hence <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> and <math> \displaystyle 2^q + 1 </math> are relatively prime.
+
We note that in general, <math> \sum_{i=0}^{p_{k}-1}(-x)^{i} </math> has remainder <math>p_k </math> when divided by <math>x+1 </math>.  But <math>p_k </math> cannot divide <math>2^q + 1 </math>, as this would require <math>2^q \equiv -1 \pmod{p_k-1}</math> when <math>q </math> is relatively prime to <math>p_k - 1 </math>.  Hence <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> and <math>2^q + 1 </math> are relatively prime.
  
We now claim that <math> \sum_{i=0}^{p_{k}-1}(-2)^{qi} </math> has at least four factors.  We start by noting that in general, <math> \sum_{i=0}^{p_{k}-1} x^i </math> divides <math> \sum_{i=0}^{p_{k}-1} x^{qi} </math>, since the roots of the former are the nonreal <math> \displaystyle p_{k} </math>th [[roots of unity]] and <math> q \perp p_{k} </math>.
+
We now claim that <math> \sum_{i=0}^{p_{k}-1}(-2)^{qi} </math> has at least four factors.  We start by noting that in general, <math> \sum_{i=0}^{p_{k}-1} x^i </math> divides <math> \sum_{i=0}^{p_{k}-1} x^{qi} </math>, since the roots of the former are the nonreal <math>p_{k} </math>th [[roots of unity]] and <math> q \perp p_{k} </math>.
  
 
Since clearly <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} > \sum_{i=0}^{p_{k}-1} (-2)^i </math>, 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
 
Since clearly <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} > \sum_{i=0}^{p_{k}-1} (-2)^i </math>, 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
Line 59: Line 59:
 
<math>
 
<math>
 
\begin{matrix}
 
\begin{matrix}
\displaystyle \sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\
+
\sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\
 
& > & \left( 2^{p_{k}} \right)^2 \qquad \quad \\
 
& > & \left( 2^{p_{k}} \right)^2 \qquad \quad \\
& > & \displaystyle \left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2
+
& > &\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2
 
\end{matrix}
 
\end{matrix}
 
</math>
 
</math>
 
</center>
 
</center>
  
Thus <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> has at least four factors and is relatively prime to <math> \displaystyle 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.
  
  

Revision as of 05:29, 26 August 2011

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 $\displaystyle 4^n$ divisors.

Solutions

Solution 1

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

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

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

Proof. Clearly, 3 divides both $\displaystyle 2^u + 1$ and $\displaystyle 2^v + 1$. Now, suppose that there is some $\displaystyle t > 3$ which divides both $\displaystyle 2^u + 1$ and $\displaystyle 2^v + 1$. Then $2^u \equiv 2^v \equiv -1 \pmod{t}$. But this means that both $\displaystyle u$ and $\displaystyle v$ are divisible by half the order of 2 in mod $\displaystyle t$, contradicting our assumption that $\displaystyle u$ and $\displaystyle 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 $\displaystyle 2^{uv} + 1$ is divisible by $\displaystyle 2^u + 1$, and, by symmetry, $\displaystyle 2^v$ also, and therefore also by $\displaystyle (2^u + 1)(2^v +1)/3$.

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

We know that $\displaystyle (2^u +1)(2^v + 1)/3$ divides $\displaystyle 2^{uv} + 1$. We also know that $\displaystyle uv > 2(u+v)$, whence $\displaystyle 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.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources