Group Theory – Proving Multiplicative Group Mod p is Cyclic

group-theorynumber theory

Let $\mathbb{Z}_p^*$ be the group of integers $\{1,2,3,\dots,p-1\}$ under multiplication mod $p$, where $p$ is a prime.

Given the following two facts:

  1. If $d$ divides $p-1$, then there are exactly $d$ elements in $\mathbb{Z}_p^*$ such that $a^d\equiv 1$.

  2. For all positive integer $n$, we have $\sum_{d | n} \phi(d) = n$. That is, the sum of Euler-Phi functions over divisors is $n$. (A proof can be found here https://proofwiki.org/wiki/Sum_of_Euler_Phi_Function_over_Divisors).

Given the above facts, how may we prove that the group $\{1,2,3,\dots,p-1\}$ under multiplication mod $p$ is cyclic?

Best Answer

Let $\psi(d)$ denote the number of elements of order $d$ in $\mathbb Z_p^*$.

Note that if $a\in\mathbb Z_p^*$ has order $d$, then $a^r$ has order $d$ if and only if $\gcd(r,d)=1$.

Thus are precisely $\phi(d)$ elements of the form of $a^r$ which have order $d$.

It follows that $\phi(d)$ divides $\psi(d)$ for all $d$.

Using (1) we want to show that $\psi(d)$ is either $0$ or equal to $\phi(d)$ for all $d|(p-1)$.

Assume on the contrary that there is some $d$ dividing $p-1$ such that $\psi(d)>\phi(d)$.

Let $a$ be an element of order $d$.

Out of the $d$ elements $a,a^2,\ldots,a^d$, precisely $\phi(d)$ have order $d$.

By our assumption, there is an element $b$ of order $d$ which is not equal to any of the $a^i$'s.

But note that $b$ and each $a^i$ satisfies $x^d\equiv 1\pmod{p}$.

This means that the congruence $x^d\equiv 1\pmod{p}$ has more than $d$ solutions, contrary to (1).

So we have $\psi(d)=0$ or $\phi(d)$.

Now note that $\sum_{d|(p-1)}\psi(d)=p-1$.

This is because each element of $\mathbb Z_p^*$ has order $d$ for some $d|p-1$.

From our earlier inference we also have $\sum_{d|p-1}\psi(d)\leq \sum_{d|p-1}\phi(d)$.

The RHS is equal $p-1$ by (2).

Therefore we cannot have $\psi(d)=0$ for any $d|p-1$ and hence $\psi(p-1)>0$, proving there is an element of order $p-1$ (and hence precisely $\phi(p-1)$ such elements).

Related Question