Let $p\geq 2$ be a prime and let g be an element of order $p-1$ in $\Bbb Z_p$. Prove that every non-zero element of $\Bbb Z_p$ can be written as a power of $g$.

So i wanted to start this proof by proving the the elements $[g],[g]^2,[g]^3,...,[g]^{p-1}$ are all distinct. But im a bit uncertain on how do this . I thought it could be something with inverses since we are in $\Bbb Z_p$ but that didn't really workout.

  • 1
    $\begingroup$ If those elements are not distinct then two of them are the same. Deduce that the order of $g$ must then be lower than $p-1$. $\endgroup$
    – lulu
    May 21 '19 at 18:20
  • $\begingroup$ @lulu well the order is the smallest number m such that $g^m \equiv\ 1\ mod\ p$. So if two elements are the same then there exist a k and y such that $[g]^y = [g]^k$ but these y and k don't say anything about the order, correct? they just say that two powers give the same result with the base g. $\endgroup$
    – johnnyB
    May 21 '19 at 18:32
  • $\begingroup$ If $g^y=g^k$ with $y>k$ then $g^{y-k}=1$. $\endgroup$
    – lulu
    May 21 '19 at 18:36
  • $\begingroup$ @lulu Ok so i think i'm with both of you only one thing remains. There was a post here that got removed it seems that asked why the inverse of $[g]^k$ is $[g]^{-k}$ in modular arithmetic the inverse is usually noted as $[g]^{-1}$ the thing that got me thinking is that $[g]^{-k} will be a fraction and not an integer. So is this really correct? $\endgroup$
    – johnnyB
    May 23 '19 at 14:03
  • $\begingroup$ Fraction? There are no fractions in modular arithmetic, not in the usual sense. If $g$ is invertible, then we can speak of $g^{-1}$ and we can raise that inverse to the $k^{th}$ power. That's what we mean by $g^{-k}$. $\endgroup$
    – lulu
    May 23 '19 at 14:14

Hint Suppose the powers $g, g^2, \ldots, g^{p - 1}$ are not distinct, so that $g^k = g^l$ for some $1 \leq k < l \leq p - 1$. Multiply both sides by $g^{-k}$.

  • $\begingroup$ Oh $g^{-k}$ is the inverse?If we multipliy we get that $g^k = g^l$ multiplying by $g^{-k}$ we get $g^k * g^{-k} = g^l * g^{-k}$ which is equal to $1 = g^{l-k}$ So since k < l the power will be positive. But how do we know that $l-k \not =0?$ if that is the case then this is not a problem. Since $g^0 = 1$ $\endgroup$
    – johnnyB
    May 21 '19 at 18:49
  • $\begingroup$ Since $1 \leq k < l \leq p - 1$ we have $1 \leq l - k < p - 1$. $\endgroup$ May 21 '19 at 21:23
  • $\begingroup$ Is the fact that [1] is not in $Z_p$ the contradiction then? That is we can write non-primes as a power of g. I'm sorry but i am having some difficulty seeing the contradiction. $\endgroup$
    – johnnyB
    May 23 '19 at 5:43
  • $\begingroup$ Since $g^{l-k} = 1$, the order of $g$ divides $l-k$ and so cannot be $p-1$. $\endgroup$ May 23 '19 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.