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

Revision as of 04: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

@@ Line 38: / Line 38: @@
 === 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>
@@ Line 48: / Line 48: @@
 </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
@@ Line 59: / Line 59: @@
 <math>
 \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 \\
-& > & \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}
 </math>
 </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.

Page

Toolbox

Search