Jack provides an answer and explanation as to how many $I$th powers there are modulo a prime $p$.
However, I am unsure as to the logic behind the following step:
When we apply the map $x\mapsto x^i$ to $\{g,...,g^{p-1}\}$, where $g$ is a primitive root modulo $p$, the new set of exponents has cardinality $$ \frac{p-1}{\gcd(i,p-1)} $$.
I understand in principle why this step works but cannot prove it rigorously.
Let $d = \gcd(i,p-1)$. Note that $(g^x)^i \equiv (g^y)^i \mod p$ iff $g^{ix - iy} \equiv 1 \mod p$, and since the multiplicative order of $g \mod p$ is $p-1$, this is the case iff $i(x-y)$ is a multiple of $p-1$, and thus iff $x-y$ is divisible by $(p-1)/d$. Thus the images of $g, g^2, \ldots, g^{(p-1)/d}$ are all distinct, and by adding multiples of $(p-1)/d$ to these we can get all of $g, g^2, \ldots, g^{p-1}$