https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Fashboy&feedformat=atom AoPS Wiki - User contributions [en] 2021-01-27T13:45:09Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2002_IMO_Shortlist_Problems/N3&diff=111275 2002 IMO Shortlist Problems/N3 2019-11-12T10:38:59Z <p>Fashboy: </p> <hr /> <div>== Problem ==<br /> <br /> Let &lt;math&gt; p_{1}, p_{2}, \ldots , p_{n} &lt;/math&gt; be distinct primes greater than 3. Show that &lt;math&gt; 2^{p_{1}p_{2} \cdots p_{n}} + 1 &lt;/math&gt; has at least &lt;math&gt;4^n &lt;/math&gt; divisors.<br /> <br /> == Solutions ==<br /> <br /> === Solution 1 ===<br /> <br /> '''Lemma 1'''. If &lt;math&gt;k &gt; m &lt;/math&gt;, then &lt;math&gt;km &lt;/math&gt; has at least twice as many divisors as &lt;math&gt;m &lt;/math&gt;.<br /> <br /> ''Proof''. For every divisor &lt;math&gt;a &lt;/math&gt; of &lt;math&gt;m &lt;/math&gt;, &lt;math&gt;ka &lt;/math&gt; is clearly a divisor of &lt;math&gt;km &lt;/math&gt;, but not &lt;math&gt;m &lt;/math&gt;.<br /> <br /> '''Lemma 2'''. If &lt;math&gt;u &lt;/math&gt; and &lt;math&gt;v &lt;/math&gt; are [[relatively prime]] odd numbers, then the [[greatest common factor]] of &lt;math&gt;2^u + 1 &lt;/math&gt; and &lt;math&gt;2^v + 1 &lt;/math&gt; is 3.<br /> <br /> ''Proof''. Clearly, 3 divides both &lt;math&gt;2^u + 1 &lt;/math&gt; and &lt;math&gt;2^v + 1 &lt;/math&gt;. Now, suppose that there is some &lt;math&gt;t &gt; 3 &lt;/math&gt; which divides both &lt;math&gt;2^u + 1 &lt;/math&gt; and &lt;math&gt;2^v + 1 &lt;/math&gt;. Then &lt;math&gt; 2^u \equiv 2^v \equiv -1 \pmod{t} &lt;/math&gt;. But this means that both &lt;math&gt;u &lt;/math&gt; and &lt;math&gt;v &lt;/math&gt; are divisible by half the order of 2 in mod &lt;math&gt;t &lt;/math&gt;, contradicting our assumption that &lt;math&gt;u &lt;/math&gt; and &lt;math&gt;v &lt;/math&gt; are relatively prime.<br /> <br /> We now note that since<br /> <br /> &lt;center&gt;<br /> &lt;math&gt;<br /> 2^{uv} = (2^{u} + 1) \left[ \sum_{i=0}^{v-1} (-2)^{ui} \right] \qquad \qquad<br /> &lt;/math&gt;,<br /> &lt;/center&gt;<br /> <br /> we know that &lt;math&gt;2^{uv} + 1 &lt;/math&gt; is divisible by &lt;math&gt;2^u + 1&lt;/math&gt;, and, by symmetry, &lt;math&gt;2^v &lt;/math&gt; also, and therefore also by &lt;math&gt;(2^u + 1)(2^v +1)/3 &lt;/math&gt;.<br /> <br /> We now prove the result by induction on &lt;math&gt;n &lt;/math&gt;. Our base case, &lt;math&gt;n=1 &lt;/math&gt;, is easy, since we know that &lt;math&gt;2^{p_1} + 1 &lt;/math&gt; is divisible by 3, and is greater than 27. Now, set &lt;math&gt; u = p_{1}\cdots p_{n-1} &lt;/math&gt; and &lt;math&gt;v = p_n &lt;/math&gt;. By Lemma 2, we know that &lt;math&gt;2^{u} + 1 &lt;/math&gt; and &lt;math&gt;2^{v} + 1 &lt;/math&gt; are relatively prime; hence &lt;math&gt;(2^u +1)(2^v + 1)/3 &lt;/math&gt; has at least &lt;math&gt;2 \cdot 4^{n-1} &lt;/math&gt; factors, by the inductive hypothesis.<br /> <br /> We know that &lt;math&gt;(2^u +1)(2^v + 1)/3 &lt;/math&gt; divides &lt;math&gt;2^{uv} + 1 &lt;/math&gt;. We also know that &lt;math&gt;uv &gt; 2(u+v) &lt;/math&gt;, whence &lt;math&gt;2^{uv} &gt; \left[ (2^u + 1)(2^v + 1)/3 \right]^2 &lt;/math&gt;. Then by Lemma 1,<br /> <br /> &lt;center&gt;<br /> &lt;math&gt;<br /> d(2^{uv} + 1) \ge d \left[ (2^{u}+1)(2^{v}+1)/3 \right] \ge 4^{n}<br /> &lt;/math&gt;.<br /> &lt;/center&gt;<br /> Q.E.D.<br /> <br /> === Solution 2 ===<br /> <br /> We proceed by induction. For our base case, &lt;math&gt;n = 1 &lt;/math&gt;, we note that &lt;math&gt; 2^{p_1} +1 &lt;/math&gt; is divisible by 3. Since &lt;math&gt; p_1 \ge 5 &lt;/math&gt;, &lt;math&gt; 2^{p_1} +1 &lt;/math&gt; is clearly greater than 3 and cannot be a larger power of three, since this would require &lt;math&gt; p_1 \equiv 3 \pmod{6} &lt;/math&gt;. Therefore &lt;math&gt; 2^{p_1} + 1 &lt;/math&gt; has some other prime factor and therefore at least 4 factors overall.<br /> <br /> Now, suppose the proposition holds for &lt;math&gt;n = k-1 &lt;/math&gt;. Without loss of generality, let &lt;math&gt;p_{k} &lt;/math&gt; be the minimum of &lt;math&gt;p_{1}, \ldots , p_{k} &lt;/math&gt;. We shall abbreviate &lt;math&gt; q = \prod_{i=1}^{k-1}p_i &lt;/math&gt;. We note the relation<br /> <br /> &lt;center&gt;<br /> &lt;math&gt;<br /> 2^{qp_k} + 1 = \left( 2^q + 1 \right) \left[ \sum_{i=0}^{p_{k}-1} (-2)^{qi} \right]<br /> &lt;/math&gt;.<br /> &lt;/center&gt;<br /> <br /> Since &lt;math&gt;2^q + 1 &lt;/math&gt; has at least &lt;math&gt;4^{k-1}&lt;/math&gt; factors, it will suffice to show that &lt;math&gt; \sum_{i=0}^{p_{k}-1} (-2)^{qi} &lt;/math&gt; is relatively prime to &lt;math&gt;2^q + 1 &lt;/math&gt;, and has at least four factors.<br /> <br /> We note that in general, &lt;math&gt; \sum_{i=0}^{p_{k}-1}(-x)^{i} &lt;/math&gt; has remainder &lt;math&gt;p_k &lt;/math&gt; when divided by &lt;math&gt;x+1 &lt;/math&gt;. But &lt;math&gt;p_k &lt;/math&gt; cannot divide &lt;math&gt;2^q + 1 &lt;/math&gt;, as this would require &lt;math&gt;2^q \equiv -1 \pmod{p_k-1}&lt;/math&gt; when &lt;math&gt;q &lt;/math&gt; is relatively prime to &lt;math&gt;p_k - 1 &lt;/math&gt;. Hence &lt;math&gt; \sum_{i=0}^{p_{k}-1} (-2)^{qi} &lt;/math&gt; and &lt;math&gt;2^q + 1 &lt;/math&gt; are relatively prime.<br /> <br /> We now claim that &lt;math&gt; \sum_{i=0}^{p_{k}-1}(-2)^{qi} &lt;/math&gt; has at least four factors. We start by noting that in general, &lt;math&gt; \sum_{i=0}^{p_{k}-1} x^i &lt;/math&gt; divides &lt;math&gt; \sum_{i=0}^{p_{k}-1} x^{qi} &lt;/math&gt;, since the roots of the former are the nonreal &lt;math&gt;p_{k} &lt;/math&gt;th [[roots of unity]] and &lt;math&gt; q \perp p_{k} &lt;/math&gt;.<br /> <br /> Since clearly &lt;math&gt; \sum_{i=0}^{p_{k}-1} (-2)^{qi} &gt; \sum_{i=0}^{p_{k}-1} (-2)^i &lt;/math&gt;, 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<br /> <br /> &lt;center&gt;<br /> &lt;math&gt;<br /> \begin{matrix}<br /> \sum_{i=0}^{p_{k}-1} (-2)^{qi} &amp; &gt; &amp; 2^{q(p_{k}-1) - 1} \quad \\<br /> &amp; &gt; &amp; \left( 2^{p_{k}} \right)^2 \qquad \quad \\<br /> &amp; &gt; &amp;\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2<br /> \end{matrix}<br /> &lt;/math&gt;<br /> &lt;/center&gt;<br /> <br /> Thus &lt;math&gt; \sum_{i=0}^{p_{k}-1} (-2)^{qi} &lt;/math&gt; has at least four factors and is relatively prime to &lt;math&gt;2^{q} + 1 &lt;/math&gt;, completing the induction.<br /> <br /> === Solution 3 ===<br /> We proceed by induction. Base case &lt;math&gt;n=1&lt;/math&gt;. Observe that &lt;math&gt;3|2^{p_1}+1&lt;/math&gt;, and since &lt;math&gt;p_1&gt;3&lt;/math&gt;, &lt;math&gt;2^{p_1}+1&gt;9 \implies \frac{2^{p_{1}}+1}{3}&gt;3&lt;/math&gt; so &lt;math&gt;2^{p_1}+1&lt;/math&gt; has at least 4 divisors.<br /> <br /> Now suppose the proposition holds for &lt;math&gt;n=h&lt;/math&gt;. <br /> <br /> <br /> lemma 1:<br /> if &lt;math&gt;gcd(a,b)=1&lt;/math&gt; with &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; both being odd, then &lt;math&gt;gcd(2^a+1,2^b+1)=3&lt;/math&gt;. <br /> <br /> Proof:<br /> let p be a prime that divides both &lt;math&gt;2^a+1&lt;/math&gt; and &lt;math&gt;2^b+1&lt;/math&gt;. Then p divides both &lt;math&gt;2^{2a}-1&lt;/math&gt; and &lt;math&gt;2^{2b}-1&lt;/math&gt;. Since &lt;math&gt;2^{2a}\equiv 1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;) and &lt;math&gt;2^{2b}\equiv 1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;), &lt;math&gt;ord_{p}\left(2\right)&lt;/math&gt; divides &lt;math&gt;2a&lt;/math&gt; and &lt;math&gt;2b&lt;/math&gt;. But, &lt;math&gt;gcd(a,b)=1&lt;/math&gt;, so &lt;math&gt;ord_{p}\left(2\right)=2 \implies p=3&lt;/math&gt;. Hence proven.<br /> <br /> <br /> <br /> <br /> <br /> <br /> lemma 2:<br /> &lt;math&gt;3||2^p+1&lt;/math&gt;, with &lt;math&gt;p&lt;/math&gt; being a prime greater than &lt;math&gt;3&lt;/math&gt;.<br /> <br /> Proof;<br /> It suffices to show that &lt;math&gt;9\nmid 2^p+1&lt;/math&gt;. for &lt;math&gt;0\le i\le8&lt;/math&gt;, the only solution to &lt;math&gt;2^i+1\equiv 0&lt;/math&gt; (mod &lt;math&gt;9&lt;/math&gt;) is &lt;math&gt;i=3&lt;/math&gt;. &lt;math&gt;6&lt;/math&gt; is the smallest natural &lt;math&gt;k&lt;/math&gt; such that &lt;math&gt;2^k-1\equiv 0&lt;/math&gt; (mod &lt;math&gt;9&lt;/math&gt;). This means that if &lt;math&gt;2^m+1\equiv 0&lt;/math&gt; (mod &lt;math&gt;9&lt;/math&gt;), &lt;math&gt;m\equiv 3&lt;/math&gt; (mod &lt;math&gt;6&lt;/math&gt;), but &lt;math&gt;p&lt;/math&gt; is a prime greater than &lt;math&gt;3&lt;/math&gt;, so this is not possible.<br /> <br /> Note that &lt;math&gt;\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3&lt;/math&gt;. Let &lt;math&gt;m=\frac{2^{p_{n+1}}+1}{3}&lt;/math&gt;. Note that &lt;math&gt;\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)&lt;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&lt;\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)&lt;/math&gt;. So &lt;math&gt;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&lt;/math&gt;. Note that &lt;math&gt;gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1&lt;/math&gt;. <br /> <br /> I will now prove &lt;math&gt;x&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;. Note that &lt;math&gt;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)}&lt;/math&gt;. We wish to prove &lt;math&gt;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)}&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;. Rearrange the inequality to get &lt;math&gt;\left(2+1\right)\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)&gt;\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)^{2}\left(2^{p_{n+1}}+1\right)&lt;/math&gt;. Note that &lt;math&gt;p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}+1&gt;2p_{1}p_{2}\cdot\cdot\cdot p_{n}+p_{n+1}&lt;/math&gt;, which implies the inequality. Since &lt;math&gt;x&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;, &lt;math&gt;x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;.<br /> <br /> Also, note that &lt;math&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&gt;m \implies x&gt;m&lt;/math&gt;. This means &lt;math&gt;mx&lt;/math&gt; has at least four factors. Note that if &lt;math&gt;gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1&lt;/math&gt;, &lt;math&gt;mx&lt;/math&gt; would be relatively prime to &lt;math&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;, which would mean &lt;math&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1&lt;/math&gt; has at least &lt;math&gt;4\cdot4^{h}=4^{h+1}&lt;/math&gt; factors.<br /> <br /> Assume &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; are not relatively prime. Then there exists some prime &lt;math&gt;q&lt;/math&gt; such that &lt;math&gt;v_{q}\left(x\right)&gt;v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)&lt;/math&gt;. Let &lt;math&gt;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}}&lt;/math&gt;, &lt;math&gt;m=pD&lt;/math&gt; and &lt;math&gt;x=kq_{1}^{e_{1}+f}&lt;/math&gt;, with &lt;math&gt;q_1&lt;/math&gt; being the prime in question. Note that &lt;math&gt;f\ge1&lt;/math&gt;. (&lt;math&gt;p&lt;/math&gt; is relatively prime to &lt;math&gt;2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1&lt;/math&gt;). Then &lt;math&gt;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&lt;/math&gt;. Let &lt;math&gt;d(n)&lt;/math&gt; be the number of divisors of &lt;math&gt;n&lt;/math&gt;. Then &lt;math&gt;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&lt;/math&gt;. Note that &lt;math&gt;f+1\ge 2&lt;/math&gt;, so <br /> &lt;math&gt;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)&lt;/math&gt;. From the inductive step &lt;math&gt;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&lt;/math&gt;, so &lt;math&gt;4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}&lt;/math&gt;. This implies &lt;math&gt;d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}&lt;/math&gt;, which completes the induction. <br /> QED<br /> <br /> <br /> == Resources ==<br /> <br /> * [[2002 IMO Shortlist Problems]]<br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=17326 Discussion on AoPS/MathLinks]<br /> <br /> <br /> [[Category:Olympiad Number Theory Problems]]</div> Fashboy