Number Theory Question by Mithil Shah # 1

We are looking for the smallest positive integer $n$ such that $n^3 \equiv 888 \mod 1000$ . Since $1000=8 \cdot 125$ , we can consider $n^3$ modulo $8$ and $125$ respectively.

First, note that $n^3 \equiv 888 \equiv 0 \mod 8$ . Thus, $n=2m$ for some $m$ . Then $(2m)^3 \equiv 888 \mod 125 \implies m^3 \equiv 111 \mod 125$ . Now we will work our way up the powers of $5$ to determine $m$ .

We have that $m^3 \equiv 1 \mod 5$ , and thus $m \equiv 1 \mod 5$ ; say $m=1+5k$ for some $k$ . Then $m^3 \equiv 11 \mod 25 \implies (1+5k)^3 \equiv 11 \mod 25 \implies 1+15k \equiv 11 \mod 25 \implies 15k \equiv 10 \mod 25$ . Dividing both sides by $5$ (including the modulus) yields $3k \equiv 2 \mod 5 \implies k \equiv 4 \mod 5$ ; say $k=4+5l$ for some $l$ , so $m=21+25l$ .

Finally, $m^3 \equiv 111 \mod 125 \implies (21+25l)^3 \equiv 111 \mod 125 \implies 25l \equiv 75 \mod 125$ . Again, dividing both sides by $25$ yields $l\equiv 3 \mod 5$ , say $l=3+5j$ for some $j$ . Then we have $m=21+25(3+5j)=96+125j$ .

Since $n=2m=192+250j$ and we want the smallest positive $n$ , we can choose $j=0$ and so $n=\boxed{192}$