Smallest cube ending in $2017$

What is the smallest cube ending in $2017$?

My try: I know that the only possible units digit is $3$,

$$(a+3)^3 = 2017 \mod 10^4\;$$

and

$$a^3 + 9a^2 + 27a = 1990\mod 10^4$$

I don't know how to proceed, I tried factoring and adding $10^5$ and $1990$ but when I saw the answer, this approach would take forever.

• You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress. – Mark Bennet Aug 12 '18 at 11:55
• It's rather modulo $10^4$ – Arnaud Mortier Aug 12 '18 at 11:55

Recall Carmichael's theorem: $a^{\lambda(m)} \equiv 1 \bmod m$ for all $a$ coprime with $m$.

For $\lambda(10^4)=500$, we get $1 + 500 = 167 \cdot 3$ and so $a \equiv a \cdot 1 \equiv a \cdot a^{500} \equiv (a^{167})^3 \bmod 10^4$.

Thus, the answer is $2017^{167} \bmod 10^4$, which is $9073$, by repeated squaring.

There is only one solution mod $10^4$ because $x \mapsto x^3$ is injective in $U(10^4)$, as we have seen above.

• Which formula you have used for the last deduction – lab bhattacharjee Aug 12 '18 at 13:17
• @user202729, see my edited answer – lhf Aug 12 '18 at 16:29

$x^3\equiv 7 \pmod {10}$. So $x\equiv 3 \pmod {10}$.

Put $x=10y+3$, and compute $\pmod {100}$. This yields $1000y^3+900y^2+270y+27 \equiv 17 \pmod {100}$. Thus $70y \equiv -10 \pmod {100}$, or equivalently, $7y \equiv -1 \pmod {10}$. Divide by $7$: $y \equiv 7 \pmod {10}$.

Put $y=10z+7$, hence $x=100z+73$. I think you see the pattern now: calculate modulo $1000$, it gives you the $\pmod{10}$ remainder of $z$, and one more iteration gives you the $\pmod {10000}$ remainder of $x$, which is also the smallest solution.

(Solution: $9073$)

$a^3 + 9a^2 + 27a = 1990\mod 10^4\Longleftrightarrow\cases{a^3 + 9a^2 + 27a = 1990\mod 2^4\\a^3 + 9a^2 + 27a = 1990\mod 5^4\\}$

Now $2^4=16$, so the first equation is easy and happens to have only one solution, $14\bmod 16$.

As for the second, the only solution is $320\bmod 625$.

By the CRT, the only solution modulo $10000$ is $9070$, resulting in the least solution $$9073^3=746883272017$$