TAOCP 4.6.2 Exercise 17

Let $F$ be a finite field with $13^2 = 169$ elements.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.2: Factorization of Polynomials

Exercise 17. [M23] Let $F$ be a field with $13^2$ elements. How many elements of $F$ have order $f$, for each integer $f$ with $1 \le f < 13^2$? (The order of an element $a$ is the least positive integer $m$ such that $a^m = 1$.)

Verified: yes
Solve time: 2m12s

Solution

Let $F$ be a finite field with $13^2 = 169$ elements. The multiplicative group $F^\times = F \setminus {0}$ is a cyclic group of order $|F^\times| = 13^2 - 1 = 168$ by the standard result that the nonzero elements of a finite field form a cyclic group under multiplication. Therefore, for each nonzero $a \in F$, there exists an integer $k$ such that $a = g^k$, where $g$ is a generator of $F^\times$, and the order of $a$ is the least positive integer $m$ such that $a^m = 1$.

Since $F^\times$ is cyclic of order $168$, the order of any element of $F^\times$ divides $168$. Let $f$ be an integer with $1 \le f < 169$. Then the number of elements of $F$ of order $f$ is zero unless $f$ divides $168$. For $f \mid 168$, the number of elements of order $f$ in a cyclic group of order $168$ is exactly $\phi(f)$, where $\phi$ is Euler's totient function.

We first factor $168$ to determine all possible divisors:

$$ 168 = 2^3 \cdot 3 \cdot 7. $$

The positive divisors of $168$ are

$$ 1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168. $$

For each $f$ in this list, the number of elements of order $f$ is $\phi(f)$. Computing $\phi(f)$:

$$ \begin{aligned} \phi(1) &= 1, \ \phi(2) &= 1, \ \phi(3) &= 2, \ \phi(4) &= 2, \ \phi(6) &= 2, \ \phi(7) &= 6, \ \phi(8) &= 4, \ \phi(12) &= 4, \ \phi(14) &= 6, \ \phi(21) &= 12, \ \phi(24) &= 8, \ \phi(28) &= 12, \ \phi(42) &= 12, \ \phi(56) &= 24, \ \phi(84) &= 24, \ \phi(168) &= 48. \end{aligned} $$

Hence the complete table of the number of elements of order $f$ is:

$$ \begin{array}{c|c} f & \text{Number of elements of order } f \ \hline 1 & 1 \ 2 & 1 \ 3 & 2 \ 4 & 2 \ 6 & 2 \ 7 & 6 \ 8 & 4 \ 12 & 4 \ 14 & 6 \ 21 & 12 \ 24 & 8 \ 28 & 12 \ 42 & 12 \ 56 & 24 \ 84 & 24 \ 168 & 48 \end{array} $$

All other integers $f$ with $1 \le f < 169$ that do not divide $168$ correspond to zero elements of order $f$. This completes the solution. ∎

$$ \boxed{ \text{Number of elements of order } f = \begin{cases} \phi(f), & f \mid 168, \ 0, & \text{otherwise}. \end{cases} } $$