I have a small question, is there a theorem about the order of the elements in the multiplicative group $\mathbb{Z}_p^*$ when $p$ is prime?

I'm looking into the reduction of order finding to factoring. could it be that the order of all elements $x \in \mathbb{Z}_p^*$ are odd. Because for an even order $r$ (thus $x^r \equiv 1$ mod $p$) we have:

$(x^{r/2}-1)(x^{r/2}+1) = x^r -1 \equiv 0$ (mod $p$)

which means $(x^{r/2}-1)$ and $(x^{r/2}+1)$ would be two factor of $p$ which would be a contradiction.

  • $\begingroup$ What is the order of $-1$? If $a b \equiv 0 $ you can only say that $a\equiv 0 $ or $b \equiv 0$. $\endgroup$ – gammatester May 5 '18 at 13:39
  • $\begingroup$ Not both, only one of the factors is divisible by $p$ (except perhaps, when $p=2$) $\endgroup$ – Peter May 5 '18 at 13:43
  • 2
    $\begingroup$ It is known that $\Bbb Z_p^*$ is cyclic when $p$ is prime. From there arguing about the order of elements is not very difficult. $\endgroup$ – Arthur May 5 '18 at 13:47
  • $\begingroup$ Given a prime $p$ the order of $\mathbb{Z}_p^*$ is exactly $p-1$. $\endgroup$ – Yanko May 5 '18 at 14:01

The multiplicative group of integers modulo a prime $p$ is cyclic of order $p-1$. In particular, it contains exactly $\varphi(k)$ elements of order $k$ for each $k$ that divides $p-1$, and contains no elements of order $k$ if $k$ does not divide $p-1$. Here, $\varphi(k)$ is the Euler phi function.

(This because a cyclic group of order $n$ has exactly one subgroup of order $d$ for each divisor $d$ of $n$, and has $\varphi(n)$ generators, i.e., elements of order exactly $n$).

This means the only case in which $\mathbb{Z}_{p}^*$ only has elements of odd order is when $p=2$, when the group is trivial.

The reason your argument does not go through to its conclusion is that if $x$ is of even order $r$, then $x^{r/2}$ is of order $2$. And there is exactly one element of order $2$ in $\mathbb{Z}_p^*$, namely $[-1]$ (the class of $-1$. That means that the factor $x^{r/2}+1$ is actually congruent to $0$ modulo $p$. Also, your conclusion that the factors $x^{r/2}+1$ and $x^{r/2}-1$ “would be two factors of $p$” is incorrect: you have that $p$ divides the product, and hence divides at least one factor. Not that the two factors divide $p$. Indeed, $p$ divides $x^{r/2}+1$ as noted above.


Since the order of $\mathbb Z_p^*$ is $p-1$, the order of every element divides $p-1$ by Lagrange. From which we get Fermat's little theorem...

Also, as Arthur points out, $\mathbb Z_p^*$ is known to be cyclic. Thus there is an element of order $p-1$. And there are $\phi(d)$ elements of order $d$ for every $d$ dividing $p-1$ (where $\phi$ is the totient function).

  • $\begingroup$ We can do better than this. For instance, in $\Bbb Z_5^*$ it is true that the order of each element divides $4$, but your answer doesn't say whether there actually is an element of order $4$. $\endgroup$ – Arthur May 5 '18 at 14:16
  • $\begingroup$ @Arthur yes. That is better... $\endgroup$ – Chris Custer May 5 '18 at 14:32

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.