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

m (alternate solutions) |
|||

(One intermediate revision by one other user not shown) | |||

Line 1: | Line 1: | ||

== Problem == | == Problem == | ||

− | Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3. Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math> | + | Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3. Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math>4^n </math> divisors. |

== Solutions == | == Solutions == | ||

Line 7: | Line 7: | ||

=== Solution 1 === | === Solution 1 === | ||

− | '''Lemma 1'''. If <math> | + | '''Lemma 1'''. If <math>k > m </math>, then <math>km </math> has at least twice as many divisors as <math>m </math>. |

− | ''Proof''. For every divisor <math> | + | ''Proof''. For every divisor <math>a </math> of <math>m </math>, <math>ka </math> is clearly a divisor of <math>km </math>, but not <math>m </math>. |

− | '''Lemma 2'''. If <math> | + | '''Lemma 2'''. If <math>u </math> and <math>v </math> are [[relatively prime]] odd numbers, then the [[greatest common factor]] of <math>2^u + 1 </math> and <math>2^v + 1 </math> is 3. |

− | ''Proof''. Clearly, 3 divides both <math> | + | ''Proof''. Clearly, 3 divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>. Now, suppose that there is some <math>t > 3 </math> which divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>. Then <math> 2^u \equiv 2^v \equiv -1 \pmod{t} </math>. But this means that both <math>u </math> and <math>v </math> are divisible by half the order of 2 in mod <math>t </math>, contradicting our assumption that <math>u </math> and <math>v </math> are relatively prime. |

We now note that since | We now note that since | ||

Line 23: | Line 23: | ||

</center> | </center> | ||

− | we know that <math> | + | we know that <math>2^{uv} + 1 </math> is divisible by <math>2^u + 1</math>, and, by symmetry, <math>2^v </math> also, and therefore also by <math>(2^u + 1)(2^v +1)/3 </math>. |

− | We now prove the result by induction on <math> | + | We now prove the result by induction on <math>n </math>. Our base case, <math>n=1 </math>, is easy, since we know that <math>2^{p_1} + 1 </math> is divisible by 3, and is greater than 27. Now, set <math> u = p_{1}\cdots p_{n-1} </math> and <math>v = p_n </math>. By Lemma 2, we know that <math>2^{u} + 1 </math> and <math>2^{v} + 1 </math> are relatively prime; hence <math>(2^u +1)(2^v + 1)/3 </math> has at least <math>2 \cdot 4^{n-1} </math> factors, by the inductive hypothesis. |

− | We know that <math> | + | We know that <math>(2^u +1)(2^v + 1)/3 </math> divides <math>2^{uv} + 1 </math>. We also know that <math>uv > 2(u+v) </math>, whence <math>2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2 </math>. Then by Lemma 1, |

<center> | <center> | ||

Line 38: | Line 38: | ||

=== Solution 2 === | === Solution 2 === | ||

− | We proceed by induction. For our base case, <math> | + | 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> | + | 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> | <center> | ||

Line 48: | Line 48: | ||

</center> | </center> | ||

− | Since <math> | + | 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> | + | 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> | + | 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 | 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> | <math> | ||

\begin{matrix} | \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( 2^{p_{k}} \right)^2 \qquad \quad \\ | ||

− | & > & | + | & > &\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2 |

\end{matrix} | \end{matrix} | ||

</math> | </math> | ||

</center> | </center> | ||

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

+ | === Solution 3 === | ||

+ | We proceed by induction. Base case <math>n=1</math>. Observe that <math>3|2^{p_1}+1</math>, and since <math>p_1>3</math>, <math>2^{p_1}+1>9 \implies \frac{2^{p_{1}}+1}{3}>3</math> so <math>2^{p_1}+1</math> has at least 4 divisors. | ||

+ | |||

+ | Now suppose the proposition holds for <math>n=h</math>. | ||

+ | |||

+ | |||

+ | lemma 1: | ||

+ | if <math>gcd(a,b)=1</math> with <math>a</math> and <math>b</math> both being odd, then <math>gcd(2^a+1,2^b+1)=3</math>. | ||

+ | |||

+ | Proof: | ||

+ | let p be a prime that divides both <math>2^a+1</math> and <math>2^b+1</math>. Then p divides both <math>2^{2a}-1</math> and <math>2^{2b}-1</math>. Since <math>2^{2a}\equiv 1</math> (mod <math>p</math>) and <math>2^{2b}\equiv 1</math> (mod <math>p</math>), <math>ord_{p}\left(2\right)</math> divides <math>2a</math> and <math>2b</math>. But, <math>gcd(a,b)=1</math>, so <math>ord_{p}\left(2\right)=2 \implies p=3</math>. Hence proven. | ||

+ | |||

+ | |||

+ | |||

+ | |||

+ | |||

+ | |||

+ | lemma 2: | ||

+ | <math>3||2^p+1</math>, with <math>p</math> being a prime greater than <math>3</math>. | ||

+ | |||

+ | Proof; | ||

+ | It suffices to show that <math>9\nmid 2^p+1</math>. for <math>0\le i\le8</math>, the only solution to <math>2^i+1\equiv 0</math> (mod <math>9</math>) is <math>i=3</math>. <math>6</math> is the smallest natural <math>k</math> such that <math>2^k-1\equiv 0</math> (mod <math>9</math>). This means that if <math>2^m+1\equiv 0</math> (mod <math>9</math>), <math>m\equiv 3</math> (mod <math>6</math>), but <math>p</math> is a prime greater than <math>3</math>, so this is not possible. | ||

+ | |||

+ | Note that <math>\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3</math>. Let <math>m=\frac{2^{p_{n+1}}+1}{3}</math>. Note that <math>\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)</math>. So <math>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</math>. Note that <math>gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>. | ||

+ | |||

+ | I will now prove <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. Note that <math>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)}</math>. We wish to prove <math>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</math>. Rearrange the inequality to get <math>\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)</math>. Note that <math>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}</math>, which implies the inequality. Since <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>, <math>x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. | ||

+ | |||

+ | Also, note that <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1>m \implies x>m</math>. This means <math>mx</math> has at least four factors. Note that if <math>gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>, <math>mx</math> would be relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>, which would mean <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1</math> has at least <math>4\cdot4^{h}=4^{h+1}</math> factors. | ||

+ | |||

+ | Assume <math>x</math> and <math>m</math> are not relatively prime. Then there exists some prime <math>q</math> such that <math>v_{q}\left(x\right)>v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)</math>. Let <math>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}}</math>, <math>m=pD</math> and <math>x=kq_{1}^{e_{1}+f}</math>, with <math>q_1</math> being the prime in question. Note that <math>f\ge1</math>. (<math>p</math> is relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>). Then <math>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</math>. Let <math>d(n)</math> be the number of divisors of <math>n</math>. Then <math>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</math>. Note that <math>f+1\ge 2</math>, so | ||

+ | <math>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)</math>. From the inductive step <math>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</math>, so <math>4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}</math>. This implies <math>d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}</math>, which completes the induction. | ||

+ | QED | ||

− | |||

== Resources == | == Resources == |

## Latest revision as of 05:38, 12 November 2019

## Problem

Let be distinct primes greater than 3. Show that has at least divisors.

## Solutions

### Solution 1

**Lemma 1**. If , then has at least twice as many divisors as .

*Proof*. For every divisor of , is clearly a divisor of , but not .

**Lemma 2**. If and are relatively prime odd numbers, then the greatest common factor of and is 3.

*Proof*. Clearly, 3 divides both and . Now, suppose that there is some which divides both and . Then . But this means that both and are divisible by half the order of 2 in mod , contradicting our assumption that and are relatively prime.

We now note that since

,

we know that is divisible by , and, by symmetry, also, and therefore also by .

We now prove the result by induction on . Our base case, , is easy, since we know that is divisible by 3, and is greater than 27. Now, set and . By Lemma 2, we know that and are relatively prime; hence has at least factors, by the inductive hypothesis.

We know that divides . We also know that , whence . Then by Lemma 1,

.

Q.E.D.

### Solution 2

We proceed by induction. For our base case, , we note that is divisible by 3. Since , is clearly greater than 3 and cannot be a larger power of three, since this would require . Therefore has some other prime factor and therefore at least 4 factors overall.

Now, suppose the proposition holds for . Without loss of generality, let be the minimum of . We shall abbreviate . We note the relation

.

Since has at least factors, it will suffice to show that is relatively prime to , and has at least four factors.

We note that in general, has remainder when divided by . But cannot divide , as this would require when is relatively prime to . Hence and are relatively prime.

We now claim that has at least four factors. We start by noting that in general, divides , since the roots of the former are the nonreal th roots of unity and .

Since clearly , 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

Thus has at least four factors and is relatively prime to , completing the induction.

### Solution 3

We proceed by induction. Base case . Observe that , and since , so has at least 4 divisors.

Now suppose the proposition holds for .

lemma 1:
if with and both being odd, then .

Proof: let p be a prime that divides both and . Then p divides both and . Since (mod ) and (mod ), divides and . But, , so . Hence proven.

lemma 2:
, with being a prime greater than .

Proof; It suffices to show that . for , the only solution to (mod ) is . is the smallest natural such that (mod ). This means that if (mod ), (mod ), but is a prime greater than , so this is not possible.

Note that . Let . Note that . So . Note that .

I will now prove . Note that . We wish to prove . Rearrange the inequality to get . Note that , which implies the inequality. Since , .

Also, note that . This means has at least four factors. Note that if , would be relatively prime to , which would mean has at least factors.

Assume and are not relatively prime. Then there exists some prime such that . Let , and , with being the prime in question. Note that . ( is relatively prime to ). Then . Let be the number of divisors of . Then . Note that , so . From the inductive step , so . This implies , which completes the induction. QED