Find the least nonnegative residue of $5^{18} \mod 11$. To do this I took $5^2 \equiv 3 \mod 11$. Then I did $(5^2)^5 \equiv 3^5 \mod 11$. And $3^5 \equiv 1 \mod 11$.
So now I have $5^{10} \equiv 1 \mod 11$. Then I multiplied both sides by $5^8$ to get $5^{18} \equiv 5^8 \mod 11$. So I believe $5^8$ is the least nonnegative residue but I am not entirely sure. Can someone please confirm that this is correct?
$\endgroup$ 13 Answers
$\begingroup$As you mentioned, we have $5^2 \equiv 3$ mod 11. However, I find it easier to proceed by showing,
$$5^8 \equiv (5^2)^4 \equiv 3^4 \equiv 4 \text{ mod }11, $$
so that $$5^{16} \equiv (5^8)^2 \equiv 4^2 \equiv 5 \text{ mod }11,$$ and then finally,
$$ 5^{18} \equiv 5^2\cdot5^{16} \equiv 3 \cdot 5 \equiv 4 \text{ mod } 11.$$
Also, this should be a much more satisfying answer since the least nonnegative residue of $n$ will always be in the interval $[0,n]$.
$\endgroup$ 2 $\begingroup$Best way to do this is to repeatedly divide the exponent by 2.
$$ 18 = 2 \times 9, ~ 9 = 2 \times 4 + 1,~ 4=2 \times 2 $$ So $$ 5^2 = 25 \equiv 3 \mod 11 \\ 5^4 \equiv 3^2 = 9 \mod 11 \\ 5^8 \equiv 9^2 = 81 \equiv 4 \mod 11 \\ 5^9 =5 \cdot 5^8 \equiv 20 \equiv 9 \mod 11 \\ 5^{18} \equiv 9^2 = 81\equiv 4 \mod 11 $$ Hence the answer is $4$.
Note you can save a lot of work by noting that by Fermat's theorem $5^{10} \equiv 1\mod11$
Hence $$5^{18} = 5^{10} 5^8 \equiv 5^8 \equiv 4 \mod 11$$
$\endgroup$ $\begingroup$${\rm mod}\ 11\!:\ 2^{18} 5^{18}\equiv 10^{18}\equiv (-1)^{18}\!\equiv 1,\ $ so $\ 5^{18}\!\equiv 2^{-18}\!\equiv 2^2 (2^5)^{-4}\equiv 2^2(-1)^{-4}\!\equiv 2^2$
$\endgroup$
