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.
 A: 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.
A: 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).  
