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

m (alternate solutions) |
m (→Solution 2) |
||

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

## Revision as of 04:29, 26 August 2011

## 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.

*Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.*