# 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?

-
Isn't this false for $a=2$ since $x^2 = (-x)^2$? Did you mean $\gcd(a,p-1)=1$? – Srivatsan Sep 14 '11 at 20:31
If $p=7, 2^3=1 \pmod p$ so it fails – Ross Millikan Sep 14 '11 at 20:32
@Srivatsan Narayanan: yep you are right, i mistyped, how to correct my mistake? make another question? – Pierre Fermat Sep 14 '11 at 22:59
Well, Pierre, what did you intend to be the question? I guess many of the answers cover both the $p$ and $p-1$ cases. Perhaps you can add the new question to the old question. But do not change the question substantially especially if that will invalidate the existing answers. – Srivatsan Sep 14 '11 at 23:05
Also see MSE question re the number of equivalence classes of (in notation of present question) $k^a\mod p$ – jwpat7 Oct 11 '11 at 22:42

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$.

-

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

-
1. Check what happens for $a=2$.
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).

-