15
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ You should use $10a+3$ instead of $a+3$ since $3$ is the units digit, and that will help you to make more progress. $\endgroup$ Commented Aug 12, 2018 at 11:55
  • 3
    $\begingroup$ It's rather modulo $10^4$ $\endgroup$ Commented Aug 12, 2018 at 11:55

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
0
11
$\begingroup$

$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$)

$\endgroup$
8
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .