proof

Posted on June 10, 2015 by Daniel — Leave a comment

The prototypical example of a finite field is ${\mathbf F}_p := {\mathbf Z} / p{\mathbf Z}$ for $p$ a prime number. We can also construct fields with $p^2$ elements by analogy with the complex numbers. Choose a non-square $d \in {\mathbf F}_p$ and define ${\mathbf F}_p[\sqrt{d}]$ to be the set of all formal expressions of the form $a+b\sqrt{d}$ with $a,b \in {\mathbf F}_p$ , together with the addition and multiplication laws $(a_1 + b_1 \sqrt{d}) + (a_2 + b_2 \sqrt{d}) = (a_1 + a_2) + (b_1 + b_2)\sqrt{d}$ and $(a_1 + b_1 \sqrt{d}) \cdot (a_2 + b_2 \sqrt{d}) = (a_1 a_2 + d b_1 b_2) + (a_1 b_2 + a_2 b_1)\sqrt{d}$ . One can easily check that ${\mathbf F}_p[\sqrt{d}]$ is a field, with the reciprocal of $\alpha = a+b \sqrt{d}$ given by $\bar{\alpha} / \| \alpha \|$ , where $\bar{\alpha} = a-b\sqrt{d}$ and $\| \alpha \| = \alpha \bar\alpha = a^2 + d b^2$ . We can identify ${\mathbf F}_p$ with the subfield $\{a + 0 \cdot \sqrt{d} \}$ of ${\mathbf F}_p[\sqrt{d}]$ .

Here are two basic properties of fields, both of which are usually known as “Lagrange’s Theorem”:

Lagrange #1: A polynomial of degree $k \geq 1$ with coefficients in a field $F$ can have at most $k$ roots in $F$ . (This is completely false if we replace “field” by “ring”.) See here for a proof in the special case $F={\mathbf F}_p$ which generalizes immediately to any field. We just need the following special case: the only roots of $x^2 - b^2$ in $F$ are $x = \pm b$ . This follows from the fact that $x^2 - b^2 = (x-b)(x+b)=0$ in $F$ implies that either $x-b = 0$ or $x+b=0$ .

Lagrange #2: Let $F$ be a finite field with $q$ elements and let $F^\times$ denote the nonzero elements of $F$ . Then the order $k$ of any $\alpha \in F^\times$ (defined as the smallest positive integer $\ell$ such that $\alpha^\ell = 1$ ) divides $|F^\times| = q-1$ . (This can be viewed as an extension of Fermat’s Little Theorem, the proof is basically the same: multiplication by $\alpha$ permutes the elements of $F^\times$ , and thus $\prod_{\beta \in F^*} \alpha \beta = \prod_{\beta \in F^*} \beta$ . Hence $\alpha^{q-1} = 1$ . Writing $q-1 = k\ell + r$ with $\ell,r$ integers such that $0 \leq r < \ell$ , it follows that $\alpha^r=1$ and hence $r = 0$ .)

The following property of the fields ${\mathbf F}_p[\sqrt{d}]$ will be crucial in what follows.

Key Lemma: For $\alpha \in {\mathbf F}_p[\sqrt{d}]$ , we have $\alpha^p = \bar\alpha$ .

Proof: Since $d$ is a quadratic non-residue modulo $p$ , Euler’s Criterion tells us that $d^{(p-1)/2} = -1$ in ${\mathbf F}_p$ . Thus $(\sqrt{d})^{p} = \sqrt{d} \cdot (\sqrt{d})^{p-1} = -\sqrt{d}$ in ${\mathbf F}_p[\sqrt{d}]$ . From the binomial theorem, the fact that $p=0$ in ${\mathbf F}_p[\sqrt{d}]$ , and Fermat’s Little Theorem, it follows that $(a+b\sqrt{d})^p = a^p + b^p (\sqrt{d})^p = a - b \sqrt{d}$ as desired.