2008 iTest Problems/Problem 94

From AoPSWiki

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

$\begin{align*} f(6007) \equiv 6007\left\lfloor \frac{2008^{6007}}{6007} \right\rfloor \equiv 0 \pmod{2003} \tag{1} \end{align*}$

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

$\begin{align*} f(6007) \equiv 2008^{6007} - 6007\left\{\frac{2008^{6007}}{6007}\right\} \pmod{2003} \tag{2} \end{align*}$

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) \begin{align*} 2008 - 2008 \equiv 0 \pmod{2003} \end{align*}$

as desired.

Personal tools

Navigation

Search

Toolbox

2008 iTest Problems/Problem 94

From AoPSWiki

Problem

Solution

See also