1
$\begingroup$

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.

$\endgroup$
4
  • $\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$ May 5, 2018 at 13:39
  • $\begingroup$ Not both, only one of the factors is divisible by $p$ (except perhaps, when $p=2$) $\endgroup$
    – Peter
    May 5, 2018 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, 2018 at 13:47
  • $\begingroup$ Given a prime $p$ the order of $\mathbb{Z}_p^*$ is exactly $p-1$. $\endgroup$
    – Yanko
    May 5, 2018 at 14:01

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\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, 2018 at 14:16
  • $\begingroup$ @Arthur yes. That is better... $\endgroup$
    – user403337
    May 5, 2018 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .