3
$\begingroup$

The question I'm inquiring about is all in the title, but I would be more interested in a few things related to the question which I don't know. I know what a primitive root of $\mathbb{F}_p$ is for any prime - an element $g \in \mathbb{F}_p$ such that $\{g^1, \dots, g^{p-1}\}$ generates the entire set $\mathbb{F}_p$ excluding 0. I don't know what elements of $\mathbb{F}_7[x]/(x^2+1)$ look like, and if there is a reasonable way to check if a given element is a primitive root like in $\mathbb{F}_p$, where all that is needed is to check that $g^n \not\equiv 1$ for any $n < p-1$ that divides $p-1$. Also what is the structure called where you take the quotient of a finite field? I'm not sure but I think that is what $\mathbb{F}_7[x]/(x^2+1)$ is an example of.

Edit: So I started multiplying everything out, taking $g^1,\dots,g^8$ taking $g = (2+5x)$ and $g^k$ to be the result modding all the coefficients by $7$ then the remainder of that divided by $(x^2 + 1)$. For example $g^2 = (5x+2)^2 = 25x^2 + 20x + 4 \equiv 4x^2 + 6x + 4 \equiv 6x$. I did this up to $g^8 = (5x+2)(2x+2) = 10x^2 + 14x + 4 \equiv 3x^2 + 4 \equiv 1$. I believe there are supposed to be 48 elements generated, and this would cycle for only 8 elements so it shouldn't be a primitive root. I am sure there must be a more efficient way of checking this, but I am also not all too confident that this is entirely correct.

$\endgroup$

2 Answers 2

5
$\begingroup$

Note that ${\bf F}_7[x]/(x^2+1)$ is not "a quotient of a finite field." In fact the only quotients of any field are the field itself and the trivial ring (which is not itself a field), or equivalently the only ideals of a field are the trivial ideal and the whole field (this follows from everything being invertible).

Rather, this is a quotient of the polynomial ring over a finite field. In fact, creating any finite field extension is equivalent (up to isomorphism) of adjoining formal variables and then quotienting by the ideal generated by the relations these variables satisfy in the extension field. For example, to create ${\bf Q}(\sqrt[3]{2})$, we adjoin the variable $x$ satisfying the relation $x^3=2$: so ${\bf Q}(\sqrt[3]{2})\cong{\bf Q}[x]/(x^2-2)$.

Note that in ${\bf F}_7$, the element $-1$ (i.e. $6$) does not have any square root, so in order to create an extension field containing such a square root, we use this process to get ${\bf F}_7[x]/(x^2+1)$. In fact you may check that $x^2+1$ is irreducible in ${\bf F}_7[x]$ (since it's degree two, this merely says it doesn't have any root in the field), hence the ideal it generates is maximal in the polynomial ring (as it's a PID due to the availability of Euclidean division), hence the quotient is also a field. In general quotients of polynomial rings need only be rings, not fields, so this is why the check is relevant.

What do elements of ${\bf F}_7[x]/(x^2+1)$ "look like"? Well, just like with integers mod $7$ we can "chop off" multiples of $7$ at will, here we can chop off multiples of $x^2+1$, or equivalently replace every instance of $x^2$ with $-1$. As a result, any polynomial expression in $x$ can be reduced to the much simpler form $a+bx$ (can you see why?). There are $7$ choices of scalars for $a$ and $b$ independently, so there are $7^2$ elements here. Note we can tell they are distinct elements of the quotient for distinct choices of $a$ and $b$: verify $a+bx=c+dx\Leftrightarrow (x^2+1)\mid[(a-c)+(b-d)x]\Leftrightarrow a=c,b=d$.

As you will or may have heard or studied, there is a classification of finite fields. For any power of a prime $q=p^s$, there is precisely one field of order $p^s$ up to isomorphism, and these are all possible finite fields. For just a prime $p$ the field is ${\bf F}_p$, in general ${\bf F}_q$ can be obtained as ${\bf F}_p[x]/(\pi(x))$ for some irreducible polynomial $\pi(x)$ of degree $s$, or as the so-called splitting field of $x^q-x$.

It is a basic abelian group theory exercise that if a finite group $G$ has at most $d$ elements of order $d$ for each divisor $d\mid\#G$, then $G$ is cyclic. This shows that any finite subgroup of $F^\times$ is cyclic for any field $F$ (finite or infinite, characteristic zero or nonzero). In particular, ${\bf F}_q^\times={\bf F}_q\setminus\{0\}$ is cyclic of order $q-1$. To check if $u\in {\bf F}_q$ is a primitive root, it suffices to check that $u^d\ne1$ for every proper divisor $d\mid(q-1)$, and for that it is sufficient to check that $u^{(q-1)/r}\ne1$ for every prime divisor $r\mid(q-1)$. (This is because the divisors $\frac{q-1}{r}\mid(q-1)$ are "cofinal" in the "poset.")

Here we have $q-1=48=2^4\cdot3$, so we check $(2+5x)^{24}\ne1\ne(2+5x)^{16}$. We have

$$(2+5x)^{24}=(2-2x)^{24}=2^{24}(1-x)^{24}=(1-2x+x^2)^{12}=(2x)^{12}=2^{12}(-1)^6=1.$$

Hence $2+5x$ is not a primitive root.

$\endgroup$
2
$\begingroup$

No, it isn't. You can calculate $$(2+5x)^2 = 25(x^2 + 1) + 20x - 21 \equiv -x$$ and so $$(2+5x)^4 \equiv (-x)^2 = x^2 \equiv -1$$ and $$(2+5x)^8 \equiv 1.$$ A primitive root would only have $(2+5x)^{n} \equiv 1$ for $n \in 48\mathbb{Z}.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .