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 $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

Page

Toolbox

Search