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

 
m (alternate solutions)
Line 67: Line 67:
  
 
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> \displaystyle 2^{q} + 1 </math>, completing the induction.
 +
 +
 +
{{alternate solutions}}
  
 
== Resources ==
 
== Resources ==

Revision as of 00:31, 28 December 2006

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, $\displaystyle n = 1$, we note that $2^{p_1}$ is divisible by 3. Since $p_1 \ge 5$, $2^{p_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 $\displaystyle n = k-1$. Without loss of generality, let $\displaystyle p_{k}$ be the minimum of $\displaystyle 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 $\displaystyle 2^q + 1$ has at least $\displaystyle 4^{k-1}$ factors, it will suffice to show that $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ is relatively prime to $\displaystyle 2^q + 1$, and has at least four factors.

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

Thus $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ has at least four factors and is relatively prime to $\displaystyle 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