- #1

- 1,270

- 0

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!

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: