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$
  • 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$ – Mark Bennet Aug 12 '18 at 11:55
  • 3
    $\begingroup$ It's rather modulo $10^4$ $\endgroup$ – Arnaud Mortier Aug 12 '18 at 11:55
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$
  • $\begingroup$ Which formula you have used for the last deduction $\endgroup$ – lab bhattacharjee Aug 12 '18 at 13:17
  • $\begingroup$ @user202729, see my edited answer $\endgroup$ – lhf Aug 12 '18 at 16:29
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.