Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on a fairly simple problem about a field, but I want to know if the operations can be explicitly described.

Suppose $c$ is not a quadratic residue modulo $p$, and consider the quotient ring $\mathbb{F}_p[X]/(x^2-c)$. Now $x^2-c$ is irreducible over $\mathbb{F}_p$, so it generates a maximal ideal, and thus $\mathbb{F}_p[X]/(x^2-c)$ can be viewed as a 2-dimensional vector space over $\mathbb{F}_p$, and thus has order $p^2$. If I take $a$ to be a root of $x^2-c$ in some extension field, then I can view the elements of the field as $0,a,c,ac,c^2,ac^2,c^3,\dots,ac^{(p^2-3)/2},c^{(p^2-1)/2}$, for a total of $p^2$ elements.

However, I don't know how to actually state what addition and multiplication look like in this field. Is there a clever way to describe the operations explicitly? Thanks.

share|improve this question
    
I think you meant is irreducible :) –  Zev Chonoles Nov 11 '11 at 4:55
    
Those are not all the elements of the field; you have a lot of repeats, because you know for sure that $c^p=c$ (and possibly smaller powers too). –  Arturo Magidin Nov 11 '11 at 5:14
    
Zev describes below how to do arithmetic in this field. I want to add that your description is incorrect. Because $c$ is an element of the prime field, we have $c^{p-1}=1$ by little Fermat. Thinks may go wrong even earlier. Just because $c$ is not a quadratic residue, it doesn't mean that it would also be primitive. For a most striking example $c=-1$ is not a square in $GF(3)$ or $GF(7)$, but we always have $(-1)^2=1$. –  Jyrki Lahtonen Nov 11 '11 at 5:16
    
Oops, I think I slipped up since the unit group of fields of prime order are cyclic, but that doesn't work here. –  Vika Nov 11 '11 at 5:39
1  
@Vika: The unit group of any finite field is cyclic. But you have to look harder to find a generator. –  Jyrki Lahtonen Nov 11 '11 at 6:09

2 Answers 2

up vote 3 down vote accepted

I would recommend thinking about it as just addition and multiplication of polynomials in $\mathbb{F}_p[x]$, modulo $x^2-c$. Given some polynomial $f\in\mathbb{F}_p[x]$, by the division algorithm we have that $$f=(x^2-c)q+r\quad\text{ where }q,r\in\mathbb{F}_p[x], \text{ and }\deg(r)<2.$$ So for any $f\in\mathbb{F}_p[x]$, we have $$f\equiv a_0+a_1x\pmod{x^2-c}$$ for some $a_0,a_1\in\mathbb{F}_p$, and so the elements of $\mathbb{F}_p[x]/(x^2-c)$ are the $p^2$ different equivalence classes we get as $a_0$ and $a_1$ range over their $p$ possible values. We can think of $a_0+a_1x\pmod{x^2-c}$ as representing "$a_0+a_1\sqrt{c}$ ". Then the operations are just as we would expect: $$(a_0+a_1\sqrt{c})+(b_0+b_1\sqrt{c})=(a_0+b_0)+(a_1+b_1)\sqrt{c}$$ and $$(a_0+a_1\sqrt{c})(b_0+b_1\sqrt{c})=(a_0b_0+a_1b_1c)+(a_1b_0+a_0b_1)\sqrt{c},$$ because $$(a_0+a_1x)+(b_0+b_1x)\equiv(a_0+b_0)+(a_1+b_1)x\pmod{x^2-c}$$ and $$\begin{align*}(a_0+a_1x)(b_0+b_1x)&\equiv a_0b_0+(a_1b_0+a_0b_1)x+a_1b_1x^2 \\ &\equiv a_0b_0+(a_1b_0+a_0b_1)x+a_1b_1(x^2-0)\\ & \equiv a_0b_0+(a_1b_0+a_0b_1)x+a_1b_1(x^2-(x^2-c))\\ &\equiv (a_0b_0+a_1b_1c)+(a_1b_0+a_0b_1)x\hskip1in\pmod{x^2-c}\end{align*}$$

share|improve this answer
    
Thanks Zev, (chars). –  Vika Nov 11 '11 at 21:32

The elements you list need not be all distinct, so your list need not be the full list of elements of your field.

For example, consider $\mathbf{F}_7$; the squares are $1$, $2$, and $4$. In particular, $-1$ is not a square, so you can take $c=-1$; then your list of elements consists only of $0$, $a$, $-1$, $-a$, and $1$, which is only $5$ elements, not the required $49$.

In fact, your list can never be all the elements, because $c^p = c$ holds, so you are repeating a lot of elements, and not getting all of them.

(Added. The best you can hope for is if $c$ is a primitive element of $\mathbf{F}_7$; that is, it generates the group of units. You still get only $2p-1$ of the required $p^2$ elements, though.)

Instead, you want to think of the elements as being the result of evaluating polynomials at $a$; since every polynomial can be written as a multiple of $x^2-c$ plust a remainder, the elements of the field will be of the form $ra+s$, with $r,s\in\mathbb{F}_p$. You add them the usual way, $(ra+s) + (ta+u) = (r+t)a+(s+u)$, with addition on the right being addition modulo $p$, and you multiply them by using the fact that $x^2=c$, $$(ra+s)(ta+u) = (ru+st)a + (su+rtc).$$

share|improve this answer
    
Thanks Arturo (extra chars). –  Vika Nov 11 '11 at 21:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.