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>\begin{align*} f(6007) \equiv 6007\left\lfloor \frac{2008^{6007}}{6007} \right\rfloor \equiv 0 \pmod{2003} \tag{1} \end{align*}</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>\begin{align*} f(6007) \equiv 2008^{6007} - 6007\left\{\frac{2008^{6007}}{6007}\right\} \pmod{2003} \tag{2} \end{align*}</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 14: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.