https://artofproblemsolving.com/wiki/index.php?title=2007_Indonesia_MO_Problems/Problem_2&feed=atom&action=history 2007 Indonesia MO Problems/Problem 2 - Revision history 2021-04-15T01:44:21Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2007_Indonesia_MO_Problems/Problem_2&diff=119384&oldid=prev Rockmanex3: Solution to Problem 2 -- LaTeXing this took a long time 2020-03-14T19:10:02Z <p>Solution to Problem 2 -- LaTeXing this took a long time</p> <p><b>New page</b></p><div>==Problem==<br /> <br /> For every positive integer &lt;math&gt; n&lt;/math&gt;, &lt;math&gt; b(n)&lt;/math&gt; denote the number of positive divisors of &lt;math&gt; n&lt;/math&gt; and &lt;math&gt; p(n)&lt;/math&gt; denote the sum of all positive divisors of &lt;math&gt; n&lt;/math&gt;. For example, &lt;math&gt; b(14)=4&lt;/math&gt; and &lt;math&gt; p(14)=24&lt;/math&gt;. Let &lt;math&gt; k&lt;/math&gt; be a positive integer greater than &lt;math&gt; 1&lt;/math&gt;.<br /> <br /> (a) Prove that there are infinitely many positive integers &lt;math&gt; n&lt;/math&gt; which satisfy &lt;math&gt; b(n)=k^2-k+1&lt;/math&gt;.<br /> <br /> (b) Prove that there are finitely many positive integers &lt;math&gt; n&lt;/math&gt; which satisfy &lt;math&gt; p(n)=k^2-k+1&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> For both parts, let &lt;math&gt;n = \prod_{i=1}^\infty {p_i}^{q_i}&lt;/math&gt;, where &lt;math&gt;p_i&lt;/math&gt; is a prime number and &lt;math&gt;q_i&lt;/math&gt; is a nonnegative integer. For given value &lt;math&gt;n&lt;/math&gt;, we know that &lt;math&gt;b(n) = \prod_{i=1}^\infty (q_i + 1)&lt;/math&gt; and &lt;math&gt;p(n) = \prod_{i=1}^\infty (\sum_{j=0}^{q_i} p_i^j)&lt;/math&gt;.<br /> <br /> &lt;br&gt;<br /> Because the value of &lt;math&gt;b(n)&lt;/math&gt; is only affected by the values of &lt;math&gt;q_i&lt;/math&gt;, one can change the value of &lt;math&gt;p_i&lt;/math&gt; and still have the same value of &lt;math&gt;b(n)&lt;/math&gt;. Since there are an infinite number of primes, there would be an infinite values of &lt;math&gt;n&lt;/math&gt; that would equal a set value &lt;math&gt;b(n)&lt;/math&gt;.<br /> <br /> &lt;br&gt;<br /> As for the value of &lt;math&gt;p(n)&lt;/math&gt;, note that for positive integers &lt;math&gt;a, b&lt;/math&gt; where &lt;math&gt;a &gt; b&lt;/math&gt;, we have &lt;math&gt;\sum_{j=0}^{a} p_i^j &gt; \sum_{j=0}^{b} p_i^j&lt;/math&gt;. Thus, because &lt;math&gt;\sum_{j=0}^{q_i} p_i^j &gt; p_i&lt;/math&gt; whenever &lt;math&gt;q_i \ge 1&lt;/math&gt;, if &lt;math&gt;p_i &gt; k^2 - k + 1&lt;/math&gt;, then we must have &lt;math&gt;q_i = 0&lt;/math&gt;, making &lt;math&gt;{p_i}^{q_i} = 0&lt;/math&gt;.<br /> <br /> &lt;br&gt;<br /> Therefore, there are only a limited number of primes &lt;math&gt;p_i&lt;/math&gt; that can be a factor of &lt;math&gt;n&lt;/math&gt;, and for a prime &lt;math&gt;p_i&lt;/math&gt; that is a factor of &lt;math&gt;n&lt;/math&gt;, there is an upper bound of the value of &lt;math&gt;q_i&lt;/math&gt;. Because there are a limited number of possible values of &lt;math&gt;p_i &gt; 1&lt;/math&gt; and &lt;math&gt;q_i&lt;/math&gt;, there are only a finite values of &lt;math&gt;n&lt;/math&gt; where &lt;math&gt;p(n) = k^2 - k + 1&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2007|num-b=1|num-a=3}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> Rockmanex3