The number of e-th power residues $\bmod m$ 
For each positive integer $m$ define $\Bbb{Z}_m = {0, 1, 2, \ldots , m − 1}$, the set of all residues modulo $m$, and define
  $$C(m,e) = \{ k ∈ \Bbb{Z}_m \mid 0 \ne k ≡ a^e \pmod m \text{ for some }a \in \Bbb{Z} \}$$
  So $C(m,e)$ is the set of all non-zero e-th power residues mod m.

For a specific $e$ such that $e\mid m-1$ and $m$ is prime, I know that you can show that the number of elements in $C(m,e)$ is $(m-1)/e$. What about the cases when $e\nmid (m-1)$? 
I computed $C(m,e)$ numerically using arbitrary values Matlab and I am pretty sure that when m is prime and $e\nmid (m-1)$, $C(m,e)$ has $m-1$ elements i.e. is a full set. How can we prove this?
And then what if m isn't prime but instead $m = pq$ and $e\mid(p-1)$ and $e\mid (q-1)$? Again I plugged in values in Matlab to find that integers with these properties gave the size of $C(m,e)$ to be$$\left(\frac{p-1}{e}+1 \right)\left(\frac{q-1}{e}+1\right)-1$$
But again I do not know how to show this analytically. Any hints or insights would be greatly appreciated.
 A: 1. Let $p$ be prime, and suppose that $e$ and $p-1$ are relatively prime. We will show that any $a$ not divisible by $p$, there is an $x$ such that $x^e\equiv a\pmod{p}$.
Since $e$ and $p-1$ are relatively prime, by the "Bezout Identity" there exist integers $s$ and $t$ such that $es+(p-1)t=1$. Then 
$$a=a^1=a^{es+(p-1)t}=(a^s)^e (a^{p-1})^t\equiv (a^s)^e\pmod{p}.$$
So we have found an $x$, namely $a^s$, such that $x^e\equiv a\pmod{p}$.
Note that it is not enough to assume that $e$ does not divide $p-1$. For example, $4$ does not divide $7-1$, but $6$ is not a fourth power of anything modulo $7$.
2. Now we look at your assertion about products $pq$ of distinct primes, where $e\mid p-1$ and $e\mod q-1$. We show that, counting $0$, there are $$\left(\frac{p-1}{e}+1\right)\left(\frac{q-1}{e}+1\right)\tag{1}$$ distinct $e$-th powers, modulo $pq$. 
Note first that any $e$-th power modulo $pq$ is an $e$-th power modulo $p$ and modulo $q$. Now let $a$ be an $e$-th power modulo $p$, and let $b$ be an $e$-th power modulo $q$. By the Chinese Remainder Theorem, there is a unique $c$ modulo $pq$ such that $c\equiv a\pmod{p}$ and $c\equiv b\pmod{q}$. We show that $c$ is an $e$-th power modulo $pq$. 
Let $x^e\equiv a\pmod{p}$, and let $y^e\equiv b\pmod{q}$. Let $w$ be the solution of the system of congruences $w\equiv x\pmod{p}$, $w\equiv y\pmod{q}$. 
Then $w^e\equiv a\equiv c \pmod{p}$ and  $w^e\equiv c\pmod{q}$, and therefore $c$ is an $e$-th power modulo $pq$.
It follows that the number of $e$-th powers modulo $pq$ is given by Formula 1. The formula and proof generalize to products of $k$ distinct primes.
