kingwinner
- 1,266
- 0
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!
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!
Last edited: