Question on primary assumption in this proof that every multiplicative group of finite field is cyclic.

Question

Given in my textbook is the theorem

If $F$ is a finite field of the order $q$ than is group $F^*,\cdot$ a cyclic group of the order $q - 1$. ...

The proof starts with a straightforward assumption that follow from the definition of a field.

... The multiplicative group $F^*$ is thus from the order $q - 1$ ...

What follows then however is a very important assumption that is to make a very important conclusion of this proof at the end and on which it falls or stand. I do however not understand why this assumption is true. The assumption goes as follows:

... such that for any element $f \in F^*$ it is true that $f^{q-1} = 1$. As a consequence the equation $x^{q-1} - 1 = 0$ has exactly $q -1$ roots in $F^*$. ...

I understand that if indeed it is true that if $f^{q-1} = 1$ is true for every element in $F^*$ that there are than those $q-1$ roots in $F*$. Here is my question however: Why is it true that $f^{q-1} = 1$ is true for every element in $F^*$?

The rest of the proof I do understand, and I'll give a summary of it here for the sake of completion.

The theorem is used that "$F^*$ is a cyclic group of order $q-1$" (i) is equivalent with "Let $d$ be a divisor of $n$. There are $d$ solutions in $F^*$ to the equation $x^d = 1$" (ii) for "$f^*$ a finite group".

(ii) is proved as follows:

• Using polynomials from $F_{[x]}$, assuming that $q -1 = dk$, than it follows that $x^{q-1} - 1 = (x^d - 1)(x^{d(k - 1)} + x^{d(k - 2)} + \cdots + x^d + 1 = (x^d - 1) \cdot g(x)$;
• $g(x)$ is of degree $d(k-1)$ and has therefore at most $d(k-1)$ roots in $F*$;
• $(x^d - 1)$ is of degree $d$ and has therefore at most $d$ roots in $F*$;

We know however that using the earlier assumptions that $x^{q-1} - 1 = x^{dk} - 1$ has exactly $q-1$ roots. And as $d + d(k -1) = d + dk - d = dk = q - 1$ it follows that $x^d + 1$ has exactly d roots in $F*$.

Now that (ii) is proven it follows that (i) is true as well and therefore it has been proven that the multiplicative group $F^*,\cdot$ of a finite field $F$ of order $q$ is a cyclic group of order $q - 1$.

So to highlight my question:

Why is it true that $f^{q-1} = 1$ is true for every element in $F^*$?

if $q$ is prime, than I know (and I can see) that every element of $\mathbb{Z}_q$ is a primitive root and therefore I can see that $x^{q-1} = 1$ is true for every $x \in \mathbb{Z}_q$, using Fermath's little theorem.

But why is this true for every $q$? Has it something to do with the fact that the order of a finite field $q$ is always in the form $p^h$ with $p$ a prime and $h$ the dimension of the $G$-vector space with $G$ the additive subgroup generated by the 1 and with order $p$?

edit: from my experience with constructing finite fields of order $p^h$ (using polynomials of degree $h$), I have noticed that $f^{q-1} = 1$ holds indeed for all $f \in F_{p^h}^*$ with $q = p^h$. We know that the order is $q$, and if I remember correctly Zech's algorithm relies on the fact that the exponents are modulo the order of the multiplicative group. This makes me think that because we know that $x^s = x^r$ in $F_{p^h}^*$ if and only if $r \equiv s (mod\ q-1)$ and thus we know that $x^{q-1} = x^0 = 1 \leftrightarrow q-1 \equiv 0\ (mod\ q-1)$. Which is always true, no matter the value of $x$. Is this why the assumption is true, or am I on the wrong track?

Answer 1

Why is it true that $f^{q-1} = 1$ is true for every $f \in F^*$?

Lagrange's theorem states the following.

For every $(H,\cdot)$ is a subgroup of finite group $(G,\cdot)$, $|H|$ is a divisor of $|G|$.

We also know that the order $k$ of an element $f \in F^*$ is the smallest positive integer such that $f^k = 1$. Because Lagrange's theorem it also follows that $k$ divides $q-1$ since the order $k$ of $f$ equals the order of the cyclic subgroup it generates.

Why is it true that $f$ generates a cyclic subgroup of $F^*$ of order $k$?

It is trivial to see that $f^0 = f^k = 1$ is part of $F^*$. We can also see that $f^i$ with $0 <= i < k$ must be in $F^*$ as $F^*$ is a group and therefore multiplication is closed. By contradiction assume that $f^i = f^j$ for $0 <= i < j < k$. Than it follows that this is true if and only if $i \equiv j\ (mod\ k)$. It must therefore be true that $\langle f \rangle = \{f^{i} \in F^* | 0 <= i < k\}$ is cyclic and $|\langle f \rangle| = k$.

If we bring this all together we get

$$ f^{q-1} = f^{dk} = (f^k)^d = 1^d = 1. $$

As $f$ was chosen at random, it follows that $f^{q-1} = 1$ is true for every $f \in F^*$.

Answer 2

This is Lagrange's theorem. The order of the group is $q-1$.

The theorem states/implies that the order of any element divides the order of the group. Just consider the subgroup generated by that element.