Let $N =\overline{abc}$ be a three-digit integer with distinct digits $a$, $b$, and $c$. What is the largest possible integer $N$ such that, when $N$ is cubed, the resulting integer ends with the same three digits as $N$?
Here is what I did: I know that $N^3\equiv N \pmod{1000}.$ That means that $N^3-N\equiv 0 \pmod{1000}$ or $N(N-1)(N+1)\equiv0 \pmod{1000}.$ However, I don't know how to quickly find numbers that fit the properties without brute force. What do I do?
As stated in the question, we are looking for a solution of $N^3\equiv N\pmod{1000}.$
This means $1000$ divides $N^3-N$, so $125$ and $8$ divide $N^3-N=N(N-1)(N+1).$
$5$ can divide only one of $N, N-1$, and $N+1$, so this means $125$ divides $N$, $N-1$, or $N+1$.
That means, if $N$ is a positive integer less than $1000,$
$ N \in \{0,1,124,125,126,249,250,251,374,375,376,499,500,501,624,625,626,749,750,751,874,875,876,999\}.$
If $8$ divides $N(N-1)(N+1)$ then $N$ is odd or $8$ divides $N.$
That means $N\in\{0,1,125,249,251,375,376,499,501,624,625,749,751,875,999\}.$
Now that we have found solutions of $N^3\equiv N\pmod{1000}$, the problem is easily solved.
OK, I got it. So, based on my initial trial, I know that $N(N-1)(N+1)\equiv0 \pmod{1000}.$ Now there are two cases. Why? Because $N+1$ and $N-1$ must have the same parity, meaning that they must both be even or they must both be odd. Note that $1000=2^3\times5^3$. Using this, we can rule out the case where $N$ is even. Why? Because if $N$ is even, $N+1$ and $N-1$ must be odd. $N$ must be divisible by 2, 4, or 8, but the two odd numbers should be divisible by 5, an impossibility (Note that $500$ is both divisible by 125 and 4, but not, 8, and since the other two numbers are odd. This means that $N$ must be odd, and if $N$ should be maximized, it should be a factor of 125. Note that there is at least one multiple of 4 next to a number ending in 25 or 75, so this assumption works. This gives us the largest three digit multiple of 125, $\boxed{875}$.
