Primitive roots & Reduced residue system

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0

Main Question or Discussion Point

Let p be a prime.
a) If gcd(k,p-1)=1, then [tex]1^k, 2^k,..., (p - 1)^k[/tex] form a reduced residue system mod p.
b) If [tex]1^k, 2^k,..., (p - 1)^k[/tex] form a reduced residue system mod p, then gcd(k,p-1)=1.
=================================

I proved part a by first showing that each of [tex]1^k, 2^k,..., (p - 1)^k[/tex] is relatively prime to p.
And then I noted that since p is a prime, there exists a primitive root mod p, call it g, so [tex]g, g^2,...,g^{p - 1}[/tex] is a reduced residue system mod p. Then using this, I showed that if gcd(k,p-1)=1, then no two of [tex]1^k, 2^k,..., (p - 1)^k[/tex] are congruent to each other mod p. Thus, it is a reduced residue system mod p.

But now I'm stuck on proving part b.
Euqivalently, for part b, we can prove that if gcd(k,p-1)≠1, then [tex]1^k, 2^k,..., (p - 1)^k[/tex] do NOT form a reduced residue system mod p. But I can't figure out how to prove this...

Any help is appreciated!
 
Last edited:

Answers and Replies

  • #2
1,056
0
What do you mean a "reduced residue system"? g, g^2....g^(p-1) ARE the residue system by nature of a primitative root. You are talking about "p, a prime," you know.
 
  • #3
1,270
0
A reduced residue system modulo n is a set of φ(n) integers such that each integer is relatively prime to n and no two are congruent modulo n. I proved all of these properties in part a.

"g, g^2....g^(p-1) ARE the residue system " <----yes, and I proved this in part a.

The problem is how to do part b?

Thanks for any help!
 
  • #4
402
1
A primitive root g must be congruent mod p to one of the elements of the residue system. On the other hand what must be the order of g, mod p?
 
  • #5
1,270
0
A primitive root g must be congruent mod p to one of the elements of the residue system. On the other hand what must be the order of g, mod p?
Since g is a primitive root mod p, the order of g (mod p) must be p-1, and we have gp-1=1(mod p)

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

Can someone kindly help me, please? I'm still puzzled...
 
Last edited:
  • #6
402
1
Correct, if g is a primitive root, then its order mod p is p-1 and you have:

[tex]g\equiv a^{k}\left(\rm{mod} p\right)[/tex]

For some [itex]a^k[/itex] in the residue set. Now, if d=gcd(k,p-1) [tex]g^\frac{p-1}{d}[/tex] is congruent to what mod p?
 
  • #7
1,270
0
Correct, if g is a primitive root, then its order mod p is p-1 and you have:

[tex]g\equiv a^{k}\left(\rm{mod} p\right)[/tex]
Can you explain why this is true, please? This doesn't seem clear to me...
Also, what is "a"?



For some [itex]a^k[/itex] in the residue set. Now, if d=gcd(k,p-1) [tex]g^\frac{p-1}{d}[/tex] is congruent to what mod p?
d=gcd(k,p-1)>1

[tex]g^\frac{p-1}{d}[/tex] = +/-1 (mod p)?? I don't think this is right...I think something like g(p-1)/d = 3 (mod p) is also possible, provided 3d=1 (mod p). There are many possibilities and I don't think there is a strict rule...


More help, please? I'm pretty confused now...
Thank you!
 
  • #8
1,056
0
If we take a look at g^(p-1)/2 it can only be equal to plus or minus 1. This is the case because [g^(p-1)/2)]^2 =1. Thus x^2==1 Mod p has the factors (x-1)(x+1). However those cases do form what is referred to as a subgroup. Since the two cases interact giving us four cases, 1x1, -1x1, 1x-1 or (-1)(-1). The first and last having the value 1 and the other two -1.

A similar thing happens for g^(p-1)/d where d divides p-1. We form a subgroup. It helps to find and study examples.
 
  • #9
402
1
Let [itex]Res[/itex] be the residue system:

[tex]Res=\left\{1^k,2^k,\cdots \left(p-1\right)^k\right\}[/tex]

Every element of it is congruent mod p to a unique element of [tex]\left\{1,2,\cdots \left(p-1\right)\right\}[/tex] (all complete residue systems satisfy this). Therefore, the primitive root g will be congruent mod p to some [itex]a^k \in Res[/itex].

Now, [tex]g^{\frac{p-1}{d}}[/tex] is congruent mod p to a specific value, but you have to apply Fermat's theorem to find it.
 

Related Threads for: Primitive roots & Reduced residue system

  • Last Post
Replies
16
Views
4K
  • Last Post
Replies
5
Views
9K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
2K
Top