Primitive roots & Reduced residue system

[kingwinner]

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

I proved part a by first showing that each of $$1^k, 2^k,..., (p - 1)^k$$ 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 $$g, g^2,...,g^{p - 1}$$ is a reduced residue system mod p. Then using this, I showed that if gcd(k,p-1)=1, then no two of $$1^k, 2^k,..., (p - 1)^k$$ 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[/color].
Euqivalently, for part b, we can prove that if gcd(k,p-1)≠1, then $$1^k, 2^k,..., (p - 1)^k$$ do NOT form a reduced residue system mod p. But I can't figure out how to prove this...

Any help is appreciated!

 

[robert Ihnot]

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.

 

[kingwinner]

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!

 

[JSuarez]

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?

 

[kingwinner]

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 g^p-1=1(mod p)

In part b, we have to show that if gcd(k,p-1)=d>1[/color], 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 show this?

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

 

[JSuarez]

Correct, if g is a primitive root, then its order mod p is p-1 and you have:

$$g\equiv a^{k}\left(\rm{mod} p\right)$$

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

 

[kingwinner]

Correct, if g is a primitive root, then its order mod p is p-1 and you have:

$$g\equiv a^{k}\left(\rm{mod} p\right)$$

Can you explain why this is true, please? This doesn't seem clear to me...
Also, what is "a"?

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

d=gcd(k,p-1)>1

$$g^\frac{p-1}{d}$$ = +/-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 3^d=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!

 

[robert Ihnot]

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.

 

[JSuarez]

Let $Res$ be the residue system:

$$Res=\left\{1^k,2^k,\cdots \left(p-1\right)^k\right\}$$

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

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