# Cyclic groups and finite fields

<strong>Cyclic groups</strong>: Every infinite cyclic group is isomorphic to the additive group of $\mathbb{Z}$, the integers. Every finite cyclic group of order $n$ is isomorphic to the additive group of $\mathbb{Z}/n\mathbb{Z}^+$, the integers modulo $n$. $\mathbb{Z}/n\mathbb{Z}^+$ is also referred to as the standard cyclic group $C_n$ in additive notation. Every cyclic group is an abelian group (meaning that its group operation is commutative).

Every group of prime order is cyclic, with all their non-identity elements as generators and are simple groups, which cannot be broken down into smaller groups. The multiplicative group of a prime field $\mathbb{F}(p)$ is a cyclic group of order $p-1$ and therefore not all its elements are generators.

<strong>Isomorphisms between cyclic groups:</strong> The additive group $\mathbb{Z}/(p-1)\mathbb{Z}^+$, $\{0,...,p-2\}$, i.e. integers mod $p-1$ with $p$ prime, is isomorphic to the multiplicative group of the prime field $\mathbb{F}(p)$, $\mathbb{Z}/p\mathbb{Z}^\times = \mathbb{Z}/p\mathbb{Z} - \{0\}$ with elements $\{1,...,p-1\}$. This is denoted $\mathbb{Z}/(p-1)\mathbb{Z}^+ \simeq \mathbb{Z}/p\mathbb{Z}^\times$.

"Multiplicative group of integers modulo $q$" where $q$ is not a prime number, $\mathbb{Z}/q\mathbb{Z}^\times$, is a group whose elements are a strict subset, $\subset \{1,...,q-1\}$, that are coprime with $q$, unlike modulo prime $p$ where every element $1\le a<p$ is coprime and have the inverse $a^{p-2}$ due to F.L.T.

In general, $\mathbb{Z}/q\mathbb{Z}^\times$ is not a cyclic group, does not have a generator and is not isomorphic to $\mathbb{Z}/(q-1)\mathbb{Z}^+$ if $q$ is not one of $\{1, 2^1, 2^2, p^k, 2p^k\}$, where $p > 2$ is a prime and $k > 0$. Therefore, aside from the special case of $p=2$, $q$ must equal $p^k$ (a prime power) or $2p^k$ for a prime $p$ for it to be cyclic (? verify the $2$ case which sounds doubtful since $2^k$ is used in extension fields in DES/AES..).

<strong>Order and number of generators:</strong> Both of these are cyclic groups with order $p-1$ and the number of generators of each is represented by the Euler's totient function $\phi(p-1)$, number of coprimes of $p-1$ greater than one and less than or equal to itself.

<strong>Generator pair to isomorphism:</strong> For the additive group, it is clear that $1 \in \mathbb{Z}/(p-1)\mathbb{Z}^+$ is a generator, along with any $\alpha$ that is coprime with $p-1$. We can write the elements of the group as an additive sequence that starts with the identity element $[0=(p-1)\alpha, 1\alpha, 2\alpha,... (p-2)\alpha ]$ for any given generator $\alpha$.

Similarly, given a generator of the multiplicative group $\delta \in \mathbb{Z}/p\mathbb{Z}^\times$, we can write the elements of the group as a multiplicative sequence that starts with the identity element, $[1=\delta^{p-1}, \delta^{1}, \delta^{2}, ... \delta^{p-2}]$.

Given a pair of generators $(\alpha, \delta)$, there exists an isomorphism that maps these sequences, $\lambda(k\alpha) = \delta^k: \mathbb{Z}/(p-1)\mathbb{Z}^+ \rightarrow \mathbb{Z}/p\mathbb{Z}^\times$ such that $\lambda(a + b) = \lambda(a) \cdot \lambda(b)$. Note that the identity elements map to each other, as well as the generator pair. Further, with another generator $\beta\neq \alpha$, we can have a different additive sequence $\{0, 1\beta, 2\beta,... (p-2)\beta \}$ that maps to the same multiplicative sequence $\{1, \delta^{1}, \delta^{2}, ... \delta^{p-2}\}$ through $\lambda(k\beta) = \delta^k$ i.e. a separate isomorphism (there are many).

<strong>Finite fields:</strong> $\mathbb{Z}/p\mathbb{Z}$ is a field when $p$ is a prime with the cyclic $\mathbb{Z}/p\mathbb{Z}^\times$ as its multiplicative group of order $p-1$, as every elements of it has multiplicinverses except for the identity element of its cyclic additive group $\mathbb{Z}/p\mathbb{Z}^+$ of order $p$. The field itself has an order $p$ and all fields of the same order are isomorphic to each other. The generators of its multiplicative group are also called <em>primitive elements of the field</em>.

$\mathbb{Z}/p\mathbb{Z}$ is denoted also as $\text{GF}(p)$ or $\mathbb{F}_p$ when $p$ is prime. $p$ is the <em>characteristic of the field</em> as summing $p$ copies of an element results in the additive identity element $0$. <em>Freshman's dream</em>, $(a+b)^p = a^p+b^p$ is true in a finite field of prime order.

<strong>$n$th roots of unity of finite field $\mathbb{F}_p$:</strong> In general, $n$th root of unity refers to a number whose $n$th power is $1$, i.e. $a^n = 1$. In the context of algebraic structures, the $n$th roots of unity refer to the elements of a cyclic group whose $n$ times group composition results in the identity element. For a multiplicative group, this is indicated by $a^n = 1$ and for an additive group, as $na = 0$. There may be many $n$th roots of unity as any power of an $n$th root of unity is itself an $n$th root of unity as well.

<strong>Primitive $n$th roots of unity:</strong>
A <em>primitive</em> $n$th root of unity $\omega$ on the other hand is defined as $\omega^n = 1$ s.t. $\omega^k \neq 1$ for $\forall k < n$. Such a primitive $n$th root of unity for the multiplicative group of the field can exists only if $n$ divides the order of the multiplicative group (in the same flavor as Langrange's theorem), e.g. in the case of $\mathbb{F}_p$, $p-1$ must be divisible by $n$. For any given generator $\delta$, $\delta^{\frac{p-1}{n}}$ is a primitive $n$th root of unity for the group (there are many).

<strong>Generators and primitive roots of unity:</strong>
Based on this general principle, in the case of $n = p-1$, we can see that any given generator $\delta=\delta^{\frac{p-1}{p-1}}$ is a primitive $(p-1)$th root of unity where $p-1$ is the order of the group. In other words, every generator of the cyclic group is a primitive root of unity for its order. The converse is also true, i.e. any given primitive $(p-1)$th root of unity is a generator of the cyclic group with order $p-1$, which is why they are also called <em>primitive elements</em>.

Note that if $n\neq p-1$, then primitive $n$th roots of unity are not generators of the group but can be generators of its subgroups (At least it sounds intuitive to me that this would be the case. Is this always true? Are all primitive $n$th roots of unity, if they exist, necessarily generators of subgroups?).