2002 IMO Shortlist Problems/N3

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

Page

Toolbox

Search