Let p be a prime.(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Primitive roots & Reduced residue system

**Physics Forums | Science Articles, Homework Help, Discussion**