https://artofproblemsolving.com/wiki/index.php?title=2006_iTest_Problems/Problem_28&feed=atom&action=history 2006 iTest Problems/Problem 28 - Revision history 2022-05-22T10:53:49Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2006_iTest_Problems/Problem_28&diff=99239&oldid=prev Rockmanex3: Solution to Problem 28 -- Primes of Nines 2018-12-03T01:20:27Z <p>Solution to Problem 28 -- Primes of Nines</p> <p><b>New page</b></p><div>==Problem==<br /> <br /> The largest prime factor of &lt;math&gt;999999999999&lt;/math&gt; is greater than &lt;math&gt;2006&lt;/math&gt;. Determine the remainder obtained when this prime factor is divided by &lt;math&gt;2006&lt;/math&gt;.<br /> <br /> ==Solution==<br /> <br /> Note that &lt;math&gt;999999999999 = 10^{12} - 1&lt;/math&gt;. This expression can be factored with difference of squares and sum/difference of cubes.<br /> &lt;cmath&gt;\begin{align*}<br /> 10^{12} - 1 &amp;= (10^6 + 1)(10^6 - 1) \\<br /> &amp;= (10^2 + 1)(10^4 - 10^2 + 1)(10^3 - 1)(10^3 + 1)<br /> \end{align*}&lt;/cmath&gt;<br /> Note that since &lt;math&gt;10^3 - 1, 10^3 + 1, 10^2 + 1&lt;/math&gt; are all less than &lt;math&gt;2006&lt;/math&gt;, none of them are the wanted factors. The only option left is &lt;math&gt;10^4 - 10^2 + 1 = 9901&lt;/math&gt;. By doing a prime check (or noting that if &lt;math&gt;9901&lt;/math&gt; has factors larger than 5, then the largest prime factor of the original number can not be greater than &lt;math&gt;2006&lt;/math&gt;), we confirm that &lt;math&gt;9901&lt;/math&gt; is the largest prime factor of &lt;math&gt;999999999999&lt;/math&gt;. The remainder when &lt;math&gt;9901&lt;/math&gt; is divided by &lt;math&gt;2006&lt;/math&gt; is &lt;math&gt;\boxed{1877}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{iTest box|year=2006|num-b=27|num-a=29|ver=[[2006 iTest Problems/Problem U1|U1]] '''•''' [[2006 iTest Problems/Problem U2|U2]] '''•''' [[2006 iTest Problems/Problem U3|U3]] '''•''' [[2006 iTest Problems/Problem U4|U4]] '''•''' [[2006 iTest Problems/Problem U5|U5]] '''•''' [[2006 iTest Problems/Problem U6|U6]] '''•''' [[2006 iTest Problems/Problem U7|U7]] '''•''' [[2006 iTest Problems/Problem U8|U8]] '''•''' [[2006 iTest Problems/Problem U9|U9]] '''•''' [[2006 iTest Problems/Problem U10|U10]]}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> Rockmanex3