If $n^{9}=19m+r $ then what is $r\mod19$

Question

If $n^{9}=19m+r $ for $n,m\in Z^{+}$then how do we find $r\mod19$? I think it must have values between $[1,18]$ as $n^{9}$ is divided by $19$ to get $r$ (remainder) . Can we tell what exact value it will be?

Answer 1

We get $n^9 \equiv r \pmod{19}$, thus by squaring we have $n^{18}=r^2$. If $n \not \equiv 0 \pmod{19}$, then we have $n^{18}\equiv 1 \pmod{19}$ by Fermat's little theorem. Thus we get $r^2 \equiv 1\pmod{19}$ in this case. This implies that $r \equiv 1 \pmod{19}$ or $r \equiv -1 \equiv 18 \pmod{19}$ as these are the only numbers who square to $1$ modulo $19$ (If you know abstract algebra, this follow because $\Bbb Z/19\Bbb Z$ is a field, as $19$ is prime. If you don't you can check that by a computation.) Of course we also have the case that $n \equiv 0 \pmod{19}$ in which case we also get $r=0 \pmod{19}$.

The possible residues are $\overline 0, \overline 1, \overline{18}$ and all three can occur.