Difference between revisions of "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