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

2019 AMC 10C Problems/Problem 25

Problem

Let $N$ be the least positive integer $x$ such that $\lfloor \frac{x^{8}}{x-1} \rfloor$ is a multiple of 10000. Find the sum of the digits of $N$. (Note: $\left\lfloor x \right\rfloor$ denotes the greatest integer less than or equal to $x$. )


$\textbf{(A)}\ 9 \qquad\textbf{(B)}\ 11 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 24 \qquad\textbf{(E)}\ 36$

Solution

We have $\left\lfloor \frac{x^8}{x-1}\right\rfloor = (1+x)(1+x^2)(1+x^4)$ so we want to solve $(1+x)(1+x^2)(1+x^4) \equiv 0 \pmod{16}$ and $0 \pmod{625}$.

Solving modulo 16 is fairly simple; the solutions are $x \equiv 3,7,11,15 \pmod{16}$ (or more compactly, $x \equiv 3 \pmod{4}$).

To solve modulo 625, observe that at most one of $1+x$, $1+x^2$, and $1+x^4$ can be divisible by 5. The case $1+x \equiv 0 \pmod{625}$ gives $x \equiv 624 \pmod{625}$. The case $1+x^4 \equiv 0 \mod{625}$ gives no solutions as $x^4 \equiv 0,1 \pmod{5}$ by FLT. Thus we want to solve $1+x^2 \equiv 0 \pmod{625}$.

Note that $x^2 + 1 \equiv 0 \pmod{625}$ implies $x \equiv 2,3 \pmod{5}$. As $x$ is a solution iff $-x$ is a solution, we can assume w.l.o.g. that $x \equiv 2 \pmod{5}$. Then $x = 5k+2$, and plugging in gives $25k^2 + 20k + 5 \equiv 0 \pmod{625} \iff 5k^2 + 4k + 1 \equiv 0 \pmod{125}$.

Taking the LHS mod 5 again, we see $k\equiv 1 \pmod{5}$, so $x \equiv 7 \pmod{25}$, so we may let $x = 25m+7$. Using the same method, we have $(25m+7)^2 + 1 = 625m^2 + 350m + 50 \equiv 0 \pmod{625} \implies 350m + 50 \equiv 0 \pmod{625} \implies 14m + 2 \equiv 0 \pmod{25}$. The solution is $m \equiv 7 \pmod{25}$, so $x = 25(25q+7)+7 \equiv 182 \pmod{625}$. Thus the solutions are $x \equiv 182, 443 \pmod{625}$.

So the solutions mod 16 and 625 are $x \equiv 3,7,11,15 \pmod{16}$, and $x \equiv 182, 443, 624 \pmod{625}$. By CRT, each combination gives us a solution mod 10000. Observing that $443 \equiv 11 \pmod{16}$ immediately gives us the minimum solution, so $N=443$ and $4+4+3 = \boxed{11}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10C_Problems/Problem_25&oldid=120803"