# Thread: Primitive roots & Reduced residue system

1. ## Primitive roots & Reduced residue system

[also under discussion in math link forum]

Since g is a primitive root mod p, the order of g (mod p) must be p-1, and we have $\displaystyle g^{p-1}$=1(mod p)

In part b, we have to show that if gcd(k,p-1)=d>1, then $\displaystyle {1^k,2^k,...,(p-1)^k}$ does NOT form a reduced residue system mod p. If we can show that some distinct elements in the set are congruent to each other, then we're done. But how to prove show this???

Can someone kindly help me, please? I'm still puzzled...

3. Since $\displaystyle \{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\}$ are all distinct, then $\displaystyle x^k \equiv a \mod{p}$ is solvable for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$.

Let's suppose $\displaystyle (k,p-1)=d>0$, now look at $\displaystyle a^{\frac{p-1}{d}}\mod{p}$:

$\displaystyle a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p}$ for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$.

Hence we've shown the order of the group $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^*$, which is $\displaystyle p-1$, divides $\displaystyle \frac{p-1}{d}$
This forces $\displaystyle d=1$.

4. hmm...I have no background in abstract algebra. I haven't learnt anything about groups and things like Z/pZ, so I can't follow your proof. Can you explain the proof in more basic terms, please?

Originally Posted by chiph588@
Since $\displaystyle \{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\}$ are all distinct, then $\displaystyle x^k \equiv a \mod{p}$ is solvable for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$.
I don't see why this is true...could you explain a little more on this, please??
Also, what is "a"?

Let's suppose $\displaystyle (k,p-1)=d>0$, now look at $\displaystyle a^{\frac{p-1}{d}}\mod{p}$:

$\displaystyle a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p}$ for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$.

Hence we've shown the order of the group $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^*$, which is $\displaystyle p-1$, divides $\displaystyle \frac{p-1}{d}$
This forces $\displaystyle d=1$.
How do you know that $\displaystyle x^{c(p-1)}$ = 1 (mod p) ???

5. Originally Posted by kingwinner
hmm...I have no background in abstract algebra. I haven't learnt anything about groups and things like Z/pZ, so I can't follow your proof. Can you explain the proof in more basic terms, please?
First note that $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^* = \{1,2,\cdot\cdot\cdot, p-1\}$.

We're given that $\displaystyle \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} \equiv \{1,2,\cdot\cdot\cdot, p-1\} \mod{p}$. Hence for every $\displaystyle a \in \{1,2,\cdot\cdot\cdot, p-1\}$, there is a corresponding $\displaystyle x^k \in \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\}$ such that $\displaystyle x^k \equiv a \mod{p}$. (A surjective map onto itself is injective too, if you like set theory.) That's what I meant when saying $\displaystyle x^k \equiv a \mod{p}$ is solvable.

I don't see why this is true...could you explain a little more on this, please??
Also, what is "a"?

How do you know that $\displaystyle x^{c(p-1)}$ = 1 (mod p) ???

Since $\displaystyle (x,p)=1$, by Fermat's little theorem, $\displaystyle x^{p-1} \equiv 1 \mod{p}$. Hence $\displaystyle x^{c\cdot (p-1)} = \left(x^{p-1}\right)^c \equiv 1^c \equiv 1 \mod{p}$.

Let me try this proof a little bit differently.

Above, I showed for all $\displaystyle a \in \{1,2,\cdot\cdot\cdot, p-1\}, \; a^{\frac{p-1}{d}} \equiv 1 \mod{p}$, where $\displaystyle d=(k,p-1)$.

Choose $\displaystyle g$ such that it's a primitive root (we know one exists here). If $\displaystyle d>1$, we would have $\displaystyle g^{\frac{p-1}{d}} \equiv 1 \mod{p}$, which is a contradiction since $\displaystyle \frac{p-1}{d} < p-1$ and for all $\displaystyle c<p-1, \; g^c\not\equiv 1 \mod{p}$.

Our contradiction forces $\displaystyle d=1$ as desired.

6. Originally Posted by chiph588@
Choose $\displaystyle g$ such that it's a primitive root (we know one exists here). If $\displaystyle d>1$, we would have $\displaystyle g^{\frac{p-1}{d}} \equiv 1 \mod{p}$, which is a contradiction since $\displaystyle \frac{p-1}{d} < p-1$ and for all $\displaystyle c<p-1, \; g^c\not\equiv 1 \mod{p}$.

Our contradiction forces $\displaystyle d=1$ as desired.
"If $\displaystyle d>1$, we would have $\displaystyle g^{\frac{p-1}{d}} \equiv 1 \mod{p}$" <-----hmm...Why is this true?

I know this may be obvious to you, but to me it's not...

Thanks for your time and patience in explaining this!

7. Originally Posted by kingwinner
"If $\displaystyle d>1$, we would have $\displaystyle g^{\frac{p-1}{d}} \equiv 1 \mod{p}$" <-----hmm...Why is this true?

I know this may be obvious to you, but to me it's not...

Thanks for your time and patience in explaining this!
It's because $\displaystyle g\in \{1,2,\cdot\cdot\cdot , p-1\}$ and it was established that $\displaystyle a^{\frac{p-1}{d}}\equiv 1 \mod{p}$ for all $\displaystyle a$, so the same applies to $\displaystyle g$.

8. Originally Posted by chiph588@
It's because $\displaystyle g\in \{1,2,\cdot\cdot\cdot , p-1\}$ and it was established that $\displaystyle a^{\frac{p-1}{d}}\equiv 1 \mod{p}$ for all $\displaystyle a$, so the same applies to $\displaystyle g$.
OK, but is it always true that any primitive root mod p must lie in the set {1,2,...,p-1}?

9. Yes, there always will exist a primitive root modulo a prime.

10. Originally Posted by chiph588@
Yes, there always will exist a primitive root modulo a prime.
But is it possible that the primitive root exists, but lies outside the set {1,2,...,p-1}?? Why or why not?

11. I'm not sure you know what a primitive root is...

A primitive root $\displaystyle g$ of a prime number $\displaystyle p$ is an element of $\displaystyle \{1,2,\cdot\cdot\cdot, p-1\}$ such that $\displaystyle g^c \not\equiv 1 \mod{p}$ for all $\displaystyle 0<c<p-1$.