# Primitive root

• Oct 4th 2008, 11:17 PM
namelessguy
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={ $m, 2m, 3m,..., (p-1)m$} is is reduced residue system mod p.
2) Let $C_k=1^k +2^k+...(p-1)^k$. Use part 1) to show that
$m^kC_k \equiv C_k mod p$
3) Let the number m be the primitive root g mod p. Prove that $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.
• Oct 5th 2008, 07:58 AM
ThePerfectHacker
Quote:

Originally Posted by namelessguy
Suppose (m,p)=1 where a is an integer and p is prime.
1) Show A={ $m, 2m, 3m,..., (p-1)m$} is is reduced residue system mod p.

Show that $mi \equiv mj (\bmod p) \implies i\equiv j (\bmod p)$ and so $m,2m,...,(p-1)m$ are all distinct. Therefore by pigeonholing they are a reduced residue system.

Quote:

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

Quote:

3) Let the number m be the primitive root g mod p. Prove that $C_k\equiv 0 mod p$ if p-1 doesn't divide k.
We get $C_k(g^k -1 ) \equiv 0 (\mod p)$. And $g^k -1 \not \equiv 0 (\bmod p)$ if $p-1\not | k$ since it is a primitive root.
• Oct 5th 2008, 06:15 PM
namelessguy
Thanks for you help, theperfecthacker, but can you elaborate on the second question. I don't really get your answer for that part.
• Oct 5th 2008, 07:08 PM
o_O
What you showed in #1 is that each of $m, 2m, \hdots, (p-1)m$ is congruent to one of $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 $p-1$ in some order:

$\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}$