[also under discussion in math link forum]
About part b:
Since g is a primitive root mod p, the order of g (mod p) must be p-1, and we have $\displaystyle g^{p-1}$=1(mod p)
In part b, we have to show that if gcd(k,p-1)=d>1, then $\displaystyle {1^k,2^k,...,(p-1)^k}$ does NOT form a reduced residue system mod p. If we can show that some distinct elements in the set are congruent to each other, then we're done. But how to prove show this???
Can someone kindly help me, please? I'm still puzzled...
Since $\displaystyle \{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\} $ are all distinct, then $\displaystyle x^k \equiv a \mod{p} $ is solvable for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* $.
Let's suppose $\displaystyle (k,p-1)=d>0 $, now look at $\displaystyle a^{\frac{p-1}{d}}\mod{p} $:
$\displaystyle a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p} $ for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* $.
Hence we've shown the order of the group $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^* $, which is $\displaystyle p-1 $, divides $\displaystyle \frac{p-1}{d} $
This forces $\displaystyle d=1 $.
hmm...I have no background in abstract algebra. I haven't learnt anything about groups and things like Z/pZ, so I can't follow your proof. Can you explain the proof in more basic terms, please?
I don't see why this is true...could you explain a little more on this, please??
Also, what is "a"?
How do you know that $\displaystyle x^{c(p-1)}$ = 1 (mod p) ???Let's suppose $\displaystyle (k,p-1)=d>0 $, now look at $\displaystyle a^{\frac{p-1}{d}}\mod{p} $:
$\displaystyle a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p} $ for all $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* $.
Hence we've shown the order of the group $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^* $, which is $\displaystyle p-1 $, divides $\displaystyle \frac{p-1}{d} $
This forces $\displaystyle d=1 $.
Thanks for your help!
First note that $\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^* = \{1,2,\cdot\cdot\cdot, p-1\} $.
We're given that $\displaystyle \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} \equiv \{1,2,\cdot\cdot\cdot, p-1\} \mod{p}$. Hence for every $\displaystyle a \in \{1,2,\cdot\cdot\cdot, p-1\} $, there is a corresponding $\displaystyle x^k \in \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} $ such that $\displaystyle x^k \equiv a \mod{p} $. (A surjective map onto itself is injective too, if you like set theory.) That's what I meant when saying $\displaystyle x^k \equiv a \mod{p} $ is solvable.
Since $\displaystyle (x,p)=1 $, by Fermat's little theorem, $\displaystyle x^{p-1} \equiv 1 \mod{p} $. Hence $\displaystyle x^{c\cdot (p-1)} = \left(x^{p-1}\right)^c \equiv 1^c \equiv 1 \mod{p} $.I don't see why this is true...could you explain a little more on this, please??
Also, what is "a"?
How do you know that $\displaystyle x^{c(p-1)}$ = 1 (mod p) ???
Thanks for your help!
Let me try this proof a little bit differently.
Above, I showed for all $\displaystyle a \in \{1,2,\cdot\cdot\cdot, p-1\}, \; a^{\frac{p-1}{d}} \equiv 1 \mod{p} $, where $\displaystyle d=(k,p-1) $.
Choose $\displaystyle g $ such that it's a primitive root (we know one exists here). If $\displaystyle d>1 $, we would have $\displaystyle g^{\frac{p-1}{d}} \equiv 1 \mod{p} $, which is a contradiction since $\displaystyle \frac{p-1}{d} < p-1 $ and for all $\displaystyle c<p-1, \; g^c\not\equiv 1 \mod{p} $.
Our contradiction forces $\displaystyle d=1 $ as desired.
I'm not sure you know what a primitive root is...
A primitive root $\displaystyle g $ of a prime number $\displaystyle p $ is an element of $\displaystyle \{1,2,\cdot\cdot\cdot, p-1\} $ such that $\displaystyle g^c \not\equiv 1 \mod{p} $ for all $\displaystyle 0<c<p-1 $.