We have, for a residue number system, $a^{n+(p-1)} \equiv a^n \bmod p$. In other words, the powers of $a$ repeat after $p-1$ iterations.
We can work with complex numbers by representing a number $$n \equiv a (\bmod p) + bi (\bmod p)$$
...In other words, we can represent a complex number as two values modulo some prime $p$. My question is: How many unique powers (or values) can there be of these complex numbers modulo a prime $p$?
In other words, if we take the values $1, n, n^2, \dots$, how many unique values can we have, modulo $p$?
To prove Fermat's little theorem one can use the fact that the ring $\mathbb{Z}/(p)$ is a finite field for all primes $p$. Now, if we are going to deal with numbers of the form $a+bi \mod{p}$, we have to introduce the ring of numbers of the form $a+bi$ and to quotient by some relation "$\mod{p}$".
Now, let $\mathbb{Z}[i] = \{ a+bi : a, b \in \mathbb{Z} \}$ be the ring of Gaussian Integers. This ring has the nice property that it is a PID and it extends the usual ring of integers $\mathbb{Z}$. Moreover, if $n \in \mathbb{N}$ is a natural number, then the quotient ring $\mathbb{Z}[i]/(n)$ is a finite ring with $n^2$ elements.
Since $\mathbb{Z}[i]$ is a PID, one can define divisibility relation on it, prime numbers, and unique prime factorization still holds.
Now, one can prove (I will not post the proof) the following theorem: if $p \in \mathbb{N}$ is a prime number, then the following are equivalent:
$p = a^2 + b^2$ for some $a,b \in \mathbb{N}$
$p=2$ or $p \equiv 1 \mod{4}$
this means that if $p\equiv 1 \mod{4}$, then it can be factorized in $\mathbb{Z}[i]$ as $p= a^2 + b^2 = (a+bi)(a-bi)$, so that $p$ is not prime in $\mathbb{Z}[i]$ (for completeness note that $2 = (1+i)(1-i)$ )!
Moreover one can also show that in the other case (i.e. $p \equiv 3 \mod{4}$) the number $p$ remains prime in $\mathbb{Z}[i]$.
So finally, fixed a prime $p \in \mathbb{N}$ we can consider the ring of numbers of the form $a+bi$ with $a,b \in \mathbb{Z}/p\mathbb{Z}$. This is just the quotient ring $\mathbb{Z}[i]/(p)$, which has, as I said above, $p^2$ elements.
In the case that $p \equiv 3 \mod{4}$, this ring is the finite field $\mathbb{F}_{p^2}$ with $p^2$ elements, since $p$ is prime in $\mathbb{Z}[i]$. Since the multiplicative group of $\mathbb{F}_{p^2}^*$ is cyclic of order $p^2-1$, we have that some numbers $n = a+bi \mod{p}$ have $p^2-1$ different powers, i.e. $1, n, n^2, \dots, n^{p^2-2}$ are all distinct. These are precisely those numbers which generate the whole group $\mathbb{F}_{p^2}^*$, and the number of them is $\varphi( p^2-1)$, where $\varphi$ denotes Euler's totient function.
In the case $p=2$ we have a ring with 4 elements which is isomorphic to $\mathbb{Z}/2 \times \mathbb{Z}/2$. Here all numbers $n \neq 0$ satisfy $n^2=1$.
In the last case $p \equiv 1 \mod{4}$ the ring $\mathbb{Z}[i]/(p)$ is not a field, but it is isomorphic to the ring $\mathbb{F}_p[x]/ (x^2+1)$, and there are some zero divisors (i.e. if $p= a^2+b^2$ then $(a+bi)(a-bi)=0$). In fact in this case there can be nilpotent elements and things can be weird. I'm not so sure on how this last case behaves.