https://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_5&feed=atom&action=history 2000 IMO Problems/Problem 5 - Revision history 2021-07-27T19:24:16Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_5&diff=151295&oldid=prev Math31415926535: Created page with "Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$? ==Solution==..." 2021-04-10T03:45:50Z <p>Created page with &quot;Does there exist a positive integer &lt;math&gt; n&lt;/math&gt; such that &lt;math&gt; n&lt;/math&gt; has exactly 2000 prime divisors and &lt;math&gt; n&lt;/math&gt; divides &lt;math&gt; 2^n + 1&lt;/math&gt;? ==Solution==...&quot;</p> <p><b>New page</b></p><div>Does there exist a positive integer &lt;math&gt; n&lt;/math&gt; such that &lt;math&gt; n&lt;/math&gt; has exactly 2000 prime divisors and &lt;math&gt; n&lt;/math&gt; divides &lt;math&gt; 2^n + 1&lt;/math&gt;?<br /> <br /> ==Solution==<br /> Let &lt;math&gt;N=2^n+1&lt;/math&gt;. We will assume for the sake of contradiction that &lt;math&gt;n|N&lt;/math&gt;.<br /> <br /> &lt;math&gt;2^n+1 \equiv 0&lt;/math&gt; (mod &lt;math&gt;n&lt;/math&gt;) &lt;math&gt;\Rightarrow 2^n \equiv -1&lt;/math&gt; (mod &lt;math&gt;n&lt;/math&gt;). So 2 does not divide &lt;math&gt;n&lt;/math&gt;, and so &lt;math&gt;n&lt;/math&gt; is odd.<br /> <br /> Select an arbitrary prime factor of &lt;math&gt;n&lt;/math&gt; and call it &lt;math&gt;p&lt;/math&gt;. Let's represent &lt;math&gt;n&lt;/math&gt; in the form &lt;math&gt;p^am&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; is not divisible by &lt;math&gt;p&lt;/math&gt;.<br /> <br /> Note that &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; are both odd since &lt;math&gt;n&lt;/math&gt; is odd. By repeated applications of Fermat's Little Theorem:<br /> <br /> &lt;math&gt;N = 2^n+1 = 2^{p^am} + 1 = (2^{p^{a-1}m})^p + 1 \equiv 2^{p^{a-1}m} + 1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;)<br /> <br /> Continuing in this manner, and inducting on k from 1 to &lt;math&gt;a&lt;/math&gt;,<br /> <br /> &lt;math&gt;2^{p^{a-k}m}+1 \equiv (2^{p^{a-k-1}m})^p + 1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;) &lt;math&gt;\equiv 2^{p^{a-k-1}m} + 1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;)<br /> <br /> So we have &lt;math&gt;N \equiv 2^m+1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;)<br /> <br /> Since &lt;math&gt;p&lt;/math&gt; is relatively prime to &lt;math&gt;m&lt;/math&gt;, &lt;math&gt;N \equiv 1+1&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;) &lt;math&gt;\equiv 2&lt;/math&gt; (mod &lt;math&gt;p&lt;/math&gt;)<br /> <br /> Since &lt;math&gt;p&lt;/math&gt; is odd, &lt;math&gt;N&lt;/math&gt; is not divisible by &lt;math&gt;p&lt;/math&gt;. Hence &lt;math&gt;N&lt;/math&gt; is not divisible by &lt;math&gt;n&lt;/math&gt;. So we have a contradiction, and our original assumption was false, and therefore &lt;math&gt;N&lt;/math&gt; is still not divisible by &lt;math&gt;n&lt;/math&gt;.</div> Math31415926535