# order of elements in $\mathbb{Z}_p^*$ with $p$ prime

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.

• What is the order of $-1$? If $a b \equiv 0$ you can only say that $a\equiv 0$ or $b \equiv 0$. – gammatester May 5 '18 at 13:39
• Not both, only one of the factors is divisible by $p$ (except perhaps, when $p=2$) – Peter May 5 '18 at 13:43
• 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. – Arthur May 5 '18 at 13:47
• Given a prime $p$ the order of $\mathbb{Z}_p^*$ is exactly $p-1$. – 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).

• 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$. – Arthur May 5 '18 at 14:16
• @Arthur yes. That is better... – Chris Custer May 5 '18 at 14:32