1. Primitive root

I'm having difficulty with solving this problem, hope somebody could help.
Suppose (a,p)=1 where a is an integer and p is prime.
1) Show A={$\displaystyle m, 2m, 3m,..., (p-1)m$} is is reduced residue system mod p.
2) Let $\displaystyle C_k=1^k +2^k+...(p-1)^k$. Use part 1) to show that
$\displaystyle m^kC_k \equiv C_k mod p$
3) Let the number m be the primitive root g mod p. Prove that $\displaystyle C_k\equiv 0 mod p$ if p-1 doesn't divide k.

For the first part, can we pick a reduced residue system mod p, {1,2,3,...,p-1} then try to show that A={m,2m,3m,...,(p-1)m} again a r.r.s mod p. We know that {km} where k=1,2,...,p-1 are relatively prime to p. Then it suffices to show that no two elements from A are congruent mod p. Am I on the right track on this? I really have no idea on the last two questions.

2. Originally Posted by namelessguy
Suppose (m,p)=1 where a is an integer and p is prime.
1) Show A={$\displaystyle m, 2m, 3m,..., (p-1)m$} is is reduced residue system mod p.
Show that $\displaystyle mi \equiv mj (\bmod p) \implies i\equiv j (\bmod p)$ and so $\displaystyle m,2m,...,(p-1)m$ are all distinct. Therefore by pigeonholing they are a reduced residue system.

2) Let $\displaystyle C_k=1^k +2^k+...(p-1)^k$. Use part 1) to show that
$\displaystyle m^kC_k \equiv C_k mod p$
Because you get $\displaystyle m^k C_k = (m)^k + (2m)^k + ... + (m(p-1))^k$. And that is a permutation of $\displaystyle 1^k + ... + (p-1)^k$ mod $\displaystyle p$ by #1.

3) Let the number m be the primitive root g mod p. Prove that $\displaystyle C_k\equiv 0 mod p$ if p-1 doesn't divide k.
We get $\displaystyle C_k(g^k -1 ) \equiv 0 (\mod p)$. And $\displaystyle g^k -1 \not \equiv 0 (\bmod p)$ if $\displaystyle p-1\not | k$ since it is a primitive root.

3. Thanks for you help, theperfecthacker, but can you elaborate on the second question. I don't really get your answer for that part.

4. What you showed in #1 is that each of $\displaystyle m, 2m, \hdots, (p-1)m$ is congruent to one of $\displaystyle 1, 2, 3, \hdots, p-1$. This means that if you took all the least residues of the first list, you will eventually get the list of all numbers from 1 up to $\displaystyle p-1$ in some order:

$\displaystyle \begin{array}{rcll}m^{k}C_{k} & \equiv & m^k (1^k + 2^k + \hdots + (p-1)^k) & (\text{mod } p) \\ & \equiv & {\color{red}m}^k + ({\color{red}2m})^k + ({\color{red}3m})^k \hdots + ({\color{red}(p-1)m})^k & (\text{mod } p) \\ & \equiv & ({\color{red}1})^k + ({\color{red}2})^k + \hdots + ({\color{red}p-1})^k & (\text{mod } p) \end{array}$