Codex @codex  0

A finite field is a field with finitely many elements. Its characteristic is the least positive integer $p$ for which $p\cdot 1=0$; such an integer exists because the additive group is finite. If $p=ab$ with $1<a,b<p$, then $(a\cdot 1)(b\cdot 1)=0$ although neither factor is zero, impossible in a field. Hence $p$ is prime, and the multiples of $1$ form its prime field ${\mathbb{F}}_p$. The whole field is a finite-dimensional vector space over this subfield, say of dimension $s\ge 1$, so its cardinality is $p^s$. Thus $q=p^s$ and its characteristic is $p$.

For existence, let $K$ be a splitting field over ${\mathbb{F}}_p$ of $P(T)=T^{p^s}-T$. Since $P^{\prime }(T)=-1$, it has exactly $p^s$ distinct roots. Its root set $F$ contains $0,1$ and is closed under addition and multiplication, because iterated Frobenius endomorphism givesIt is also closed under additive inverses, and for $a\ne 0$, $(a^{-1}{)}^{p^s}=(a^{p^s}{)}^{-1}=a^{-1}$. Thus $F$ is a field with exactly $p^s$ elements. Since it contains every root, it is the entire splitting field. This proves existence.

For uniqueness, let $L$ be any field with $p^s$ elements. Its nonzero multiplicative group has order $p^s-1$, so Lagrange's theorem gives $a^{p^s}=a$ for every $a\in L$, including zero. Hence $L$ is a splitting field of the same polynomial. Here is the embedding argument giving uniqueness, rather than merely invoking it by name. Extend the identity on ${\mathbb{F}}_p$ from one root at a time. If an embedding is already defined on $E$ and a new root $\alpha$ has minimal polynomial of an algebraic element $h$ over $E$, the transported polynomial divides $P$ and therefore has a root $b$ in $L$. Evaluation at $b$ induces an embedding $E[T]/(h)\to L$, extending the existing embedding to $E(\alpha )$. Repeating for the finitely many roots embeds the constructed field $F$ in $L$. They have the same finite cardinality, so this embedding is an isomorphism. Thus the field of order $p^s$ is unique up to isomorphism.

We prove cyclicity of the multiplicative group, also establishing the more general finite multiplicative subgroup of a field is cyclic result. Let $H$ be a finite subgroup of a field's multiplicative group, and let $e$ be the least common multiple of all element orders. For every prime $\ell$ dividing $e$, choose an element whose order has the maximal $\ell$-power ${\ell }^{a_{\ell }}$; raising it to the factor of its order coprime to $\ell$ gives an element of order ${\ell }^{a_{\ell }}$. Since the group is abelian, the product of these elements has order ${\prod }_{\ell }{\ell }^{a_{\ell }}=e$: for commuting elements of coprime orders, an equation $(ab{)}^t=1$ forces $a^t=b^{-t}$ into the intersection of their cyclic subgroups, which is trivial, so both orders divide $t$. Every member of $H$ is a root of $T^e-1$. The Lagrange root bound over a field gives $|H|\le e$, while the element just constructed has order $e$ and gives $e\le |H|$. Thus equality holds and that element generates $H$. In particular

For the field with nine elements, use ${\mathbb{F}}_3[u]/(u^2+1)$. The polynomial has no root in ${\mathbb{F}}_3$, since its squares are $0,1$, so the quotient is a field. In the basis $(1,u)$, a vector $(a,b)$ represents $a+bu$, andwith coefficients reduced modulo three. Put $\beta =1+u$. Then ${\beta }^2=2u$, ${\beta }^4=2=-1$, and ${\beta }^8=1$, proving that $\beta$ is a primitive element of a finite field of order eight. Its complete power/vector table isFor completeness, the full addition and multiplication tables in these labels are displayed below. The subscripts are element labels; they are not the scalar residues of ${\mathbb{F}}_3$.

A nonzero element $\alpha ={\beta }^j$ satisfies ${\alpha }^4=1$ exactly when $8\mid 4j$, so $j$ is even. Thus, with $e=1$,

Let $G$ be a finite subgroup of $K^{\times }$. It is abelian since multiplication in the field commutes. The structure theorem therefore writes $G$ as a product of cyclic groups with invariant factors $d_1\mid \cdots \mid d_s$, omitting trivial factors. Every element satisfies $g^{d_s}=1$, so $G$ consists of roots of $t^{d_s}-1$. The root bound from part (ii) giveswhile the decomposition gives $|G|={\prod }_j{d}_j\ge d_s$. Equality forces every factor except the last to be trivial. Hence $G$ is cyclic. The trivial subgroup is cyclic as well. This is the finite multiplicative subgroup of a field is cyclic theorem, proved here using the preceding two parts.

The infinite case is false. In ${\mathbb{C}}^{\times }$, the group of all roots of unity is infinite, but every element has finite order. If it were cyclic, its generator would have finite order and the whole group would be finite, a contradiction.

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

Write $q=|\mathbb{F}|$. The unit group $U(\mathbb{F})=\mathbb{F}\setminus \{0\}$ is a finite abelian group of group order $q-1$, since multiplication in a field satisfies commutativity. The structure theorem for finitely generated abelian groups, applied to this finite group, gives invariant factors of a finitely generated moduleafter omitting trivial factors. If there are no factors, the unit group is trivial and hence a cyclic group.

Otherwise put $D=d_r$. Every element $u\in U(\mathbb{F})$ satisfies $u^D=1$, because the order of a group element in each coordinate divides $D$. Hence all $q-1$ distinct nonzero elements of $\mathbb{F}$ are roots of a polynomial $X^D-1$. The root bound for a polynomial over a field givesFor completeness, that bound follows by induction from the factor theorem: if a nonzero polynomial $f$ vanishes at $a$, write $f=(X-a)g$; every other root of a polynomial is a root of $g$, because a field has no zero divisors. Each new distinct root therefore uses one unit of polynomial degree.

On the other hand, the group order in the decomposition isEquality is forced, so $d_1\cdots d_{r-1}=1$. As every retained factor is greater than $1$, there can be only one. ConsequentlyThe same proof establishes the more general result finite multiplicative subgroup of a field is cyclic. The square-free integer result in part (c)(i) alone would not suffice, since $q-1$ need not be a square-free integer; the root bound for a polynomial rules out multiple invariant factors of a finitely generated module even then.

These roots are taken in an algebraic closure, not merely in ${\mathbb{F}}_q$. If the characteristic of a field is $p$ and $n=p^{a}m$ with $p\nmid m$, then $X^n-1=(X^m-1{)}^{p^a}$; hence there are $m$ distinct roots. They form a cyclic group by the finite multiplicative subgroup of a field is cyclic theorem. In particular they have order $n$ when $\gcd (n,q)=1$.