Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

3 Answers 3

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

share|improve this answer

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

share|improve this answer
  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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.