# Roots in a finite field

Given a finite field $|K|=q$ and an irreducible $f \in K[x]$ with $\deg(f)=n$ with $\alpha$ as a root. My candidates for the roots are $\alpha, \dots , \alpha^{q^{n-1}}$.

Assuming $\alpha^{q^i} = \alpha^{q^j}$ I want to conclude that $\alpha = \alpha^{q^{j-i}}$ or more precisly I want to conclude that $f \mid x^{q^{j-i}}-x$.

Its a basic algebra course and we had not had Galois theory yet. So assume we have to lead $\alpha^{q^i} = \alpha^{q^j}$ to a contradiction by hand.

-
If $f$ is irreducible, then there is no root in $K$, so where do you find $\alpha$? – Thomas Andrews Jul 4 '12 at 14:48
In $K(\alpha)$. If $\alpha$ was in $K$ all the roots would be the same. – joachim Jul 4 '12 at 14:54
Read my revised answer to your previous question where I show the result that you need, viz. that if $\alpha^{q^0}, \alpha^{q^1}, \ldots, \alpha^{q^{m-1}}$ are distinct but $\alpha^{q^m} = \alpha^{q^i}$ for some $i \in \{0, 1, \ldots, m-1\}$, then the assumption that $i > 0$ leads to a contradiction, and it must be that $\alpha^{q^m} = \alpha$. Incidentally, what the result shows is that $f(x) \vert (x^{q^m} - x)$, not $f(x) \vert (x^m - x)$ as you claim you want to conclude. – Dilip Sarwate Jul 4 '12 at 15:08
The last paragraph of Arturo's answer to your previous question shows how to conclude $i=j$ from $\large \alpha^{q^i} = \alpha^{q^j}$, and thus $\large \alpha^{q^{j-i}} = \alpha^{q^0}=\alpha.$ – Ragib Zaman Jul 4 '12 at 15:29
joachim, I understand your concern, but it's possible that someone else may end up with the same misunderstanding on their own, and the answers that get posted to this page might help them too, so I'd like to keep this open. – Zev Chonoles Jul 4 '12 at 16:09

Judging from your comment to Dilip's answer to your previous question you have not fully absorbed one aspect of finite field arithmetic. Namely the fact that if $\mathrm{char} K=p$ (or equivalently $q=p^m$ for some positive integer $m$) implies the rules $$(a+b)^p=a^p+b^p,\qquad (a-b)^p=a^p-b^p.$$ I am willing to bet that this really is somewhere in your lecture notes, in which case this is just a refresher. Going from particular to general, let us first study the case $q=2^m$. Then $K$ has $\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}$ as a subfield, so in the field $K$ we have $2=1+1=0$, because that's the way it goes in that subfield. This implies that $$(a+b)^2=a^2+2ab+b^2=a^2+0ab+b^2=a^2+b^2$$ as claimed. Similarly, if $|K|=3^m$ it has $\mathbb{F}_3=\mathbb{Z}/3\mathbb{Z}$ as a subfield, and consequently $3=1+1+1=0$. This then implies $$(a+b)^3=a^3+3a^2b+3ab^2+b^3=a^3+0a^2b+0ab^2+b^3=a^3+b^3.$$ The general case $|K|=p^m, p>3$ follows from a similar calculation with the binomial formula, after we first observe that the binomial coefficient $${p\choose k}=\frac{p!}{(p-k)!k!}$$ is divisible by $p$ (the numerator is manifestly divisible by $p$, but the denominator is not, because $p$ is a prime and all the factors in the factorials in the denominator are smaller than $p$). The claim for the differences then follows from this rule by replacing $b$ with $-b$.

As a consequence of this fact we also get that in any extension field of $K$, e.g. in $K(\alpha)$ we have $$(a-b)^q=(a-b)^{p^m}=\left((a-b)^p\right)^{p^{m-1}}=(a^p-b^p)^{p^{m-1}}=\cdots a^q-b^q$$ proving the formula you had trouble with.

-

Let $\alpha$ be a root in an algebraic extension $L$ of $K$.

Since $(L^*,\cdot)$ is a group, you get by Lagrange Theorem than

$$\alpha^{q^i}=\alpha$$

Thus, $\alpha$ is a root of $x^{q^i}-x$. Now since $f$ is the minimal polynomial of $\alpha$ over $K$, you get that $f | x^{q^i}-x$.

-

Consider the field $L=K[x]/(f)\cong K(\alpha)$ where $\alpha$ is the image of $x$. Then the field $L$ has $q^n$ elements and the multiplicative group $L^*$ is cyclic with $q^n-1$ elements. So any element of $L$ satisfies $x^{q^n}-x$.

So $\alpha$ satisfies $x^{q^n}-x$, but $\alpha$ does not have to be the generator of the multiplicative group.

If you know that $L$ is the splitting field of $f(x)$ then you could conclude that $f\ |\ x^{q^n}-x$

-

Note that every element of $K(\alpha)$ satisfies $r^{q^n} = r$, as noted.

Assume $\alpha^{q^i} = \alpha^{q^j}$ with $i\leq j$. Then: $$\alpha = \alpha^{q^{n}}=(\alpha^{q^i})^{q^{n-i}} = (\alpha^{q^j})^{q^{n-i}} = \alpha^{q^{n+j-i}} = \alpha^{q^nq^{j-i}} = (\alpha^{q^n})^{q^{j-i}} = \alpha^{q^{j-i}},$$ which is the equality you want.

-