elementary number theory - The remainder of $n^{11}$ when divided by $23$.

Let $n$ be a natural number such that $n$ is not divisible by $23$. Then the remainder when $n^{11}$ is divided by $23$ is $±1(\mod 23)$.

I have solve it by a laborious calculations. Since by division algorithm there exist integers $q$ and $r$ such that $n=23q+r$ where $0

Answer

By Fermat's little theorem:
$$n^{22} \equiv 1 \pmod {23}$$

Since $23$ is a prime, $\Bbb Z/23\Bbb Z$ is a field, so $x^2-1$ only has two roots over $\Bbb Z/23\Bbb Z$, but we know that those two roots are $\pm1$, so $n^{11} \equiv \pm1 \pmod {23}$ since $n^{11}$ is a solution to $x^2-1=0$.

Informally, the last sentence means "take square root of both sides".