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've been trying to find the decomposition of $x^2-2$ to irreducible polynomials over $\mathbf{F}_5$ and $\mathbf{F}_7$. I know that for some $a$ in $\mathbf{F}_5$ (for example), $x-a$ divides $x^2-2$ iff $f(a) = 0$, i.e $a$ is a root of $x^2-2$. Over the field $\mathbf{F}_7$, I've found (by trail and error) that one irreducible polynomial is $x-3$. I've now got two questions -

  1. How can I find the other irreducible polynomial?
  2. Is there any more efficient method to find roots than trial and error?

Thanks in advance

share|improve this question
1  
To answer your first question, you can use either long division or trial and error. As for the second question, there isn't a more efficient method I am aware of right now, but that isn't to say there isn't a better way. –  Clayton Apr 17 '13 at 21:06
    
The problem is that long devision over finite fields is just not "working right" for some reason . An example could be great –  itamar Apr 17 '13 at 21:11
1  
@itamar, perhaps you're perfomring the long division without making arithmetic modulo 5 (or 7)? Because it works just fine over any field, whether finite or not. –  DonAntonio Apr 17 '13 at 21:42
1  
The usual rules of degree work for polynomials over a finite field, so try multiplying out and solving solving $x^{2}-2 = (x-3)(x-b)$ mod $7$ for $b$. –  tharris Apr 17 '13 at 21:43

2 Answers 2

In a field of characteristic other than $2$, the usual quadratic formula $$\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$ provides the roots of the quadratic polynomial $ax^2+bx+c$. So the roots of $x^2-2 = 2\left(\frac{1}{2}x^2-1\right)$ are $$\frac{-0\pm\sqrt{0^2-4\times\frac{1}{2}(-1)}}{2\times \frac{1}{2}} = \pm \sqrt{2}.$$ In $\mathbb F_5$, $2$ is not a quadratic residue and so $\sqrt{2}$ is not an element of $\mathbb F_5$, that is, $x^2-2$ is irreducible over $\mathbb F_5$. It does factor into two polynomials of degree $1$ in $\mathbb F_{5^2}[x]$. On the other hand, $\sqrt{2} = 3$ in $\mathbb F_7$ and so $x^2-2$ factors into two polynomials of degree $1$ in $\mathbb F_7[x]$.

share|improve this answer
    
how come that square root of 2 = 3 in F7 ? And thanks for the answer –  itamar Apr 18 '13 at 5:53
    
$3^2 = 9 \equiv 2 \bmod 7$. –  Dilip Sarwate Apr 18 '13 at 9:41

There are many ways of looking at this, but you’re just being asked to find a number that squares to $2$, modulo $5$ in the first case, modulo $7$ in the second. You can check that no matter what you square modulo $5$, the results are always $0$, $1$, $4$, so that $2$ has no square root here, and your polynomial is irreducible. Modulo $7$, it’s $0$, $1$, $2$ (because $3^2\equiv2\pmod7\>$) and $4$. Since you’ve found one square root of $2$ modulo $7$, the other is, of course, $-3\equiv4\pmod7$. Thus $x^2-2=(x-3)(x-4)$ over $\mathbb F_7$.

share|improve this answer

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.