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 - The Fusion of Science and Community**

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

# Primitive roots & Reduced residue system

Loading...

Similar Threads - Primitive roots Reduced | Date |
---|---|

Primitive roots of Z_32 | Oct 28, 2012 |

Relationship between primitive roots of a prime | Nov 17, 2009 |

Primitive root modulo n | Jan 9, 2009 |

Primitive 5th root of unity extension | Aug 18, 2008 |

Primitive roots - annoying problem | May 11, 2008 |

**Physics Forums - The Fusion of Science and Community**