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**

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**