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}$ .

Page

Toolbox

Search

2019 AMC 10C Problems/Problem 25

Problem

Solution