Let $p$ be a prime, and let $q>1$ be relatively prime to p.
In a paper that I'm reading, it says that "since p is an element of the group of units modulo q, there exists m > 0 such that $p^m \equiv 1 \pmod{q}$ and thus $q\mid(p^m – 1)$". So my first question is, what is meant by "group of units modulo $q$"? Is this simply the multiplicative group $\mathbb{Z}_q^{\ast}$ or how is it defined?
Then the text continues by defining $F:=GF(p^m)$ and saying, "since the multiplicative group of a finite field is cyclic, this implies that $F$ contains a primitive $q^\text{th}$ root of 1 – that is, an element g such that $g^q = 1$, and $g^r \neq 1$ for $1 \leq r < q$." Therefore, my second question is why such a q-th primitive root has to exist, I can't follow this reasoning.
Any help on answering these questions is highly appreciated! 🙂
Best Answer
Question 1: The integers modulo $q$ form a ring under modular addition and modular multiplication. The units modulo $q$ are the elements of this ring that have multiplicative inverses; it consists precisely of the classes of integers $a$, such that $\gcd(a,q)=1$. It is a group under modular multiplication, and it is indeed often denoted $(\mathbb{Z}_q)^*$ or $\mathbb{Z}_q^*$.
The assertion is that because $\gcd(p,q)=1$, then $p$ is invertible modulo $q$; that is, it is an element of the multiplicative group $\mathbb{Z}_q^*$. Because this is a finite group, $p$ has finite order in this group, which is $m$.
Second Question: The order of the multiplicative group of nonzero elements of $F$ is $p^m-1$. You have a cyclic group of order $p^m-1$. A cyclic group of order $k$ has a subgroup of order $d$ if and only if $d$ divides $k$, and in that case it has one and only one subgroup of that order. Since $q$ divides $p^m-1$, and the nonzero elements of $F$ form a a cyclic group of order $p^m-1$, this cyclic group has a subgroup of order exactly $q$. This subgroup is cyclic (subgroup of cyclic group is cyclic), generated by some element $g\in F$. Thus, $\langle g\rangle$ has order $q$, so $g^q=1$ but $g^r\neq 1$ for $1\leq r\lt q$. This is from the group theory side.
Now, in a field, an element $\zeta$ such that $\zeta^n=1$ but $\zeta^r\neq 1$ for $1\leq r\lt n$ is called a "primitive $n$th root of unity". So the $g$ we found in $F$ is a primitive $q$th root of unity in $F$.