My original problem is to find all the possible values of $n^7$ mod $29$ for $n \in \mathbb{Z}$, and I was wondering if there is a more efficient way to get all of the possible values than this method:
First, I noted that every integer $n$ can be written as $n = 29k + a$ for $n \in \mathbb{Z}$, $k \in \{0,1, ..., 28\}$.
Then, we have $n^7 = (29k + a)^7 = 29M+a^7$ for some $M \in \mathbb{Z}$. Therefore, all powers of $7$ are congruent to one of $0^7$, $1^7$, ..., $28^7$ mod $29$. Working out all $29$ of these we get that the possible values are $\{0, 1, 12, 17, 28\}$.
I am wondering if there is a faster way to obtain these values since to check $29$ cases and only get $5$ values is a lot, and have made these observations:
I have found this very similar question - find the possible values of $a^4$ mod $120$, that uses the prime factorisation of $120$ and the Chinese Remainder Theorem with all of $120$'s prime factors as moduli, but since $29$ is prime I am not sure if any of the methods there can help.
I have observed that $\phi(29) = 28 = \color{red}{4}*7$, where $\phi$ is the Euler totient function. Picking another prime number that is one above a multiple of $7$, we have $\phi(43) = 42 = \color{red}{6}*7$, and it turns out that $n^7$ mod $43$ has $\{0, 1, 6, 7, 36, 37, 42\}$ as solutions: $7$ total solutions, $\color{red}{6}$ of which are non-zero, similarly to how $29$ has $5$ total solutions, $\color{red}{4}$ of which are non-zero.
Is this link always valid, i.e. is the Euler totient function telling us how many solutions to expect? (So, generally, we would expect that for a prime $p$, $n^a$ mod $p$ has $k$ solutions if we can write $\phi(p) = p-1$ as $ak$ for some integer $k$?) How can we prove this?