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.
Best Answer
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.