Powers as a complete residue system modulo $p$? Question 1.
With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$  is a complete residue system modulo $p$?  If not, will a similar statement hold?
Question 2. 
I was told it works for $a = 3$, does anyone know a simple proof of it in this particular case?
 A: Note. Original question read "$\gcd(a,p)=1$" instead of $\gcd(a,p-1)=1$".
Question 1. No. Note that the condition $\gcd(a,p)=1$ is redundant: if $p$ is prime, then $\gcd(a,p)=1$ for all $a$, $0\lt a\lt p$. If you take $a=p-1$, then by Fermat's Little Theorem you have that $r^a = r^{p-1}\equiv 1\pmod{p}$ for every $r$ that is not divisible by $p$, so your list consists of $0$ and $1$ (the latter $p-1$ times) and only those.
More generally: for every proper divisor $d$ of $p-1$, there exists an $r$, $1\lt r\lt p$, such that $r^d\equiv 1\pmod{p}$ (this follows from the fact that the multiplicative group of integers modulo $p$ is cyclic of order $p-1$). In particular, your list cannot contain all residue classes.
However, if $\gcd(a,p-1)=1$, then the answer is yes (was that what your condition was meant to be?) For $p=2$ this is immediate. For $p$ odd, let $g$ be a primitive root modulo $p$. Then $g^a$ is also a primitive root modulo $p$ (since its multiplicative order is $(p-1)/\gcd(a,p-1) = p-1$), which yields the result.
Question 2. It's false. Take $p=7$. Then
$$\begin{align*}
1^3 &\equiv 1 \pmod{7}\\
2^3 &\equiv 1 \pmod{7}\\
3^3 &\equiv 6\pmod{7}\\
4^3 &\equiv 1\pmod{7}\\
5^3 &\equiv 6\pmod{7}\\
6^3 &\equiv 6\pmod{7}
\end{align*}$$
so you only get $1$ and $6$. Your list then consists of $0$, three copies of $1$, and three copies of $6$, not a complete residue system modulo $p$. $3$ works for primes that are congruent to $2$ modulo $3$, for $p=2$ and for $p=3$, and that's it; it fails for every prime that is congruent to $1$ modulo $3$.
A: HINT $\rm\ (a,p-1)=1\ \Rightarrow\ \exists\: b,\ b\:a\:\equiv\: 1\pmod{p-1}\ \Rightarrow\ (n^b)^{\:a}\equiv\: n\pmod{p}\ $ so $\rm\:x\:\to\: x^{\:a}\:$ is onto
A: *

*Check what happens for $a=2$.

*A pointer to the proof (which also shows the way for a more general proof): for every $p$ there exists a "primitive element" $g$ such that $g^0,g^1,g^2,\dots,g^{p-1}$ is a complete residue system modulo p. Hence, you need only ask yourself what is $g^0,g^3,g^6,\dots,g^{3(p-1)}$.


Note that as was said in the comments, you'll need $\gcd(a,p-1)=1$ in order for this to work (try to see where this pops up in the proof).
