Primitive roots & Reduced residue system

**kingwinner** · March 2nd 2010, 05:51 PM

[also under discussion in math link forum]

**kingwinner** · March 3rd 2010, 12:49 PM

About part b:

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

In part b, we have to show that if gcd(k,p-1)=d>1, then ${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...

**chiph588@** · March 3rd 2010, 03:06 PM

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

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

$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 $a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$ .

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

**kingwinner** · March 3rd 2010, 07:06 PM

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 $\{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\}$ are all distinct, then $x^k \equiv a \mod{p}$ is solvable for all $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 $(k,p-1)=d>0$ , now look at $a^{\frac{p-1}{d}}\mod{p}$ :

$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 $a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$ .

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

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

Thanks for your help!

**chiph588@** · March 3rd 2010, 07:36 PM

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 $\left(\mathbb{Z}/p\mathbb{Z}\right)^* = \{1,2,\cdot\cdot\cdot, p-1\}$ .

We're given that $\{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} \equiv \{1,2,\cdot\cdot\cdot, p-1\} \mod{p}$ . Hence for every $a \in \{1,2,\cdot\cdot\cdot, p-1\}$ , there is a corresponding $x^k \in \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\}$ such that $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 $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 $x^{c(p-1)}$ = 1 (mod p) ???

Thanks for your help!

Since $(x,p)=1$ , by Fermat's little theorem, $x^{p-1} \equiv 1 \mod{p}$ . Hence $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 $a \in \{1,2,\cdot\cdot\cdot, p-1\}, \; a^{\frac{p-1}{d}} \equiv 1 \mod{p}$ , where $d=(k,p-1)$ .

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

Our contradiction forces $d=1$ as desired.

**kingwinner** · March 3rd 2010, 09:59 PM

Originally Posted by chiph588@

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

Our contradiction forces $d=1$ as desired.

"If $d>1$ , we would have $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!

**chiph588@** · March 3rd 2010, 10:05 PM

Originally Posted by kingwinner

"If $d>1$ , we would have $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 $g\in \{1,2,\cdot\cdot\cdot , p-1\}$ and it was established that $a^{\frac{p-1}{d}}\equiv 1 \mod{p}$ for all $a$ , so the same applies to $g$ .

**kingwinner** · March 3rd 2010, 10:09 PM

Originally Posted by chiph588@

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

OK, but is it always true that any primitive root mod p must lie in the set {1,2,...,p-1}?

**chiph588@** · March 3rd 2010, 10:12 PM

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

**kingwinner** · March 3rd 2010, 10:15 PM

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?

**chiph588@** · March 4th 2010, 05:51 AM

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

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

Thread: Primitive roots & Reduced residue system

LinkBack

Thread Tools

Display

Primitive roots & Reduced residue system

Similar Math Help Forum Discussions

Reduced residue system modulo m

Proof with reduced residue systems

Help with reduced row echelon form/solving system

Reduced system of representatives

primitive root and quadratic residue

Search Tags