Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

\begin{align*}f(6007)\equiv 2008 - 2008 \equiv 0 \pmod{2003} \end{align*}

as desired.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_94&oldid=87695"