Difference between revisions of "2008 iTest Problems/Problem 94"
(solution) |
(→Solution) |
||
Line 10: | Line 10: | ||
To do so, we claim that | To do so, we claim that | ||
− | < | + | <cmath> |
holds, and since <math>6007</math> is prime the result follows. Indeed, <math>\left\lfloor \frac{2008^{6007}}{6007} \right\rfloor = \frac{2008^{6007}}{6007} - \left\{\frac{2008^{6007}}{6007}\right\}</math>, where <math>\{x\} = x - \lfloor x \rfloor</math> denotes the fractional part of a number. So <math>(1)</math> becomes | holds, and since <math>6007</math> is prime the result follows. Indeed, <math>\left\lfloor \frac{2008^{6007}}{6007} \right\rfloor = \frac{2008^{6007}}{6007} - \left\{\frac{2008^{6007}}{6007}\right\}</math>, where <math>\{x\} = x - \lfloor x \rfloor</math> denotes the fractional part of a number. So <math>(1)</math> becomes | ||
− | < | + | <cmath> |
By [[Fermat's Little Theorem]], we have <math>2008^{2002} \equiv 1 \pmod{2003}</math>, so <math>2008^{6007} \equiv 2008^{2002} \cdot 2008 \equiv 2008 \pmod{2003}</math>. Also, <math>6007\left\{\frac{2008^{6007}}{6007}\right\}</math> is equivalent to the remainder when <math>2008^{6007}</math> is divided by <math>6007</math>, and by Fermat's Little Theorem again, we have <math>2008^{6007} \equiv 2008 \pmod{6007}</math>. Hence, equation <math>(2)</math> reduces to | By [[Fermat's Little Theorem]], we have <math>2008^{2002} \equiv 1 \pmod{2003}</math>, so <math>2008^{6007} \equiv 2008^{2002} \cdot 2008 \equiv 2008 \pmod{2003}</math>. Also, <math>6007\left\{\frac{2008^{6007}}{6007}\right\}</math> is equivalent to the remainder when <math>2008^{6007}</math> is divided by <math>6007</math>, and by Fermat's Little Theorem again, we have <math>2008^{6007} \equiv 2008 \pmod{6007}</math>. Hence, equation <math>(2)</math> reduces to | ||
− | < | + | <cmath> \begin{align*}f(6007)\equiv 2008 - 2008 \equiv 0 \pmod{2003} \end{align*}</cmath> |
− | as desired. | + | as desired. |
== See also == | == See also == | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 13:30, 7 October 2017
Problem
Find the largest prime number less than that is a divisor of some integer in the infinite sequence
Solution
The largest prime number less than is ; we claim that this is the answer. Indeed, we claim that the th term divides , where is prime (and hence relatively prime to ).
To do so, we claim that
holds, and since is prime the result follows. Indeed, , where denotes the fractional part of a number. So becomes
By Fermat's Little Theorem, we have , so . Also, is equivalent to the remainder when is divided by , and by Fermat's Little Theorem again, we have . Hence, equation reduces to
as desired.