2008 iTest Problems/Problem 94

Revision as of 15:41, 16 September 2008 by Azjps (talk | contribs) (solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Find the largest prime number less than $2008$ that is a divisor of some integer in the infinite sequence

\[\left\lfloor \frac{2008}{1} \right\rfloor, \left\lfloor \frac{2008^2}{2} \right\rfloor, \left\lfloor \frac{2008^3}{3}\right\rfloor, \left\lfloor \frac{2008^4}{4} \right\rfloor, \cdots\]

Solution

The largest prime number less than $2008$ is $2003$; we claim that this is the answer. Indeed, we claim that the $6007$th term divides $2003$, where $6007$ is prime (and hence relatively prime to $2003$).

To do so, we claim that

$(1)f(6007)60072008600760070(mod2003)$ (Error compiling LaTeX. Unknown error_msg)

holds, and since $6007$ is prime the result follows. Indeed, $\left\lfloor \frac{2008^{6007}}{6007} \right\rfloor = \frac{2008^{6007}}{6007} - \left\{\frac{2008^{6007}}{6007}\right\}$, where $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of a number. So $(1)$ becomes

$(2)f(6007)200860076007{200860076007}(mod2003)$ (Error compiling LaTeX. Unknown error_msg)

By Fermat's Little Theorem, we have $2008^{2002} \equiv 1 \pmod{2003}$, so $2008^{6007} \equiv 2008^{2002} \cdot 2008 \equiv 2008 \pmod{2003}$. Also, $6007\left\{\frac{2008^{6007}}{6007}\right\}$ is equivalent to the remainder when $2008^{6007}$ is divided by $6007$, and by Fermat's Little Theorem again, we have $2008^{6007} \equiv 2008 \pmod{6007}$. Hence, equation $(2)$ reduces to

$f(6007) 200820080(mod2003)$ (Error compiling LaTeX. Unknown error_msg)

as desired.

See also